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

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

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)`

.