2
$\begingroup$

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?

  • 0
    @yoonsi I'm glad you got what you wanted.2012-08-29

1 Answers 1

2

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.