(Hanoi Tower) There are $3$ identical rods labeled as $A$, $B$, $C$; and $n$ disks of different sizes which can be slide onto any of these three rods. Initially, the $n$ disks are stacked in ascending order of their sizes on $A$. What is the minimal number of moves in order to transfer all the disks to $B$ providing that each move can only transfer one disk to another rod's topmost position and at no time, a bigger disk can be placed on top of a smaller one.
Let $m_n$ be the required number of moves. Then, it will need a minimal of $m_{n-1}$ moves to transfer the top $(n-1)$ disks from one rod to another. It follows that
- Transferring top $(n-1)$ disks from $A$ to $C$ requires a minimal of $m_{n-1}$ moves.
- Transferring the biggest disk from $A$ to $B$ requires 1 move.
- Transferring all the $(n-1)$ disks from $C$ to $B$ requires a minimal of $m_{n-1}$ moves.
Hence, we have $$m_n= m_{n-1} + 1 + m_{n-1} = 2m_{n-1}+1$$
with the initial condition $m_1=1$. There are several ways to solve this recursion. One is to transform the relation above to $$(m_n+1)=2(m_{n-1}+1)$$
Then the sequence $\{m_n+1\}$ is a geometric with initial value of $2$ and common ratio $2$. Hence $$m_n+1=2^n\implies m_n=\boxed{2^n-1}$$