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