8.

2 Solving Linear Recurrence Relations 541

degree two. The recurrence relation an = an−5 is a linear homogeneous recurrence relation of
degree five. ◂

To help clarify the definition of linear homogeneous recurrence relations with constant co-
efficients, we will now provide examples of recurrence relations each lacking one of the defining
properties.
EXAMPLE 2 The recurrence relation an = an−1 + a2n−2 is not linear. The recurrence relation Hn = 2Hn−1 + 1
is not homogeneous. The recurrence relation Bn = nBn−1 does not have constant coefficients.◂

Linear homogeneous recurrence relations are studied for two reasons. First, they often occur
in modeling of problems. Second, they can be systematically solved.

8.2.2 Solving Linear Homogeneous Recurrence Relations

with Constant Coefficients
Recurrence relations may be difficult to solve, but fortunately this is not the case for linear
homogenous recurrence relations with constant coefficients. We can use two key ideas to find
all their solutions. First, these recurrence relations have solutions of the form an = rn , where
r is a constant. To see this, observe that an = rn is a solution of the recurrence relation an =
c1 an−1 + c2 an−2 + ⋯ + ck an−k if and only if

rn = c1 rn−1 + c2 rn−2 + ⋯ + ck rn−k .

When both sides of this equation are divided by rn−k (when r ≠ 0) and the right-hand side is
subtracted from the left, we obtain the equation

rk − c1 rk−1 − c2 rk−2 − ⋯ − ck−1 r − ck = 0.

Consequently, the sequence {an } with an = rn where r ≠ 0 is a solution if and only if r is a

solution of this last equation. We call this the characteristic equation of the recurrence relation.
The solutions of this equation are called the characteristic roots of the recurrence relation. As
we will see, these characteristic roots can be used to give an explicit formula for all the solutions
of the recurrence relation.
The other key observation is that a linear combination of two solutions of a linear homoge-
neous recurrence relation is also a solution. To see this, suppose that sn and tn are both solutions
of an = c1 an−1 + c2 an−2 + ⋯ + ck an−k . Then

sn = c1 sn−1 + c2 sn−2 + ⋯ + ck sn−k

and

tn = c1 tn−1 + c2 tn−2 + ⋯ + ck tn−k .

Now suppose that b1 and b2 are real numbers. Then

b1 sn + b2 tn = b1 (c1 sn−1 + c2 sn−2 + ⋯ + ck sn−k ) + b2 (c1 tn−1 + c2 tn−2 + ⋯ + ck tn−k )

= c1 (b1 sn−1 + b2 tn−1 ) + c2 (b1 sn−2 + b2 tn−2 ) + ⋯ + ck (b1 sn−k + bk tn−k ).

This means that b1 sn + b2 tn is also a solution of the same linear homogeneous recurrence rela-
tion.
Using these key observations, we will show how to solve linear homogeneous recurrence
relations with constant coefficients.
542 8 / Advanced Counting Techniques

THE DEGREE TWO CASE We now turn our attention to linear homogeneous recurrence
relations of degree two. First, consider the case when there are two distinct characteristic roots.

THEOREM 1 Let c1 and c2 be real numbers. Suppose that r2 − c1 r − c2 = 0 has two distinct roots r1
and r2 . Then the sequence {an } is a solution of the recurrence relation an = c1 an−1 + c2 an−2
if and only if an = 𝛼1 r1n + 𝛼2 r2n for n = 0, 1, 2, … , where 𝛼1 and 𝛼2 are constants.

Proof: We must do two things to prove the theorem. First, it must be shown that if r1 and r2
are the roots of the characteristic equation, and 𝛼1 and 𝛼2 are constants, then the sequence {an }
with an = 𝛼1 r1n + 𝛼2 r2n is a solution of the recurrence relation. Second, it must be shown that if
the sequence {an } is a solution, then an = 𝛼1 r1n + 𝛼2 r2n for some constants 𝛼1 and 𝛼2 .
We now show that if an = 𝛼1 r1n + 𝛼2 r2n , then the sequence {an } is a solution of
the recurrence relation. Because r1 and r2 are roots of r2 − c1 r − c2 = 0, it follows
that r12 = c1 r1 + c2 and r22 = c1 r2 + c2 .
From these equations, we see that

