The Tower of Hanoi is a famous problem first posed in 1883 by E. Lucas. There are 3 rods and n disks resting on one rod, sorted in size like a pyramid with the smallest disk on top. Given that you can only move the disks one at a time and that you can never place a bigger disk on a smaller disk, the aim is to move all the disks from the left hand post to the right hand post in the smallest number of moves possible.
Obtaining a Recurrence
Consider n = 0, the simplest case with no discs. As there are no discs to move, we cannot make any moves, so the number of steps required is 0. Letting Sn be the number of moves required for n disks, we get S0 = 0.
Now, we must consider how the problem scales. With n = 1, a single step will solve the problem. With n = 2, the answer is 3 steps: one to move the top (small) disk to another rod, one step to move the big disk to the destination rod, and lastly one step to move the small disk on top of the big disk.
We now consider n discs. We need Sn-1 steps to move all disks except the biggest one, then move the biggest disks then move the sub-tower on top of that disc with Sn-1 steps again. So we have the following upper bound:
What about a lower bound? At some point we must move the biggest disk to the destination rod. To get to the biggest disk, we must have moved all disks on top of it to another rod (the sub-tower), and after having moved the biggest disk, we must move this sub-tower back on top of that rod back onto the biggest disk. Due to these constraints due to the rules of the problem, we know that for n > 0 we must take at least 2*(Sn-1) + 1 steps.
Hence, this recurrence relation gives us the exact number moves needed.
Simplifying the Recurrence
Claim: Sn = 2n – 1 for all natural n.
Proof (by Induction):
Clearly true for n = 0.
Then Sk+1 = 2*(Sk + 1 = 2*(2k – 1) + 1, by the induction hypothesis.
So Sk+1 = 2*2k – 2 + 1 = 2k+1 – 1, as required.
So the claim holds by induction.
So we have found an easy formula for the number of steps needed to solve the Tower of Hanoi problem for any n!