# Tower of Hanoi

## The Tower of Hanoi is a puzzle whose goal is to move all the disks from one post to another post by only moving one disk at a time and never placing a larger disk on top of a smaller disk. Our department has two of these games to take to the classroom.

## Suppose that only one disk is on a spike. How many moves are required? Count it.

Only 1 move

Only 1 move

## Suppose that two disks are on one spike. How many moves are required? Count them.

Only 3 moves

Only 3 moves

## Suppose that three disks are on one spike. How many moves are required? Prediction?

Only 7 moves

Only 7 moves

## What is the pattern?

## Extend this recursive process until the number of disks reaches 64. You can use the calculator with the following commands:

1 enter |
for the first number of moves |

ANS*2+1 enter |
to get the second number of moves |

enter |
62 times to reach 64 disks to obtain 1.8446744 X 1019 moves |

## This iterative process is said to define a sequence RECURSIVELY. Using the notation a_{1} , a_{2} , a_{3} , … , a_{n} , a_{n+1} , … , we can write the sequence with the formulas:

## The recursive formula can also be written in terms of the number of disks:

## This pattern generalizes to a formula that can be used to find the number of moves needed when using 64 disks. Using sequence notation, the GENERAL TERM FORMULA (also called the nth term) is written as: