Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1  
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

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.