The moves of the Tower of Hanoi

Text

In the Tower of Hanoi game you move $n$ discs of different sizes among three pegs, one disc at a time, never placing a larger disc on a smaller one. The minimum number of moves satisfies the recursion $M_n = 2M_{n-1}+1$ with $M_1=1$. How many moves are needed for $n=12$ discs?

Solution

To move $n$ discs you first move the top $n-1$ onto a spare peg, then the largest disc, then again the $n-1$: hence $M_n=2M_{n-1}+1$. The solution of the recursion is $M_n = 2^n - 1.$ For $n=12$: $M_{12} = 2^{12} - 1 = 4096 - 1 = \boxed{4095}.$