In this article I will gather the solutions I was able to find to the exercises in the book "Concrete Mathematics" By Graham, Knuth and Patashnik. That may be a very short article, but I'll be proud of any single one I've found. I know that the solutions are given at the end of the book, however these ones are "brief" as the authors themselves admit. I'll go more in details here, hopefully it will be helpful to someone. Finally I'll update this article little by little, at a probably extremely slow pace.
Ex. 1.2
\(T_n\) is the minimum number of steps to move a stack of \(n\) disks from A to C (or backward from C to A).
By hand: \(T_0=0\), \(T_1=2\), \(T_2=8\).
A solution is to move the \(n\)-th disk (disks indexed from smaller to larger), move the \(n-1\) disks from A to B to C, then move the \(n\)-th disk to B, then move the \(n-1\) disks from C to B to A, then move the \(n\)-th disk to C, then move the \(n-1\) disks from A to B to C. Then, \(T_n\le 3T_{n-1}+2\).
Also, to move the \(n\)-th disk (largest one) from A, one must move the \(n-1\) disks above it. The largest disk needs to move to B first, and as it is the largest, B needs to be empty to receive it. Hence there is no other option than moving first the \(n-1\) smaller disks from A to C to be able to move the largest one from A to B. This takes at least \(T_{n-1}+1\) steps. Once the largest is on B, to move it to C we need C (where the smaller ones currently are) to be empty and no disks above the largest on B. The only option is to move the \(n-1\) smaller disks from C to A and then move the larger disk to C. This takes also at least \(T_{n-1}+1\) steps. Finally, the largest disk is on C, and the other disks are on A. Moving the smaller disks from A to C takes at least \(T_{n-1}\) steps. Then, \(T_n\ge 3T_{n-1}+2\).
Hence, \(T_n=3T_{n-1}+2\).
$$
\begin{array}{l}
U_n=T_n+1\\
U_n-1=3(U_{n-1}-1)+2\\
U_n=3U_{n-1}-3+2+1\\
U_n=3U_{n-1}\\
T_0=0\implies U_0=1\implies U_n=3^n\\
T_n=3^n-1\\
\end{array}
$$
Ex. 1.3
One disk can be on one of three pegs at a given step. Then there are \(3^n\) possible states.
Moving the stack from A to C requires \(3^n-1\) moves. Hence it goes through 1 initial state plus \(3^n-1\) other states (the states after each move). The total number of states visited is then equal to \(3^n\).
All visited states are different: if states at step \(i\) and \(j>i\) are identicals then the solution going through states \(0,...,i,(j+1),(3^n-1)\) is valid and shorter than \(3^n-1\) states, which contradicts the result of ex. 1.2. Hence there can't be two identical states in the \(3^n-1\) steps solution.
The solution visits \(N\) different states within \(N\) possible states, hence it visits all possible states.