LearnViz Math
Advanced ⛓ Discrete Math & Number Theory Topic 47 of 103

Tower of Hanoi

Minimum moves for n disks.

Key idea

Minimum moves for n disks.

In depth

Moving n disks needs Tₙ = 2Tₙ₋₁ + 1 moves (move n − 1 away, move the largest, move n − 1 back), so Tₙ = 2ⁿ − 1. It is the classic recursion example.

Worked example

3 disks need 7 moves; 10 disks 1,023; 64 disks about 1.8 × 10¹⁹.

Formula

Tₙ = 2ⁿ − 1

Real-world uses

Common mistake

Not noticing the recursion and trying to move disks one by one without a plan.

How to learn this

  1. Read the key idea and say it in your own words.
  2. Work through the worked example, then try a similar problem.
  3. Use the interactive lesson’s visual and mini-quiz to check the pattern.

Frequently asked questions

What is Tower of Hanoi?

Minimum moves for n disks. It is a topic at the advanced level in Discrete Math & Number Theory.

What is the formula for Tower of Hanoi?

The key formula is Tₙ = 2ⁿ − 1.

Where is Tower of Hanoi used in real life?

Real-world examples: A puzzle for practising recursion and modelling the cost of step-by-step moves in computing.

What should I learn before Tower of Hanoi?

Make sure you are comfortable with Closed Form of Fibonacci (Binet), the previous topic in Discrete Math & Number Theory.

What is a common mistake with Tower of Hanoi?

Not noticing the recursion and trying to move disks one by one without a plan.

How can I practise Tower of Hanoi?

Open the interactive lesson, play with the visual, then answer the three-question mini-quiz. Getting two right marks the topic complete.

What comes after Tower of Hanoi?

Move on to Divide-and-Conquer Recurrences next.

Related advanced topics in Discrete Math & Number Theory