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