# Tower of Hanoi - Suggested Solution

An age-old exercise in finding a mathematical pattern.

CA Mathematics Standards Alignment
Algebra and Functions 3.0
Mathematical Reasoning 1.0
Algebra and Functions 1.1
Mathematical Reasoning 1.0
Algebra I 16.0, 25.0

Number of Disks Number of Moves
to Complete Game
1 1
2 3
3 7
4 15
5 31
6 63
7 127
. . . . . .
n 2^n - 1

#### Answer the following questions:

1. Do you see a pattern?

Yes.

2. Explain what you see.

We looked at the number of moves that it took and we noticed that the difference between the numbers was 2 and then 4 and then 8 and then 16 and.....we thought, "Those are all powers of 2."

Use the properties of numbers to construct a simple, valid argument for the above pattern that will lead to a formal equation. State the equation and explain how you found it.

If M equals the minimum number of moves and n equals the number of disks, then M = 2^n -1. We found the equation by looking at the patterns of numbers. We looked at our list of the numbers that were the minimum number of moves and we thought those are the powers of two minus one. The first answer was "two to the power of one, minus 1" and the second answer was "two to the power of two, minus 1." We continued trying our patterning idea and it continued to work. We generalized to "two to the power of n, minus 1."