c1 an−1 + c2 an−2 = c1 (𝛼1 r1n−1 + 𝛼2 r2n−1 ) + c2 (𝛼1 r1n−2 + 𝛼2 r2n−2 )

= 𝛼1 r1n−2 (c1 r1 + c2 ) + 𝛼2 r2n−2 (c1 r2 + c2 )
= 𝛼1 r1n−2 r12 + 𝛼2 r2n−2 r22
= 𝛼1 r1n + 𝛼2 r2n
= an .

This shows that the sequence {an } with an = 𝛼1 r1n + 𝛼2 r2n is a solution of the recurrence relation.
To show that every solution {an } of the recurrence relation an = c1 an−1 + c2 an−2
has an = 𝛼1 r1n + 𝛼2 r2n for n = 0, 1, 2, … , for some constants 𝛼1 and 𝛼2 , suppose that {an } is a
solution of the recurrence relation, and the initial conditions a0 = C0 and a1 = C1 hold. It will
be shown that there are constants 𝛼1 and 𝛼2 such that the sequence {an } with an = 𝛼1 r1n + 𝛼2 r2n
satisfies these same initial conditions. This requires that

a0 = C0 = 𝛼1 + 𝛼2 ,
a1 = C1 = 𝛼1 r1 + 𝛼2 r2 .

We can solve these two equations for 𝛼1 and 𝛼2 . From the first equation it follows that
𝛼2 = C0 − 𝛼1 . Inserting this expression into the second equation gives

C1 = 𝛼1 r1 + (C0 − 𝛼1 )r2 .

Hence,

C1 = 𝛼1 (r1 − r2 ) + C0 r2 .

This shows that

C1 − C0 r2
𝛼1 =
r1 − r2

and
C1 − C0 r2 C r − C1
𝛼2 = C0 − 𝛼1 = C0 − = 0 1 ,
r1 − r2 r1 − r2
 8.2 Solving Linear Recurrence Relations 543

where these expressions for 𝛼1 and 𝛼2 depend on the fact that r1 ≠ r2 . (When r1 = r2 , this the-
orem is not true.) Hence, with these values for 𝛼1 and 𝛼2 , the sequence {an } with 𝛼1 r1n + 𝛼2 r2n
satisfies the two initial conditions.
We know that {an } and {𝛼1 r1n + 𝛼2 r2n } are both solutions of the recurrence relation
an = c1 an−1 + c2 an−2 and both satisfy the initial conditions when n = 0 and n = 1. Because
there is a unique solution of a linear homogeneous recurrence relation of degree two with two
initial conditions, it follows that the two solutions are the same, that is, an = 𝛼1 r1n + 𝛼2 r2n for
all nonnegative integers n. We have completed the proof by showing that a solution of the lin-
ear homogeneous recurrence relation with constant coefficients of degree two must be of the
form an = 𝛼1 r1n + 𝛼2 r2n , where 𝛼1 and 𝛼2 are constants.

The characteristic roots of a linear homogeneous recurrence relation with constant coef-
ficients may be complex numbers. Theorem 1 (and also subsequent theorems in this section)
still applies in this case. Recurrence relations with complex characteristic roots will not be dis-
cussed in the text. Readers familiar with complex numbers may wish to solve Exercises 38
and 39.
Examples 3 and 4 show how to use Theorem 1 to solve recurrence relations.

EXAMPLE 3 What is the solution of the recurrence relation

Extra
an = an−1 + 2an−2
Examples

with a0 = 2 and a1 = 7?

