Mathematics for Computer Science

21.3. Linear Recurrences 879

f.0/ D 0 ,f.1/D 1 ,f.2/ D 4 , andf.3/ D 9. Then we would obtain four
equations in four unknowns:

f.0/D 0 implies a
s^0 Cb
t^0 Cc
u^0 Cd
0u^0 D 0

f.1/D 1 implies a
s^1 Cb
t^1 Cc
u^1 Cd
1u^1 D 1

f.2/D 4 implies a
s^2 Cb
t^2 Cc
u^2 Cd
2u^2 D 4

f.3/D 9 implies a
s^3 Cb
t^3 Cc
u^3 Cd
3u^3 D 9

This looks nasty, but remember thats,t, anduare just constants. Solving this sys-
tem gives values fora,b,c, anddthat define a solution to the recurrence consistent
with the boundary conditions.

21.3.3 Solving General Linear Recurrences

We can now solve all linear homogeneous recurrences, which have the form

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


Cadf.nd/:

Many recurrences that arise in practice do not quite fit this mold. For example, the
Towers of Hanoi problem led to this recurrence:

f.1/D 1

f.n/D2f.n1/C 1 (forn 2 ):

The problem is the extraC 1 ; that is not allowed in a homogeneous linear recur-
rence. In general, adding an extra functiong.n/to the right side of a linear recur-
rence gives aninhomogeneous linear recurrence:

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


Cadf.nd/Cg.n/:

Solving inhomogeneous linear recurrences is neither very different nor very dif-
ficult. We can divide the whole job into five steps:

1. Replaceg.n/by 0, leaving a homogeneous recurrence. As before, find roots
   of the characteristic equation.


2. Write down the solution to the homogeneous recurrence, but do not yet use
   the boundary conditions to determine coefficients. This is called thehomo-
   geneous solution.


3. Now restoreg.n/and find a single solution to the recurrence, ignoring bound-
   ary conditions. This is called aparticular solution. We’ll explain how to find
   a particular solution shortly.