The Tower of Hanoi: Solving A Recurrence

Concrete Mathematics presents two alternate solutions for the Tower of Hanoi recurrence relation. We reviewed one of them in the previous post. This post explores the second approach.

Here's the recurrence relation we're discussing:

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

Observe the results of adding 1 to both sides of the equations:

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

Now suppose that

$\begin{equation*} U_n = T_n + 1 \ . \end{equation*}$ 2

Then, by substitution:

$\begin{equation*} \flushleft U_0 = 1 \ ; \\ U_n = 2U_{n-1} \ , \qquad \text{for } n > 0 \ . \end{equation*}$ 3

Following the usual steps of the recurrence analysis, we write down the values for the small cases:

n	0	1	2	3	4	5
U_n-1	-	1	2	4	8	16
U_n	1	2	4	8	16	32

Based on the data in the table, we may 🤞 guess that the closed-form expression for the recurrence relation (3) is

$\begin{equation*} U_n = 2^n \ , \qquad \text{for } n \ge 0 \ . \end{equation*}$ 4

And now, for fun and practice, we will prove that (4) holds using the method of mathematical induction.

Proof

Base case. Let $n = 0$ . Then

$\begin{equation*} U_0 = 2^0 = 1 \ , \end{equation*}$

which equals the recurrence relation (3).

Inductive step. We suppose that (4) holds for $n = k$ , where $k$ is any positive integer. Namely, that:

$\begin{equation*} U_k = 2^k \ . \end{equation*}$ 5

Now we must show that the hypothesis (5) is also correct for $n = k + 1$ . That is:

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

Now

$\begin{align*} U_{k+1} &= 2U_{(k+1)-1} \qquad \textit{\small by (3)} \\ &= 2U_k \\ &= 2 \times 2^k \qquad \qquad \textit{\small by (5)} \\ &= 2^{k+1} \ . \end{align*}$

Hence, we showed that (4) holds for $n \ge 0$ .

It follows from (4) and (2), that

$\begin{equation*} T_n + 1 = 2^n \end{equation*}$

and, by subtracting 1 from the both sides of the equation,

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

Therefore, we have just confirmed once more that (6) is the closed-form expression for the Tower of Hanoi recurrence relation (1).

And now we're ready to move on to the next chapter, Lines in the Plane.