Induction proof to prove recursive formula is equal to explicit formula
I'm really stuck on these, any help is appreciated. In each of the following a sequence is defined recursively. Guess an explicit formula for the sequence, then use mathematical induction to prove the correctness of your formula. Sorry I had some font sizing issues. If you can just explain the first one, then I can probably figure out the other two. Thanks.
(a) csub(k) = 3csub(k- 1) + 1, for all integers k >= 2
c1 = 1
(b) gsub(k) = (gsub(k -1) ) / (gsub(k- 1) + 2) , for all integers k >= 2
g1 = 1
(c) psub(k) = psub(k -1) + 2 · 3^k, for all integers k >= 2
p1 = 2
Re: Induction proof to prove recursive formula is equal to explicit formula
I think I might be spoiling you because in this format it's hard to read and not likely to get accepted.
(a) ck = 3ck-1 + 1 for all integers (INDUCTION STATEMENT P)
c1 = 1
ck-1 = 3ck-2 + 1, so
ck = 3 (3ck-2 + 1) + 1 = (3^2)ck-2 + 2 (MODIFIED INDUCTION STATEMENT P)
((Proceed inductively by replacing ck-m term until you reach c1 = 1 ))
= 3^(k-1)c1 + k
= 3^(k-1) + k
Prove this statement by general induction if needed.