Solution: Theorem 1 can be used to solve this problem. The characteristic equation of the re-
currence relation is r2 − r − 2 = 0. Its roots are r = 2 and r = −1. Hence, the sequence {an } is
a solution to the recurrence relation if and only if

an = 𝛼1 2n + 𝛼2 (−1)n ,

for some constants 𝛼1 and 𝛼2 . From the initial conditions, it follows that

a0 = 2 = 𝛼1 + 𝛼2 ,
a1 = 7 = 𝛼1 ⋅ 2 + 𝛼2 ⋅ (−1).

Solving these two equations shows that 𝛼1 = 3 and 𝛼2 = −1. Hence, the solution to the recur-
rence relation and initial conditions is the sequence {an } with

an = 3 ⋅ 2n − (−1)n . ◂

EXAMPLE 4 Find an explicit formula for the Fibonacci numbers.

Solution: Recall that the sequence of Fibonacci numbers satisfies the recurrence relation fn =
fn−1 + fn−2 and also satisfies the initial conditions
√ f0 = 0 and f1 =√
1. The roots of the character-
2
istic equation r − r − 1 = 0 are r1 = (1 + 5)∕2 and r2 = (1 − 5)∕2. Therefore, from The-
orem 1 it follows that the Fibonacci numbers are given by
( √ )n ( √ )n
1+ 5 1− 5
fn = 𝛼1 + 𝛼2 ,
2 2
544 8 / Advanced Counting Techniques

for some constants 𝛼1 and 𝛼2 . The initial conditions f0 = 0 and f1 = 1 can be used to find these
constants. We have

f0 = 𝛼1 + 𝛼2 = 0,
( √ ) ( √ )
1+ 5 1− 5
f1 = 𝛼1 + 𝛼2 = 1.
2 2

The solution to these simultaneous equations for 𝛼1 and 𝛼2 is

√ √
𝛼1 = 1∕ 5, 𝛼2 = −1∕ 5.

Consequently, the Fibonacci numbers are given by

( √ )n ( √ )n
1 1+ 5 1 1− 5
fn = √ −√ .
5 2 5 2 ◂

Theorem 1 does not apply when there is one characteristic root of multiplicity two. If this
happens, then an = nr0n is another solution of the recurrence relation when r0 is a root of multi-
plicity two of the characteristic equation. Theorem 2 shows how to handle this case.

THEOREM 2 Let c1 and c2 be real numbers with c2 ≠ 0. Suppose that r2 − c1 r − c2 = 0 has only one root
r0 . A sequence {an } is a solution of the recurrence relation an = c1 an−1 + c2 an−2 if and only
if an = 𝛼1 r0n + 𝛼2 nr0n , for n = 0, 1, 2, … , where 𝛼1 and 𝛼2 are constants.

The proof of Theorem 2 is left as Exercise 10. Example 5 illustrates the use of this theorem.

EXAMPLE 5 What is the solution of the recurrence relation

an = 6an−1 − 9an−2

with initial conditions a0 = 1 and a1 = 6?

Solution: The only root of r2 − 6r + 9 = 0 is r = 3. Hence, the solution to this recurrence rela-
tion is

an = 𝛼1 3n + 𝛼2 n3n

for some constants 𝛼1 and 𝛼2 . Using the initial conditions, it follows that

a0 = 1 = 𝛼1 ,
a1 = 6 = 𝛼1 ⋅ 3 + 𝛼2 ⋅ 3.

Solving these two equations shows that 𝛼1 = 1 and 𝛼2 = 1. Consequently, the solution to this
recurrence relation and the initial conditions is

an = 3n + n3n .
◂
 8.2 Solving Linear Recurrence Relations 545

THE GENERAL CASE We will now state the general result about the solution of linear ho-
mogeneous recurrence relations with constant coefficients, where the degree may be greater
than two, under the assumption that the characteristic equation has distinct roots. The proof of
this result will be left as Exercise 16.

