Mathematics for Computer Science

21.4. Divide-and-Conquer Recurrences 881

Therefore, the functionf.n/D 2 
 2 nn 2 solves this variant of the Towers

of Hanoi recurrence. For comparison, the solution to the original Towers of Hanoi

problem was 2 n 1. So if moving disks takes time proportional to their size, then

the monks will need about twice as much time to solve the whole puzzle.

21.3.4 How to Guess a Particular Solution

Finding a particular solution can be the hardest part of solving inhomogeneous

recurrences. This involves guessing, and you might guess wrong.^1 However, some

rules of thumb make this job fairly easy most of the time.

 Generally, look for a particular solution with the same form as the inhomo-

geneous termg.n/.

 Ifg.n/is a constant, then guess a particular solutionf.n/Dc. If this doesn’t

work, try polynomials of progressively higher degree:f.n/DbnCc, then

f.n/Dan^2 CbnCc, etc.

 More generally, ifg.n/is a polynomial, try a polynomial of the same degree,

then a polynomial of degree one higher, then two higher, etc. For example,

ifg.n/D6nC 5 , then tryf.n/DbnCcand thenf.n/Dan^2 CbnCc.

 Ifg.n/is an exponential, such as 3 n, then first guess thatf.n/ D c3n.

Failing that, tryf.n/Dbn3nCc3nand thenan^23 nCbn3nCc3n, etc.

The entire process is summarized on the following page.

21.4 Divide-and-Conquer Recurrences

We now have a recipe for solving general linear recurrences. But the Merge Sort

recurrence, which we encountered earlier, is not linear:

T.1/D 0

T.n/D2T.n=2/Cn 1 (forn 2 ):

In particular,T.n/is not a linear combination of a fixed number of immediately

preceding terms; rather,T.n/is a function ofT.n=2/, a term halfway back in the

sequence.

(^1) Chapter 15 explains how to solve linear recurrences with generating functions—it’s a little more
complicated, but it does not require guessing.