Concrete Mathematics (by Graham, Knuth, Patashnik), Ex. 1.2

https://liron.tilde.team

December 14, 2025

I had a lot of trouble with the “warmup” exercise 1.2, which is why I share my very detailed solution here. Maybe someone has a use for it.

We are facing the towers of hanoi problem again, but this time we cannot move discs directly from A to B. We must go over C everytime. That means for the case T_{1}, we have two moves: A → C → B. For the case T_{2}, we basically need to

1. move the small disc to B first (2 moves)

2. then move the large disc to C (1 moves)

3. get the small disc out of the way, i.e. move it back to A (2 moves)

4. move the large disc from C to B (1 move)

5. Move the small disc to B (2 moves)

So we get T_{2} = 8. For the case T_{3}, we need to do a lot more moves. Because of this, I will refer to the three plates by greek letters: α is the smallest, β the middle-sized one and γ will denominate the largest of the three plates. The start setup is:

\begin{matrix}α \\ β \\ γ \end{matrix}

The sequence of moves is:

\begin{matrix}α \\ β \\ γ \end{matrix}  → \begin{matrix}β \\ γ & α \end{matrix} → \underline{γ β α} → \begin{matrix}α \\ γ & β \end{matrix}  → \begin{matrix}α \\ γ & β \end{matrix} →

\begin{aligned}& α \\ γ & β \end{aligned} →  \begin{aligned}& α \\ γ & β \end{aligned} → \underline{α γ β} → \begin{aligned}& β \\ α & γ \end{aligned}  →  \begin{matrix}β \\ γ & α \end{matrix} →

\underline{β γ α} → \begin{matrix}α \\ β & γ \end{matrix}  → \begin{matrix}α \\ β & γ \end{matrix} → \begin{aligned}& α \\ β & γ \end{aligned} →  \begin{aligned}& α \\ β & γ \end{aligned} →

\underline{α β γ} → \begin{aligned}& β \\ α & γ \end{aligned} → \begin{matrix}α \\ β \\ γ \end{matrix}

Please note: For the sake of brevity, I did not include moving α from position A to C and then to B. I collapsed these two steps into one in the figure. If you look at these moves closely, a pattern emerges. Every other step we need to move α out of the way. This was the same for T_{2}, but because T_{2} = 5, it was not evident at the beginning. Furthermore, after we moved γ to position B, α and β are positioned at A, like in the beginning of the case T_{2}. All the moves that follow are the same as for this case.

If we now want to calculate the number of moves for T_{3}, we can group the steps where α was moved, and the other steps. We find 9 times where α as moved and 8 times where β or γ where moved. This gets us T_{3} = 9 ∗ 2 + 8 ∗ 1 = 26.

Further explanation: As I described above, I collapsed the two α moves in the figure each time into one step, for the sake of brevity. However, α is always being moved from A to B. α never stays at C. That means, whenever α is moved, we count two moves. β and γ are always moved only one step, before α is being moved again.

Now we now that we are looking for a recurrence to calculate arbitrary T_{n}. We can take into account that the last 5 steps are the same as for T_{2}. This leaves us with T_{3} = T_{2} + 6 · 2 + 6 · 1 = 26. Simplifying this equation, we get T_{3} = T_{2} + 6 · (2 + 1) = T_{2} + 6 · 3. We know that T_{2} = 8 and T_{1} = 2, or T_{2} = T_{1} + 6. If we count the required moves for T_{4} (I will not include a similar figure due to me being lazy, but feel free to construct it for yourself for understanding), we find T_{4} = 80. All together:

T_{1} = 2
T_{2} = T_{1} + 6
T_{3} = T_{2} + 18
T_{4} = T_{3} + 54

There seems to be a pattern hidden here, as 6, 18 and 54 are divisible by 6, or 3, respectively. We can see that:

T_{1} = 2
T_{2} = 8 = 3 · T_{1} + 2
T_{3} = 26 = 3 · T_{2} + 2
T_{4} = 80 = 3 · T_{3} + 2
...
T_{n} = 3 · T_{n−1} + 2

Use this recursion, we can now calculate the results for larger n:

\begin{matrix}T_{0} & T_{1} & T_{2} & T_{3} & T_{4} & T_{5} & T_{6} \\ 0 & 2 & 8 & 26 & 80 & 242 & 728 \end{matrix}

Now we are looking for a closed form instead of the recursion. Trying random things with the calculator^{1} shows that:

\begin{matrix}n^{0} & n^{1} & n^{2} & n^{3} & n^{4} & n^{5} & n^{6} \\ 1 & 3 & 9 & 27 & 81 & 243 & 729 \end{matrix}

So we can assume that T_{n} = 3^{n} −1. Using induction, we can prove this, by swapping in our assumption for T_{n−1} in the recursive formular:

T_{n} = 3 · (T_{n−1}) + 2 = 3 · (3^{n−1} − 1) + 2 = 3^{n} − 3 + 2 = 3^{n} − 1

Which is the same result as in the book. The problem is therefore solved.

1Yes, really.