# Induction proof to prove recursive formula is equal to explicit formula

• November 14th 2012, 04:31 PM
Walshy
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

• November 14th 2012, 04:54 PM
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 $k \geq 2$ (INDUCTION STATEMENT P)
c1 = 1

However,
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.