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 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.