The Tower of Hanoi: The Closed Form Proof

After delving into an informal introduction to mathematical induction, let's take a look at the proof for the Tower of Hanoi closed-form solution. We are going to explore the proof in more detail than it is done in Concrete Mathematics.

By experimenting with the Tower of Hanoi puzzle, we found the recurrence relation that allows us to compute in how many moves the puzzle can be solved for an arbitrary number of disks:

$\begin{equation*} \flushleft T_0 = 0 \ ; \\ T_n = 2T_{n-1} + 1 \ , \qquad \text{for } n > 0 \ . \end{equation*}$ 1

Now we want to prove that the closed-form solution for this recurrence relation is:

$\begin{equation*} T_n = 2^n - 1 \ , \qquad \text{for } n \ge 0 \ . \end{equation*}$ 2

For this we use the method of mathematical induction.

Proof

Base case. At first, we show that the closed form holds for the boundary value; that it computes the same value as the boundary equation from (1). Namely, that $T_n = 0 \ , \text{ for } n = 0$ .

Let $n = 0$ . Then

$\begin{align*} T_0 &= 2^0 - 1 \qquad \textit{\small by substitution} \\ &= 1 - 1 \phantom{1} \qquad \textit{\small by the laws of algebra} \\ &= 0 \ . \end{align*}$

Hence (2) holds for $n = 0$ .

Inductive step. In this step we show that for any positive integer $k$ , if (2) holds for $n = k$ , then it also holds for $n = k + 1$ .

We introduce an inductive hypothesis, by supposing that

$\begin{equation*} T_{k} = 2^k - 1 \ . \end{equation*}$

Now we must show that

$\begin{equation*} T_{k+1} = 2^{k+1} - 1 \ . \end{equation*}$

Indeed,

$\begin{align*} T_{k+1} &= 2T_{(k+1)-1} + 1 \phantom{1} \qquad \textit{\small by the recurrence relation} \\ &= 2T_k + 1 \\ &= 2 (2^k - 1) + 1 \qquad \textit{\small by the inductive hypothesis} \\ &= 2^{k+1} - 2 + 1 \\ &= 2^{k+1} - 1 \ . \end{align*}$

Hence (2) holds for $n > 0$ too.

In the next post we will review one more way to solve the recurrence (2).