Chapter 21 Recurrences878
21.3.2 Solving Homogeneous Linear Recurrences
The method we used to solve the Fibonacci recurrence can be extended to solve
any homogeneous linear recurrence; that is, a recurrence of the form
f.n/Da 1 f.n 1/Ca 2 f.n 2/CCadf.n d/wherea 1 ;a 2 ;:::;adanddare constants. Substituting the guessf.n/Dxn, as
with the Fibonacci recurrence, gives
xnDa 1 xn ^1 Ca 2 xn ^2 CCadxn d:Dividing byxn dgives
xdDa 1 xd ^1 Ca 2 xd ^2 CCad 1 xCad:This is called thecharacteristic equationof the recurrence. The characteristic equa-
tion can be read off quickly since the coefficients of the equation are the same as
the coefficients of the recurrence.
The solutions to a linear recurrence are defined by the roots of the characteristic
equation. Neglecting boundary conditions for the moment:
Ifris a nonrepeated root of the characteristic equation, thenrnis a solution
to the recurrence. Ifris a repeated root with multiplicitykthenrn,nrn,n^2 rn,... ,nk ^1 rn
are all solutions to the recurrence.Theorem 21.3.1 implies that every linear combination of these solutions is also a
solution.
For example, suppose that the characteristic equation of a recurrence has rootss,
t, andutwice. These four roots imply four distinct solutions:
f.n/Dsn f.n/Dtn f.n/Dun f.n/Dnun:Furthermore, every linear combination
f.n/DasnCbtnCcunCdnun (21.1)is also a solution.
All that remains is to select a solution consistent with the boundary conditions
by choosing the constants appropriately. Each boundary condition implies a linear
equation involving these constants. So we can determine the constants by solving
a system of linear equations. For example, suppose our boundary conditions were