Drexel dragonThe Math ForumDonate to the Math Forum

Stations 1 and 2

Tower of Hanoi - Suggested Solution

An age-old exercise in finding a mathematical pattern.


Table of Contents

CA Mathematics Standards Alignment
  • 6th grade
        Algebra and Functions 3.0
        Mathematical Reasoning 1.0
  • 7th grade
        Algebra and Functions 1.1
        Mathematical Reasoning 1.0
  • 8th grade
        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."

Links to more information:

Tower of Hanoi - Ask Dr. Math FAQ

Tower of Hanoi - Cut-the-Knot by Alexander Bogomolny.

[Privacy Policy] [Terms of Use]

_____________________________________
Home || The Math Library || Quick Reference || Search || Help 
_____________________________________

© 1994-2014 Drexel University. All rights reserved.
http://mathforum.org/
The Math Forum is a research and educational enterprise of the Drexel University School of Education.The Math Forum is a research and educational enterprise of the Drexel University School of Education.
Send comments to: Suzanne Alejandre