RtW

26 December 2021

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

1

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

Now suppose that

2

Then, by substitution:

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
Un-1 - 1 2 4 8 16
Un 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

4

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:

5

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,

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.