# 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:

Observe the results of adding `1`

to both sides of the equations:

Now suppose that

Then, by substitution:

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

And now, for fun and practice, we will prove that `(4)`

holds using the method of
mathematical induction.

#### Proof

**Base case**. Let . Then

which equals the *recurrence relation* `(3)`

.

**Inductive step**. We suppose that `(4)`

holds for , where
is any positive integer. Namely, that:

Now we must show that the hypothesis `(5)`

is also correct for . That is:

Now

Hence, we showed that `(4)`

holds for .

It follows from `(4)`

and `(2)`

, that

and, by subtracting `1`

from the both sides of the equation,

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.