Notes on Concrete Mathematics - Chapter 1 Section 1

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
$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.