How to complete this proof regarding closed form of tower of hanoi problem? 
Possible Duplicate:
can one derive the $n^{th}$ term for the series, $u_{n+1}=2u_{n}+1$,$u_{0}=0$, $n$ is a non-negative integer 

I'm trying to learn induction through practise and I'm dealing with the classic tower of hanoi question.
$T_{n} = 2T_{n-1} + 1$ 
for $ n > 0$
I've come up with a closed form equation:
$T_{n} = 2^{n}-1$
Now I'm trying to prove the second statement inductively and this is what I have thus far, but I think I'm missing the mark a bit. 
$T_{n} = 2T_{n-1}+1=2(2^{n-1}-1)+1 = ...$
I'm sure that this expands out to $2^{n} - 1$ but I cant seem to do it. Can someone please show me how?
 A: What you really want to show is that the function $f(n)=2^n-1$ that expresses your closed form solution satisfies the recurrence and initial conditions of the Tower of Hanoi problem. The recurrence should be $T_n=2T_{n-1}+1$ for $n>0$. You want to prove by induction that $T_n$, defined by this recurrence with initial condition $T_1=1$, is equal to $f(n)$ for every positive integer $n$.
First we get the induction off the ground: $f(1)=2^1-1=1=T_1$, so all’s well. Now assume that $T_n=f(n)$ for some $n\ge 1$; that’s your induction hypothesis, and you want to use it to prove that $T_{n+1}=f(n+1)$. The computation is pretty straightforward:
$$\begin{align*}
T_{n+1}&\overset{(1)}=2T_n+1\\
&\overset{(2)}=2f(n)+1\\
&\overset{(3)}=2\left(2^n-1\right)+1\\
&\overset{(4)}=2\cdot2^n-2+1\\
&\overset{(5)}=2^{n+1}-1\\
&\overset{(6)}=f(n+1)
\end{align*}$$
Here $(1)$ is by virtue of the recurrence definining the numbers $T_k$, $(2)$ uses the induction hypothesis that $T_n=f(n)$, $(3)$ replaces $f(n)$ by its definition, $(4)$ and $(5)$ are algebra, and $(6)$ is the definition of $f$ again.
Since you’ve checked that $T_1=f(1)$ and that $T_n=f(n)$ implies that $T_{n+1}=f(n+1)$, it follows from the principle of mathematical induction that $T_n=f(n)=2^n-1$ for all positive integers $n$.
Of course this is an excessively careful presentation of the argument; in practice both the calculation and the verbiage can be reduced a bit.
