# How to complete this proof regarding closed form of tower of hanoi problem? [duplicate]

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?

-

## marked as duplicate by MJD, Zhen Lin, sdcvvc, Eric NaslundAug 29 '12 at 3:50

distribute the 2 and add – mathmath8128 Aug 29 '12 at 2:18
@platinumtucan I keep ending up with $4^{n} - 1$ : ( EDIT: Wait... $2 * (2^{n-1})$ this gives you just.. $2^{n}$ is that right? – yoonsi Aug 29 '12 at 2:22
Here's another close match: Form or asymptotic behaviour of $T(n) =2T(n-1)+n$ – MJD Aug 29 '12 at 2:56
And another: question about solving recurrences – MJD Aug 29 '12 at 2:58
And here's the one it was closed in favor of: Solving a Recurrence Relation/Equation, is there more than 1 way to solve this? – MJD Aug 29 '12 at 3:00

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.

-