THEOREM 3 Let c1 , c2 , … , ck be real numbers. Suppose that the characteristic equation

rk − c1 rk−1 − ⋯ − ck = 0

has k distinct roots r1 , r2 , … , rk . Then a sequence {an } is a solution of the recurrence relation

an = c1 an−1 + c2 an−2 + ⋯ + ck an−k

if and only if

an = 𝛼1 r1n + 𝛼2 r2n + ⋯ + 𝛼k rkn

for n = 0, 1, 2, … , where 𝛼1 , 𝛼2 , … , 𝛼k are constants.

We illustrate the use of the theorem with Example 6.

EXAMPLE 6 Find the solution to the recurrence relation

an = 6an−1 − 11an−2 + 6an−3

with the initial conditions a0 = 2, a1 = 5, and a2 = 15.

Solution: The characteristic polynomial of this recurrence relation is

r3 − 6r2 + 11r − 6.

The characteristic roots are r = 1, r = 2, and r = 3, because r3 − 6r2 + 11r − 6 =

(r − 1)(r − 2)(r − 3). Hence, the solutions to this recurrence relation are of the form

an = 𝛼1 ⋅ 1n + 𝛼2 ⋅ 2n + 𝛼3 ⋅ 3n .

To find the constants 𝛼1 , 𝛼2 , and 𝛼3 , use the initial conditions. This gives

a0 = 2 = 𝛼1 + 𝛼2 + 𝛼3 ,
a1 = 5 = 𝛼1 + 𝛼2 ⋅ 2 + 𝛼3 ⋅ 3,
a2 = 15 = 𝛼1 + 𝛼2 ⋅ 4 + 𝛼3 ⋅ 9.

When these three simultaneous equations are solved for 𝛼1 , 𝛼2 , and 𝛼3 , we find that 𝛼1 = 1,
𝛼2 = −1, and 𝛼3 = 2. Hence, the unique solution to this recurrence relation and the given initial
conditions is the sequence {an } with

an = 1 − 2n + 2 ⋅ 3n . ◂

We now state the most general result about linear homogeneous recurrence relations with
constant coefficients, allowing the characteristic equation to have multiple roots. The key point
is that for each root r of the characteristic equation, the general solution has a summand of the
546 8 / Advanced Counting Techniques

form P(n)rn , where P(n) is a polynomial of degree m − 1, with m the multiplicity of this root.
We leave the proof of this result as Exercise 51.

THEOREM 4 Let c1 , c2 , … , ck be real numbers. Suppose that the characteristic equation

rk − c1 rk−1 − ⋯ − ck = 0

has t distinct roots r1 , r2 , … , rt with multiplicities m1 , m2 , … , mt , respectively, so

that mi ≥ 1 for i = 1, 2, … , t and m1 + m2 + ⋯ + mt = k. Then a sequence {an } is a solu-
tion of the recurrence relation

an = c1 an−1 + c2 an−2 + ⋯ + ck an−k

if and only if

an = (𝛼1,0 + 𝛼1,1 n + ⋯ + 𝛼1,m1 −1 nm1 −1 )r1n

+ (𝛼2,0 + 𝛼2,1 n + ⋯ + 𝛼2,m2 −1 nm2 −1 )r2n
+ ⋯ + (𝛼t,0 + 𝛼t,1 n + ⋯ + 𝛼t,mt −1 nmt −1 )rtn

for n = 0, 1, 2, … , where 𝛼i,j are constants for 1 ≤ i ≤ t and 0 ≤ j ≤ mi − 1.

Example 7 illustrates how Theorem 4 is used to find the general form of a solution of a
linear homogeneous recurrence relation when the characteristic equation has several repeated
roots.
EXAMPLE 7 Suppose that the roots of the characteristic equation of a linear homogeneous recurrence relation
are 2, 2, 2, 5, 5, and 9 (that is, there are three roots, the root 2 with multiplicity three, the root
5 with multiplicity two, and the root 9 with multiplicity one). What is the form of the general
solution?

