Mathematics for Computer Science

21.1. The Towers of Hanoi 869

to remember—indeed, a rule applicable to the whole of college life—ischug in
moderation.

TnD2Tn 1 C 1

D2.2Tn 2 C1/C 1 plug

D4Tn 2 C 2 C 1 chug

D4.2Tn 3 C1/C 2 C 1 plug

D8Tn 3 C 4 C 2 C 1 chug

D8.2Tn 4 C1/C 4 C 2 C 1 plug

D16Tn 4 C 8 C 4 C 2 C 1 chug

Above, we started with the recurrence equation. Then we replacedTn 1 with
2Tn 2 C 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:

TnD 2 kTnkC 2 k^1 C 2 k^2 C


C 22 C 21 C 20

D 2 kTnkC 2 k 1

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-and-
chug.

TnD 2 kTnkC 2 k 1

D 2 k.2Tn.kC1/C1/C 2 k 1 plug

D 2 kC^1 Tn.kC1/C 2 kC^1  1 chug

The final expression on the right is the same as the expression on the first line,
except thatkis replaced bykC 1. Surprisingly, this effectivelyprovesthat the
formula is correct for allk. Here is why: we know the formula holds forkD 1 ,
because that’s the original recurrence equation. And we’ve just shown that if the
formula holds for somek 1 , then it also holds forkC 1. So the formula holds
for allk 1 by induction.