21.1: The Towers of Hanoi

There are several methods for solving recurrence equations. The simplest is to guess the solution and then verify that the guess is correct with an induction proof.

For example, as a alternative to the generating function derivation in Section 15.4.2 of the value of the number, \(T_n\), of moves in the Tower of Hanoi problem with \(n\) disks, we could have tried guessing. As a basis for a good guess, let’s look for a pattern in the values of \(T_n\) computed above: 1, 3, 7, 15, 31, 63. A natural guess is \(T_n = 2^n - 1\). But whenever you guess a solution to a recurrence, you should always verify it with a proof, typically by induction. After all, your guess might be wrong. (But why bother to verify in this case? After all, if we’re wrong, its not the end of the... no, let’s check.)

Claim 21.1.1. \(T_n = 2^n - 1\) satisfies the recurrence:

\[\begin{aligned} T_1 &= 1 \\ T_n &= 2T_{n-1} + 1 & (\textit{for } n \geq 2). \end{aligned}\]

Proof. The proof is by induction on \(n\). The induction hypothesis is that \(T_n = 2^n - 1\). This is true for \(n = 1\) because \(T_1 = 1 = 2^1 - 1\). Now assume that \(T_{n-1} = 2^{n-1} - 1\) in order to prove that \(T_n = 2^n - 1\), where \(n \geq 2\):

\[\begin{aligned} T_n &= 2T_{n-1} + 1 \\ &= 2(2^{n-1} -1 ) + 1 \\ &= 2^n - 1. \end{aligned}\]

The first equality is the recurrence equation, the second follows from the induction assumption, and the last step is simplification. \(\quad \blacksquare\)

Such verification proofs are especially tidy because recurrence equations and induction proofs have analogous structures. In particular, the base case relies on the first line of the recurrence, which defines \(T_1\). And the inductive step uses the second line of the recurrence, which defines \(T_n\) as a function of preceding terms.

Our guess is verified. So we can now resolve our remaining questions about the 64-disk puzzle. Since \(T_{64} = 2^{64} - 1\), the monks must complete more than 18 billion billion steps before the world ends. Better study for the final

The Upper Bound Trap

When the solution to a recurrence is complicated, one might try to prove that some simpler expression is an upper bound on the solution. For example, the exact solution to the Towers of Hanoi recurrence is \(T_n = 2^n - 1\). Let’s try to prove the “nicer” upper bound \(T_n \leq 2^n\), proceeding exactly as before.

Proof. (Failed attempt.) The proof is by induction on \(n\). The induction hypothesis is that \(T_n \leq 2^n\). This is true for \(n = 1\) because \(T_1 = 1 \leq 2^1\). Now assume that \(T_{n-1} \leq 2^{n-1}\) in order to prove that \(T_n \leq 2^n\), where \(n \geq 2\):

\[\begin{aligned} T_n &= 2T_{n-1} + 1 \\ &\leq 2(2^{n-1}) + 1 \\ &\nleq 2^n & \color{red}\text{IMPLIES Uh-oh!} \end{aligned}\]

The first equality is the recurrence relation, the second follows from the induction hypothesis, and the third step is a flaming train wreck. \(\quad \blacksquare\)

The proof doesn’t work! As is so often the case with induction proofs, the argument only goes through with a stronger hypothesis. This isn’t to say that upper bounding the solution to a recurrence is hopeless, but this is a situation where induction and recurrences do not mix well.

Plug and Chug

Guess-and-verify is a simple and general way to solve recurrence equations. But there is one big drawback: you have to guess right. That was not hard for the Towers of Hanoi example. But sometimes the solution to a recurrence has a strange form that is quite difficult to guess. Practice helps, of course, but so can some other methods.

Plug-and-chug is another way to solve recurrences. This is also sometimes called “expansion” or “iteration.” As in guess-and-verify, the key step is identifying a pattern. But instead of looking at a sequence of numbers, you have to spot a pattern in a sequence of expressions, which is sometimes easier. The method consists of three steps, which are described below and illustrated with the Towers of Hanoi example.