Solution: By Theorem 4, the general form of the solution is

(𝛼1,0 + 𝛼1,1 n + 𝛼1,2 n2 )2n + (𝛼2,0 + 𝛼2,1 n)5n + 𝛼3,0 9n . ◂

We now illustrate the use of Theorem 4 to solve a linear homogeneous recurrence relation
with constant coefficients when the characteristic equation has a root of multiplicity three.

EXAMPLE 8 Find the solution to the recurrence relation

an = −3an−1 − 3an−2 − an−3

with initial conditions a0 = 1, a1 = −2, and a2 = −1.

Solution: The characteristic equation of this recurrence relation is

r3 + 3r2 + 3r + 1 = 0.

Because r3 + 3r2 + 3r + 1 = (r + 1)3 , there is a single root r = −1 of multiplicity three of the

characteristic equation. By Theorem 4 the solutions of this recurrence relation are of the form

an = 𝛼1,0 (−1)n + 𝛼1,1 n(−1)n + 𝛼1,2 n2 (−1)n .

 8.2 Solving Linear Recurrence Relations 547

To find the constants 𝛼1,0 , 𝛼1,1 , and 𝛼1,2 , use the initial conditions. This gives

a0 = 1 = 𝛼1,0 ,
a1 = −2 = −𝛼1,0 − 𝛼1,1 − 𝛼1,2 ,
a2 = −1 = 𝛼1,0 + 2𝛼1,1 + 4𝛼1,2 .

The simultaneous solution of these three equations is 𝛼1,0 = 1, 𝛼1,1 = 3, and 𝛼1,2 = −2.
Hence, the unique solution to this recurrence relation and the given initial conditions is the
sequence {an } with

an = (1 + 3n − 2n2 )(−1)n . ◂

8.2.3 Linear Nonhomogeneous Recurrence Relations

with Constant Coefficients
We have seen how to solve linear homogeneous recurrence relations with constant coefficients.
Is there a relatively simple technique for solving a linear, but not homogeneous, recurrence
relation with constant coefficients, such as an = 3an−1 + 2n? We will see that the answer is yes
for certain families of such recurrence relations.
The recurrence relation an = 3an−1 + 2n is an example of a linear nonhomogeneous re-
currence relation with constant coefficients, that is, a recurrence relation of the form

an = c1 an−1 + c2 an−2 + ⋯ + ck an−k + F(n),

where c1 , c2 , … , ck are real numbers and F(n) is a function not identically zero depending only
on n. The recurrence relation

an = c1 an−1 + c2 an−2 + ⋯ + ck an−k

is called the associated homogeneous recurrence relation. It plays an important role in the
solution of the nonhomogeneous recurrence relation.

EXAMPLE 9 Each of the recurrence relations an = an−1 + 2n , an = an−1 + an−2 + n2 + n + 1, an = 3an−1 +

n3n , and an = an−1 + an−2 + an−3 + n! is a linear nonhomogeneous recurrence relation with
constant coefficients. The associated linear homogeneous recurrence relations are an = an−1 ,
an = an−1 + an−2 , an = 3an−1 , and an = an−1 + an−2 + an−3 , respectively. ◂

The key fact about linear nonhomogeneous recurrence relations with constant coefficients
is that every solution is the sum of a particular solution and a solution of the associated linear
homogeneous recurrence relation, as Theorem 5 shows.

(p)
THEOREM 5 If {an } is a particular solution of the nonhomogeneous linear recurrence relation with con-
stant coefficients

an = c1 an−1 + c2 an−2 + ⋯ + ck an−k + F(n),

(p)
then every solution is of the form {an + a(h) (h)
n }, where {an } is a solution of the associated
homogeneous recurrence relation

an = c1 an−1 + c2 an−2 + ⋯ + ck an−k .