The Tower of Hanoi: Recursion and 2ⁿ − 1

To move a tower of n disks, move the top n − 1 out of the way, move the biggest disk, then move the n − 1 back on top. That plan gives the recurrence H(n) = 2H(n − 1) + 1, and its solution, 2ⁿ − 1, explains why the legendary 64-disk tower would take hundreds of billions of years.

How it works

Recurrence relations and induction

In one sentence

The recurrence $H_n = 2H_{n-1} + 1$ with $H_1 = 1$ has the closed form $H_n = 2^n - 1$ , by induction. No solution uses fewer moves, because the largest disk must move at least once, with the other $n - 1$ disks stacked elsewhere both before and after.

General formula

{\htmlData{sym=0}{H_n}} = 2H_{{\htmlData{sym=1}{n}}-1} + 1,\;\; H_1 = 1 \quad\Longrightarrow\quad {\htmlData{sym=0}{H_n}} = 2^{\htmlData{sym=1}{n}} - 1

Each extra disk means solving the whole smaller puzzle twice. Doubling at every step is exponential growth.

What the symbols mean

$H_n$
Moves needed
The fewest moves that transfer a tower of n disks.
$n$
Disks
How many disks the tower has.

To move $n$ disks from the left peg to the right, the biggest disk must move at some point, and at that moment the other $n - 1$ disks must all sit on the middle peg.
So the best plan moves $n - 1$ disks to the middle ( $H_{n-1}$ moves), the biggest disk across (1 move), and the $n - 1$ disks back on top of it ( $H_{n-1}$ moves): $H_n = 2H_{n-1} + 1$ .
The values $1, 3, 7, 15, 31$ suggest $H_n = 2^n - 1$ , and induction proves it: $2(2^{n-1} - 1) + 1 = 2^n - 1$ .
The smallest disk moves on every other turn, always in the same direction around the pegs, which gives a simple rule a person or a computer can follow without thinking about recursion.

Learn the math

Mathematical InductionDiscrete · Lesson 8, Proofs Recurrence RelationsDiscrete · Lesson 21, Sequences and Recurrences