Question

Q(n) = {4 if n = 0
Q(n) = {2 · Q(n − 1) − 3 if n > 0
Prove by induction that
Q(n) = 2n + 3, for all n ≥ 0.
(Induction on n.) Let f(n) = 2n + 3.
Base Case: If n = 0, the recurrence relation says that Q(0) = 4, and the formula says that f(0) = 2 ? + 3 = ? , so they match.
Inductive Hypothesis: Suppose as inductive hypothesis that Q(k − 1) = ? for some k > 0.
nductive Step: Using the recurrence relation,
Q(k) = 2 · Q(k − 1) − 3, by the second part of the recurrence relation
= 2( ? ) − 3, by inductive hypothesis
= (2k + 6) − 3
= ?
so, by induction, Q(n) = f(n) for all n ≥ 0.

Answer 1

Let f(n) = 2n + 3.
Base Case: If n = 0, the recurrence relation says that Q(0) = 4, and the formula says that f(0) = 2 ? + 3 = ? , so they match.

f(0) =2*0+3 = 3, I don't see how they match

Answer 2

see if this makes more sense

Answer 3

ahh you put 2n+3

Answer 4

yeah, couldnt get the equation to look right

Answer 5

the first box is 0
the second is 4
the third is 2^(k-1) + 3
the fourth is 2^(k-1)+3
the last is f(k)

Answer 6

I hate to tell you the answers like this, but I have to run and I hope at least this way you will figure it out.

Answer 7

Thanks it does help

Answer 8

1) 0 because we want f(0)
2) IH if f(k-1) then f(k)
3) f(k-1)
4) f(k-1)
5) we are trying to show if f(k-1) then f(k) and the last step shows that

Answer 9

as always, you are a huge help...I understand it now, thank you

Answer 10

good deal, have a good day