KnowledgeMadeFun, home

Lesson · Grade 11 · Foundations of Mathematics

Tower of Hanoi: From Pattern to Proof

  • Grade 11
  • Foundations of Mathematics
  • 1 min 59 s
  • British Columbia
  • BC11-MA-105

Playing the Tower of Hanoi with 1, 2, 3 and 4 discs gives 1, 3, 7 and 15 moves, which leads to the conjecture that n discs take 2ⁿ − 1 moves (inductive reasoning), with a warning that a pattern alone is not a proof. Breaking the 4-disc solution into 7 + 1 + 7 moves gives the rule M(n) = 2 × M(n − 1) + 1, which proves the formula for every n (deductive reasoning) and shows that 64 discs would take about 585 billion years.

Concept: Puzzle analysis: the Tower of Hanoi

Anyone can watch two lessons on the website without an account. Signing in is free, no payment and no card, and opens three a day; Plus has no limit.

Loading

Share to Google Classroom

In one sentence

The question this lesson answers

In the Tower of Hanoi, you move a stack of discs to another peg.

Move one disc at a time, and never put a larger disc on a smaller one.

Transcript

What the lesson says

In the Tower of Hanoi, you move a stack of discs to another peg.

Move one disc at a time, and never put a larger disc on a smaller one.

What is the fewest number of moves for n discs? Call it M of n.

Play it out. One disc takes 1 move.

Two discs: small aside, large across, small on top. That is 3 moves.

Three discs take 7 moves, and four discs take 15.

Add 1 to each answer: 2, 4, 8, 16. These are powers of 2.

So we conjecture, or guess without proof, that M of n is 2 to the power n, minus 1.

Going from examples to a general rule is called inductive reasoning.

The common mistake is to stop here: a pattern can work for a few cases, then fail.

Deductive reasoning goes from known facts to a conclusion that must be true.

The largest disc can only move once the 3 discs above it sit on the spare peg: 7 moves.

Then the largest disc moves, and the 3 discs go back on top: 2 times 7, plus 1, is 15.

For any n: M of n is 2 times M of n minus 1, plus 1.

Put the conjecture into this rule and it fits. M of 1 is 1 too, so the formula is proved for every n.

64 discs take 2 to the power 64, minus 1 moves: at one move a second, about 585 billion years.

Inductive reasoning found 2 to the power n, minus 1. Deductive reasoning proved it.

Curriculum

Where this fits

British Columbia, Grade 11

Foundations of Mathematics 11, Logic and reasoning: forms of mathematical reasoningBC11-MA-105

Previous: Deductive Reasoning: Proving Odd + Odd Is Always Even

The outcomes and strands follow the British Columbia curriculum.

Keep going

More on this topic