# Deriving a formula and induction

1. Mar 30, 2009

### muso07

1. The problem statement, all variables and given/known data
We know that T(2)=1, and T(n+1)=1+2T(n), i.e. T(3)=1+2*1=3, etc.
Derive a formula for T(n) from above information. Prove the formula by mathematical induction.

2. Relevant equations
??
I don't think there are any apart from the stuff from above.

3. The attempt at a solution
I don't really know where to start... Isn't T(n+1)=1+2T(n) already a formula? How am I supposed to come up with another one?

Basically, in the previous part, I showed that the sequence goes 1, 3, 7, 15, 31,.. as per the rule. (Not sure what the point of that was.) But the question says to use that to derive the formula.

I just need some help with coming up with the formula.. hopefully I can do the induction stuff by myself.

Any help would be greatly appreciated!

2. Mar 30, 2009

### lanedance

Hi Muso07

I noticed you could re-write the first 2 terms as:
$$T(2) = 1 = 1+(1-1) = 2-1= 2^1 - 1$$
$$T(3) = 1+2.1 = 2 + 2 - 1 = 2^2 - 1$$
hope this helps

3. Mar 31, 2009

### muso07

Thank you so much!