The Towers of Hanoi is a game played with a set of donut shaped disks stacked on one of three posts. The disks are graduated in size with the largest on the bottom. The object of the game is to transfer all the disks from post B to post A moving one disk at a time without placing a larger disk on top of a smaller one. What is the minimum number of moves required when there are n disks?

In order to visualize the most efficient procedure for winning the game consider the following:

1. Move the first n – 1 disks, per the rules in the most efficient manner possible, from post B to post C.
2. Move the remaining, largest disk from post B to post A.
3. Move the n – 1 disks, per the rules in the most efficient manner possible, from post C to post A.

Let m_n be the number of moves required to transfer n disks per the rules in the most efficient manner possible from one post to another. Step 1 requires moving n – 1 disks or m_n – 1 moves. Step 2 requires 1 move. Step 3 requires m_n – 1 moves again. We have then,

Because only one move is required to win the game with only one disk, the initial condition for this sequence is m₁ = 1. Now we can determine the number of moves required to win the game, in the most efficient manner possible, for any number of disks.

Unfortunately, this recursive method of determining the number of moves required is exhausting if we wanted to solve say a game with 69 disks. We have to calculate each previous term before we can determine the next.

Lets look for a pattern that may be useful in determining an explicit formula for m_n. In looking for patterns it is often useful to forego simplification of terms. m_n = 2m_n – 1 + 1, m₁= 1

So we guess an explicit formula:

m_k = 2^k –1 + 2^k – 2 + … + 2² + 2 + 1.

Recall Theorem 4.2.3 Sum of a Geometric Sequence:
For any real number r except 1, and any integer n ³ 0,