Patterns in Numbers

Tower of Hanoi

This game comes from an ancient myth about monks moving 64 gold disks from one room to another in their temple. Use the following rules to play the game, beginning with ONE disk on the left-hand spot. Record the minimal number of required moves on the table below. Play again with two disks, then three, and so on. Find a formula to predict how many moves will n disks take. Finally, find out how long will it take the priests to move 64 disks.

RULES:

1. Only move ONE disk at a time from the TOP of a pile.
2. A larger disk may never be placed on top of a smaller disk.

3. If more than one disk are in the same space, they must be stacked.
4. You may move a disk to any empty spot or on top of any larger disk (yes, you may skip over an empty spot).


# of disks in tower
# of minimal moves to reconstruct tower
pattern
1
          
     
2
     
     
3
     
     
4
     
     
5
     
     
:
:
:
:
:
:
n