Example 2.4.1 The Tower of Hanoi Problem: Suppose there are $n$ disks stacked on column $A$ in ascending order of size, with the largest at the bottom and the smallest at the top, as shown in Figure 2-7. Now, we need to move all the disks from column $A$ to column $C$, with the constraint that only one disk can be moved at a time and a larger disk cannot be placed on top of a smaller one. Assuming there are three columns $A, B, C$ available for use, how many moves are required to transfer all $n$ disks from column $A$ to column $C$?
Let $f_{n}$ be the number of moves required to transfer $n$ disks. We can consider first transferring the top $n-1$ disks to the $B$ peg via the $C$ peg, which requires $f_{n-1}$ moves, then moving the largest disk from the $A$ peg to the $C$ peg, which requires 1 move, and finally transferring the $n-1$ disks from the $B$ peg to the $C$ peg via the $A$ peg, which also requires $f_{n-1}$ moves. Thus, we have
$$
\left\{\begin{array}{l}
f_{n}=2 f_{n-1}+1, \\
f_{1}=1 .
\end{array}\right.
$$

To solve the above recurrence relation, we can proceed by successive substitution:
$$
\begin{aligned}
f_{n} & =2 f_{n-1}+1 \\
& =2\left(2 f_{n-2}+1\right)+1 \\
& =2^{2} f_{n-2}+2+1 \\
& =2^{3} f_{n-3}+2^{2}+2+1=\cdots \\
& =2^{n-1} f_{1}+2^{n-2}+2^{n-3}+\cdots+2+1 \\
& =2^{n}-1 .
\end{aligned}
$$

Alternatively, we can solve it as follows: $f_{n}+1=2\left(f_{n-1}+1\right)=2^{2}\left(f_{n-2}+1\right)=\cdots=$ $2^{n-1}\left(f_{1}+1\right)=2^{n}, f_{n}=2^{n}-1$.