Mathematics for Computer Science

Chapter 21 Recurrences882

Short Guide to Solving Linear Recurrences

A linear recurrence is an equation

f.n/Da 1 f.n1/Ca 2 f.n2/C


Cadf.nd/

„ ƒ‚ ...

homogeneous part

Cg.n/

„ƒ‚...

inhomogeneous part

together with boundary conditions such asf.0/Db 0 ,f.1/Db 1 , etc. Linear
recurrences are solved as follows:

1. Find the roots of the characteristic equation
   xnDa 1 xn^1 Ca 2 xn^2 C
   
   
   Cak 1 xCak:


2. Write down the homogeneous solution. Each root generates one term and
   the homogeneous solution is their sum. A nonrepeated rootrgenerates the
   termcrn, wherecis a constant to be determined later. A rootrwith multi-
   plicitykgenerates the terms
   d 1 rn d 2 nrn d 3 n^2 rn ::: dknk^1 rn
   whered 1 ;:::dkare constants to be determined later.


3. Find a particular solution. This is a solution to the full recurrence that need
   not be consistent with the boundary conditions. Use guess-and-verify. If
   g.n/is a constant or a polynomial, try a polynomial of the same degree, then
   of one higher degree, then two higher. For example, ifg.n/Dn, then try
   f.n/DbnCcand thenan^2 CbnCc. Ifg.n/is an exponential, such as 3 n,
   then first guessf.n/Dc3n. Failing that, tryf.n/D.bnCc/3nand then
   .an^2 CbnCc/3n, etc.


4. Form the general solution, which is the sum of the homogeneous solution
   and the particular solution. Here is a typical general solution:
   f.n/D c2„nCƒ‚d.1/...n
   homogeneous solution

C 3n„ƒ‚C... 1.

inhomogeneous solution

5. Substitute the boundary conditions into the general solution. Each boundary
   condition gives a linear equation in the unknown constants. For example,
   substitutingf.1/D 2 into the general solution above gives
   2 Dc
   21 Cd
   .1/^1 C 3
   1 C 1
   IMPLIES 2 D2cd:
   Determine the values of these constants by solving the resulting system of
   linear equations.