Mathematics 11–12 · Year 12

Tower of Hanoi: 2^n - 1 moves, from pattern to proof by induction

Proof by mathematical induction (Mathematics Extension 1, Year 12); Sequences and series: Geometric sequences and series (Mathematics Advanced, Year 12)

Practical, model not builtLow risk

This site has no interactive model of its own. Where a step or a material names a Concept Studio model, simulation or tool, it has not been built; an external simulation a step names (for example PhET) is not part of this site.

The idea

Counting the fewest moves for one, two, three and four discs suggests 2^n - 1; counting how often each disc moves turns the total into the sum 1 + 2 + ... + 2^(n-1), and mathematical induction proves that this sum equals 2^n - 1 for every n.

What you need

A Tower of Hanoi set with 6 to 8 discs (or 8 coins of different sizes and three marked spots)
A recording sheet

How to do it

Move 1, then 2, then 3, then 4 discs from the first peg to another with the fewest moves, one disc at a time and never a larger disc on a smaller one.
Tabulate n against the number of moves and conjecture a formula.
Argue the recursion as motivation: to move n discs, move n - 1 discs aside, move the largest, then move the n - 1 discs back on top, so M(n) = 2 M(n - 1) + 1 and each disc moves twice as often as the next larger disc.
Count how often each disc moves in the optimal solution (the smallest moves 2^(n-1) times, the largest once), so the fewest moves is the sum 1 + 2 + ... + 2^(n-1).
Prove 1 + 2 + ... + 2^(n-1) = 2^n - 1 for every positive integer n by mathematical induction: base case n = 1, then add the next term 2^k to both sides of the case n = k; check the result with the geometric series formula.
Compute the moves for 64 discs and the time at one move per second.

What you should see

The fewest moves are 1, 3, 7, 15, 31, 63, 127 and 255 for 1 to 8 discs. Base case: 1 = 2^1 - 1. Inductive step: if 1 + 2 + ... + 2^(k-1) = 2^k - 1, then adding 2^k gives 2^k - 1 + 2^k = 2^(k+1) - 1. The recursion M(n) = 2 M(n - 1) + 1 explains why the counts double; the proof the syllabus asks for is the induction on the sum. For 64 discs 2^64 - 1 = 18 446 744 073 709 551 615 moves, about 585 billion years at one move per second. The learner knows it worked when a 5-disc solution takes exactly 31 moves and any shorter attempt breaks a rule.

What changes

What you change: number of discs n
What you measure: fewest moves
What you keep the same: the two rules
moves counted by a partner

Common misconceptions

Each of these ideas is wrong, and the activity is a chance to test it.

Checking the formula for n = 1 to 8 proves it; only the inductive step covers every n.
Doubling the number of discs doubles the moves; adding one disc roughly doubles the moves.

Safety card

Low riskLearners carry it out

Hazards

No hazard is listed.

Controls

No control is listed.

Note

No chemicals and no heat are used, so the NSW Department of Education Chemical Safety in Schools package does not apply; ordinary classroom supervision.

Curriculum references

The NSW syllabus outcomes and Australian Curriculum v9 codes this activity supports. They are references, not a verified or complete curriculum alignment.

Mathematics Extension 1 11–12 Syllabus (2024), Year 12 focus area Proof by mathematical induction; Year 11 taught from Term 1 2026, Year 12 from Term 4 2026, first HSC examination 2027 (the 2017 syllabus is still taught to Year 12 until then); page read 2026-09-22ME1-12-01
Mathematics Advanced 11–12 Syllabus (2024), Year 12 focus area Sequences and series; Year 11 taught from Term 1 2026, Year 12 from Term 4 2026, first HSC examination 2027 (the 2017 syllabus is still taught to Year 12 until then); page read 2026-09-22MAV-12-03
Australian Curriculum v9No Australian Curriculum v9 code is listed.

Sources

The pages the author read to write this activity.

All Concept Studio activities