I decided to spend some time to read Concrete Mathematics. So I'll put some notes here, just to keep a memo and share my thoughts with you.

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


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.