So let us begin with a rather simple problem: The Tower of Hanoi.
In this section, the author stresses on the nontrivial inequality:
$$T_n{\geq}2T_{n-1}+1, \text{for }n>0$$,
which indicates that the solution is optimal. Here a sketch will be of great help if you did not get the point.
After we got the recurrence $$T_n{\geq}2T_{n-1}+1$$, it is time to solve it.
Actually, If we add both sides with 1, it yields
$$T_n+1=2(T_{n-1}+1).$$
Obviously $${T_n+1}$$ is a geometric sequence.
Thus $$T_n=2^n-1$$
In the Exercises section, we have some non-intuitive problems, for example, Warmup 2 and 3.
The Warmup 2 and 3 further added a limitation to the original problem:No direct moves are allowed.
After a while of thinking, it became clear that we need to move a tower of n-1 and a disk(the largest one) once more(This rule just made the middle step more complex).
Thus $$T_n=3T_{n-1}+2,$$
which yields $$T_n=3^n-1$$
But that's not the best part - Warmup 3 now asked you to prove the nontrivial fact that in the preceding process, every possible legal permutation of the disks will be encountered!
How could I do this?
It can be almost immediately noticed that in all $$T_n=3^n-1$$ steps, the arrangement of disks will never repeat. Thus we only have to calculate the total number of permutations.
There are 3 pegs with n disks. On each peg, the disks are sorted in the order of size.
Here I made a big mistake: I tried to compute the enormous sum $$P_n=\sum_{i+j{\leq}n}C_n^iC_{n-i}^j$$But actually any disk can be on one of the three pegs, so the result is obviously $$N=3^n$$In the preceding process, we encountered $$N_0=T_n+1\=3^n$$ states.QED.