
Proof induction
Stuck on a question , im very confused.
Use mathematical induction to show that
S(n) = 3 × 2 n1 2
is the solution for the recurrence relation:
T(n) = 2T(n – 1) + 2 for n > 1 and T(1) = 1
Ive answered
T(n) = 2T(n – 1) + 3
= 2T(n 2) + 2
= 2(2T(n − 2) + 1) + 1
= 2(3 × 2^(n2) 2) + 2
S(n) = 3 × 2 n1 2
S = 0 , T=0
It just dosnt make sense to me, the coursework is so large im running out of time to try work this out.
please help :(

Re: Proof induction
I think there is something missing, for T term we have T on right hand side
the expression for S(n) also appears to be confusing. Please clarify.
The steps fro MI are very clear.
1. Check if the statement is true for n = 1
2. assume the statement to be true for n = k and then
3. Prove that the statement is true for n = k + 1

Re: Proof induction