---
tag: 0906Z03EMN
kind: example
name: Tower of Hanoi
msc: [00A08]
instance_of: [0FYX44GP92]
sources:
  - url: https://en.wikipedia.org/wiki/Tower_of_Hanoi
    locator: Recursive solution
same_as:
  wikidata: Q213593
  wikipedia: Tower of Hanoi
---

## Example

The Tower of Hanoi is a puzzle with three rods and $n$ discs of different sizes.
At the start, all discs are on one rod, in order of size, with the largest at the bottom.
A move takes the top disc of one rod and puts it on top of another rod.
No move may put a disc on a smaller disc.
The aim is to move all discs to another rod.

Let $T_n$ be the minimum number of moves for $n$ discs.
Then $T_0 = 0$ and $T_n = 2 T_{n-1} + 1$ for $n \ge 1$.
This [[recurrence relation|07TZV87Y0T]] has the solution $T_n = 2^n - 1$.

## Remarks

The recurrence comes from the largest disc. Before it moves, the other $n - 1$ discs must be on the third rod. After it moves, they must come back on top of it.
Values: $T_1 = 1$, $T_2 = 3$, $T_3 = 7$ and $T_4 = 15$.
The French mathematician Édouard Lucas invented the puzzle and presented it in 1883.

## Explanations

### L1 human

To move a tower of $n$ discs, first move the top $n - 1$ discs out of the way. Then move the largest disc, and then move the $n - 1$ discs back on top.
Each new disc doubles the work and adds one move.