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.
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
Namely, that .
Let . Then
(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
(2) holds for too.
In the next post we will review one more way to solve the recurrence