Step 1: Plug and Chug Until a Pattern Appears

The first step is to expand the recurrence equation by alternately “plugging” (applying the recurrence) and “chugging” (simplifying the result) until a pattern appears. Be careful: too much simplification can make a pattern harder to spot. The rule to remember—indeed, a rule applicable to the whole of college life—is chug in moderation.

\[\begin{aligned} T_n &= 2T_{n-1} + 1 \\ &= 2(2T_{n-2} + 1) + 1 & \text{plug} \\ &= 4T_{n-2} + 2 + 1 & \text{chug} \\ &= 4(2T_{n-3} + 1) + 2 + 1 & \text{plug} \\ &= 8T_{n-3} + 4 + 2 + 1 & \text{chug} \\ &= 8(2T_{n-4} + 1) + 4 + 2 + 1 & \text{plug} \\ &= 16T_{n-4} + 8 + 4 + 2 + 1 & \text{chug} \end{aligned}\]

Above, we started with the recurrence equation. Then we replaced \(T_{n-1}\) with \(2T_{n-2} + 1\), since the recurrence says the two are equivalent. In the third step, we simplified a little—but not too much! After several similar rounds of plugging and chugging, a pattern is apparent. The following formula seems to hold:

\[\begin{aligned}T_n &= 2^k T_{n-k} + 2^{k-1} + 2^{k-2} + \cdots + 2^2 + 2^1 + 2^0 \\ &= 2^k T_{n-k} + 2^k - 1 \end{aligned}\]

Once the pattern is clear, simplifying is safe and convenient. In particular, we’ve collapsed the geometric sum to a closed form on the second line.

Step 2: Verify the Pattern

The next step is to verify the general formula with one more round of plug-andchug.

\[\begin{aligned}T_n &= 2^k T_{n-k} + 2^{k} - 1 \\ &= 2^k(2T_{n-(k+1)} + 1) + 2^k - 1 & \text{plug} \\ &= 2^{k+1} T_{n-(k+1)} + 2^{k+1} - 1 & \text{chug} \end{aligned}\]

The final expression on the right is the same as the expression on the first line, except that \(k\) is replaced by \(k + 1\). Surprisingly, this effectively proves that the formula is correct for all \(k\). Here is why: we know the formula holds for \(k = 1\), because that’s the original recurrence equation. And we’ve just shown that if the formula holds for some \(k \geq 1\), then it also holds for \(k + 1\). So the formula holds for all \(k \geq 1\) by induction.

Step 3: Write \(T_n\) Using Early Terms with Known Values

The last step is to express \(T_n\) as a function of early terms whose values are known. Here, choosing \(k = n - 1\) expresses \(T_n\) in terms of \(T_1\), which is equal to 1. Simplifying gives a closed-form expression for \(T_n\):

\[\begin{aligned}T_n &= 2^{n-1} T_1 + 2^{n-1} - 1 \\ &= 2^{n-1} \cdot 1 + 2^{n-1} - 1 \\ &= 2^n - 1. \end{aligned}\]

We’re done! This is the same answer we got from guess-and-verify.

Let’s compare guess-and-verify with plug-and-chug. In the guess-and-verify method, we computed several terms at the beginning of the sequence, \(T_1, T_2, T_3,\) etc., until a pattern appeared. We generalized to a formula for the \(n\)th term, \(T_n\). In contrast, plug-and-chug works backward from the \(n\)th term. Specifically, we started with an expression for \(T_n\) involving the preceding term, \(T_{n-1}\), and rewrote this using progressively earlier terms, \(T_{n-2}\), \(T_{n-3}\), etc. Eventually, we noticed a pattern, which allowed us to express \(T_n\) using the very first term, \(T_1\), whose value we knew. Substituting this value gave a closed-form expression for \(T_n\). So guess-and-verify and plug-and-chug tackle the problem from opposite directions.