RtW

16 December 2021

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

Now we want to prove that the closed-form solution for this recurrence relation is: 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 .

Let . Then Hence (2) holds for .

Inductive step. In this step we show that for any positive integer , if (2) holds for , then it also holds for .

We introduce an inductive hypothesis, by supposing that Now we must show that Indeed, Hence (2) holds for too.

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

Created by Y.E.T.If you see an error, please report it.