Towers of Hanoi

Recurrence. To move $n$ disks: move $n-1$ to auxiliary peg ($T_{n-1}$ moves), move the largest to the target (1 move), move $n-1$ onto it ($T_{n-1}$ moves). So $T_n=2T_{n-1}+1$.

Base case. $T_0=0$.

Solve. $T_n=2^n-1$ by induction.

Conclusion. The minimum number of moves is $2^n-1$.