Concrete Mathematics: Chapter 1

This series of blog posts is dedicated to the Concrete Mathematics book by Graham, Knuth and Patashnik. I should note that I'm a beginner when it comes to pretty much all of the contents of this book. I have an A level in maths and a passion for the subject, but I'm by no means good. The book is complex, so these blogs will document my struggles working through it.

Fortunately I didn't struggle too much with the first chapter. Therefore these notes are to just jog my memory of what I learnt.

Recurrent Problems: Tower of hanoi

The tower of hanoi puzzle is the first example that the book works through. So for a little bit of extra information, I'll work through the same problem but the pieces have to move through peg B on their way to peg C. This is the same puzzle as is posed by warmup exercise 2.

The original challenge is to move all the pieces from one peg to another to produce the same order but on a different peg (peg C in this case). You can't place a larger piece on top of a smaller piece, and the idea is to solve it in as fewer moves as possible. However in our version we must make sure to move each piece via peg B.

The starting position for the board is as follows:

Because of our new rules, the only legal move we can make right now is to move the top piece of the tower to peg B. Next we have to move the same piece to peg C, in order to get the next piece of the tower on peg B. If we continue on we should eventually reach the end position, which looks as follows:

If we have counted correctly and played optimally, this should have only taken 26 moves for 3 game pieces. Cool. While this is great and all, the purpose of the book is to teach us how to solve recurrent problems. So the real question is, how do we find out the minimum number of turns for $n$ pieces. It's best to start by defining some terms.

$$\begin{aligned} n &= \textrm{Number of pieces} \\ T_n &= \textrm{Number of moves to solve the puzzle} \end{aligned}$$

Now we have some terms we can look at the solutions for a different $n$. The very simplest is $n=0$, here we have no pieces on peg A to move. This means that the puzzle is essentially already solved, and it took 0 turns. Next we can look at $n=1$. With this we are essentially moving along 1 peg each turn until we end up on peg C. So the first move is to peg B, then finally to C. So when $n=1$, $T_n$ is equal to 2. Below is a table showing a few different values for $n$ as well as the corresponding $T_n$.

Eagle eyed people will notice that this is the same as $3^n-1$, crafty people will put the sequence into the on-line encyclopedia of integer sequences (OEIS) and discover the same.

Sadly just noticing the pattern isn't exactly proof that the sequence will continue with our expectations. Instead we need to prove it. This chapter teaches us how to do just that via an induction proof.

An induction proof is where we prove a basis case (the smallest value) such as $n_0=0$, then we prove for values of $n$ which are greater than $n_0$, making sure that the values between $n$ and $n_0$ have also been proved. This is the inductive step. So if $P(0)$ is true and it implies $P(1)$, likewise that $P(1)$ implies $P(2)$. We can assume that $P(n)$ implies $P(n+1)$ and the proof holds true. This is what we'll use later on.

Noticing the recurrence

As this chapter is about recurrent problems, we should find the recurrence in the puzzle. Let's think about the problem when $n$ is 1 and 2. More specifically the end state when $n=1$, and whether or not this state occurs within the puzzle when $n=2$. If you look hard enough you will find that this occurs on the 2nd and 8th move in the $n_2$ puzzle.

Great! But how what about in between? Well, it helps to notice that it wouldn't make a difference if the puzzle was mirrored. This means that it will still take $T_{n-1}$ turns even if the pieces are going in the other direction. An example of this in action is for turns 2 & 3 when $n=2$.

On turn 2 we can see that we have already used $T_{n-1}$ turns, and the next step moves the largest piece to peg B. This adds 1 turn. Now we can think about $T_{n-1}$ but mirrored! So we complete yet another journey back to peg A with $n-1$ pieces, so we can move our largest piece to the finish line, and then the final $T_{n-1}$ to complete the tower.

All in all this turns out to be:

$$\begin{aligned} T_0 &= 0 \\ T_n &= T_{n-1} + 1 + T_{n-1} + 1 + T_{n-1}, \quad \text{for } n > 0. \\ &= 3T_{n-1} + 2 \end{aligned}$$

We can now cancel this down by simply adding 1 to both sides of the equation:

$$\begin{aligned} T_0 + 1 &= 1 \\ T_n + 1 &= 3T_{n-1} + 3, \quad \text{for } n > 0. \\ T_n + 1 &= 3(T_{n-1} + 1) \\ \end{aligned}$$

Let $U_n = T_n + 1:$

$$\begin{aligned} U_0 &= 1\\ U_n &= 3U_{n-1}, \quad \text{for } n > 0. \end{aligned}$$

Now we can see the recurrence as $U_n = 3^n$ (this is more explicit when shown like so, $U_n = 3 \cdot 3^{n-1}$), so it follows that $T_n = 3^n - 1.$ Now all that is left to do is to prove the inductive step. This is done by 'plugging in' the non-recursive into the recursive solution. Thus proving that $n-1$ implies $n$.

$$\begin{aligned} T_n &= 3T_{n-1} + 2 \\ &= 3(3^{n-1} - 1) + 2 \\ &= 3^n - 3 + 2 \\ &= 3^n - 1 \end{aligned}$$

et voila, or should I say Q.E.D.