Go up to The Tower of Hanoi
Go forward to Discovering the Mathematics, Continued
Switch to graphical version (better pictures & formulas)

### Discovering the Mathematics Behind the Game

If you've played the game as well as possible, you should have discovered that the minimum number of turns it takes to win (for 1, 2, 3, and 4 disks, respectively) are 1, 3, 7, and 15.

Looking for the Pattern. To figure out how many turns it'll take for more than four disks, and to figure out how long it'll take the monks to finish their task, you need to find a pattern relating the number of disks to the minimum number of turns it takes to win the game. Write down the minimum number of turns it takes for one, two, three, and four disks. Can you conjecture a pattern? (Hint: try adding one to each of the numbers; do you recognize a pattern now?)

Justifying the Pattern. It's great that you've found a pattern. But maybe the pattern is just a coincidence, and doesn't continue for larger numbers of disks. To see if it does, we need a more systematic, mathematical approach. We will proceed by induction: if we know how many turns it takes to win the n-disk game, we'll try to use that to find how many turns it takes to win the (n+1)-disk game. Having done that, we'll be able to find the number of turns for any n.

So, suppose we know that it takes M turns to move a pile of n disks from one post to another. How many turns will it take to move n+1 disks?

Think of it this way: imagine you can move the top n disks as a single unit. Now, what's the quickest way to move all n+1 disks? Your answer should involve a certain number of moves of the top n disks (as a single unit), and a certain number of moves of the bottom disk (by itself).

Now, although this is illegal (you can't move the top n disks as a unit), you can achieve the same effect in M legal moves, because we know that it takes M turns to move a pile of n disks from one post to another.

Therefore, you now have a procedure for legally moving all n+1 disks to their new home: follow the procedure you devised before, but instead of moving the top n disks as a unit, use the M legal moves required to achieve the same effect. How many turns does this procedure take?

The answer is in the next section, but don't go there until you've tried to work it out for yourself.