Solving the Tower of Hanoi

Let us assume that $T_n$ be the minimum number of moves to transfer $n$ disks from one rod to another.

So obviously, $T_1=1$ .

In our procedure we first transfer $n-1$ disks from one rod to another (requiring $T_{n-1}$ moves), then we move the largest disk to another rod (requiring $1$ move) and then we finally transfer $n-1$ disks back on the largest disk (requiring another $T_{n-1}$ moves).

$\begin{aligned} \therefore T_n &=2T_{n-1}+1 \quad, \quad n>0 \\ T_2 &= 3 \\ T_3 &= 7 \\ T_4 &= 15 \\ T_5 &= \boxed{31} \end{aligned}$

Generalization

It certainly looks as if $T_n=2^n-1 \quad, \quad n≥0$ .

The induction follows for $n>0$ , $\begin{aligned} T_n &= 2T_{n-1}+1 \\ &= 2(2^{n-1}-1)+1 \\ &=2^n-1 \\ \therefore T_n &=2^n-1 \end{aligned}$