Date: Feb 9, 2013 4:06 AM Author: jokie Subject: Proof induction Stuck on a question , im very confused.

Use mathematical induction to show that

S(n) = 3 × 2 n-1 -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^(n-2) -2) + 2

S(n) = 3 × 2 n-1 -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