MATH 359: DISCRETE MATHEMATICS

Benedict Vasco NORMENYO, PhD

UNIVERSITY OF GHANA
COLLEGE OF BASIC AND APPLIED SCIENCES
SCHOOL OF PHYSICAL AND MATHEMATICAL SCIENCES
DEPARTMENT OF MATHEMATICS

December 4, 2023

SECTION 4 - RECURRENCE RELATIONS

ug1.jpg

Benedict Vasco NORMENYO, PhD MATH 359: DISCRETE MATHEMATICS December 4, 2023 1/48
Recurrence relations

Definition 4.1 (Recurrence relation)

A recurrence relation for the sequence {an }∞ n=0 is an equation that
expresses an in terms of one or more of the previous terms of the
sequence, namely, a0 , . . . , an−1 , for all integers n with n ≥ n0 , where n0 is
a non-negative integer. A sequence is called a solution of a recurrence
relation if its terms satisfy the recurrence relation.

Example 4.1
Find the first five terms of the sequence {an }∞
n=0 defined by each of the
following recurrence relations and initial conditions.
1 an = −an−1 + n − 1, a0 = 7
2 xn+2 + 5xn+1 + 6xn = 0, x0 = 1, x1 = −1
3 an = an−1 + an−3 , a0 = 1, a1 = 2, a2 = 0
ug1.jpg

Benedict Vasco NORMENYO, PhD MATH 359: DISCRETE MATHEMATICS December 4, 2023 2/48
Recurrence relations

SOLUTION:
1 To obtain the other terms of the sequence, we notice that the
an = −an−1 + n − 1 holds for n ≥ 1. We have that

a0 = 7
a1 = −a0 + 0 = −7
a2 = −a1 + 1 = 8
a3 = −a2 + 2 = −6
a4 = −a3 + 3 = 9

ug1.jpg

Benedict Vasco NORMENYO, PhD MATH 359: DISCRETE MATHEMATICS December 4, 2023 3/48
Recurrence relations

2 Here, we consider the recurrence xn+2 + 5xn+1 + 6xn = 0 holds for

n ≥ 0. This leads us to the following:

x0 = 1
x1 = −1
x2 = −(5x1 + 6x0 ) = −1
x3 = −(5x2 + 6x1 ) = 11
x4 = −(5x3 + 6x2 ) = −49

Note that the recurrence relation xn+2 + 5xn+1 + 6xn = 0 can be

rewritten in the form xn = −5xn−1 − 6xn−2 for n ≥ 2 (by replacing n
with n − 2).

ug1.jpg

Benedict Vasco NORMENYO, PhD MATH 359: DISCRETE MATHEMATICS December 4, 2023 4/48
Recurrence relations

3 We consider an = an−1 + an−3 with n > 2. This yields

a0 = 1
a1 = 2
a2 = 0
a3 = a2 + a0 = 1
a4 = a3 + a1 = 3,

which are the first five terms of the given sequence.

ug1.jpg

Benedict Vasco NORMENYO, PhD MATH 359: DISCRETE MATHEMATICS December 4, 2023 5/48
Recurrence relations
Example 4.2
Determine whether the sequence {an }∞n=0 is a solution of the recurrence
relation an = 8an−1 − 16an−2 given that
1 an = n4n
2 an = 1

SOLUTION:
1 Let the sequence {a }∞ n
n n=0 be given by an = n4 . This means that
an−1 = (n − 1)4 n−1 and an−2 = (n − 2)4 n−2 for n ≥ 2. We find that
8(n − 1)4n−1 − 16(n − 2)4n−2 = 4n−2 [8(n − 1) × 4 − 16(n − 2)]
= 16 × 4n−2 [2n − 2 − n + 2]
= n4n
= an ,
ug1.jpg

Benedict Vasco NORMENYO, PhD MATH 359: DISCRETE MATHEMATICS December 4, 2023 6/48
Recurrence relations

which mean that the sequence {an }∞ n

n=0 , given by given by an = n4 , is a
solution of the recurrence relation an = 8an−1 − 16an−2 .
2 Let the sequence {an }∞
n=0 be given by an = 1. Then, an−1 = 1 and
an−2 = 1 for n ≥ 2. We observe that

8 − 16 = −8 ̸= 1 = an ,

for all n ≥ 2. Hence, the sequence {an }∞ n=0 , given by given by an = 1

is not a solution of the recurrence relation an = 8an−1 − 16an−2 .

ug1.jpg

Benedict Vasco NORMENYO, PhD MATH 359: DISCRETE MATHEMATICS December 4, 2023 7/48
Linear recurrence relations
Definition 4.2 (Linear recurrence relation)
A recurrence relation of the form

an = c1 (n)an−1 + c2 (n)an−2 + · · · + cp (n)an−p + f (n) (4.1)

where cp (n) ̸= 0 and c1 , c2 , . . . , cp , f are functions of n, is called a linear

recurrence relation of order p.

Example 4.3
1 3
an = 3an−1 + 4an−2 is non-linear, since an−1 is raised to power 3, and
is of order 2.
2 an = 3n3 an−1 + nan−2 is linear and has order 2.
3 an = an−1 an−2 + n2 is non-linear, because of the product an−1 an−2 ,
and has order 2.
4 an = 6an−1 − 11an−2 + 6an−3 is linear and has order 3. ug1.jpg

Benedict Vasco NORMENYO, PhD MATH 359: DISCRETE MATHEMATICS December 4, 2023 8/48
Linear recurrence relations

Definition 4.3 (Linear homogeneous recurrence relation)

A linear recurrence relation of the form

an = c1 (n)an−1 + c2 (n)an−2 + · · · + cp (n)an−p , (4.2)

where cp (n) ̸= 0, is called a linear homogeneous recurrence relation of

order p.

Example 4.4
1 an = an−1 an−2 + n2 is non-linear, non-homogeneous and has order 2.
2 an = 6an−1 − 11an−2 + 6an − 3 is linear, homogeneous and has order
3.
3 an = 5an−1 − 6an−2 + n is linear, non-homogeneous of order 2.
ug1.jpg

Benedict Vasco NORMENYO, PhD MATH 359: DISCRETE MATHEMATICS December 4, 2023 9/48
Linear recurrence relations

Definition 4.4 (Linear recurrence relation with constant

coefficients)
A linear recurrence of the form

an = c1 an−1 + c2 an−2 + · · · + cp an−p + f (n), (4.3)

where cp ̸= 0, with constants ci for 1 ≤ i ≤ p, is called a linear recurrence

relation with constant coefficients of order p.

Example 4.5
1 an = 5an−1 − 6an−2 + n is linear with constant coefficients and of
order 2.
2 an = 6an−1 − 11an−2 + 6an−3 is linear with constant coefficients and
of order 3.
ug1.jpg

Benedict Vasco NORMENYO, PhD MATH 359: DISCRETE MATHEMATICS December 4, 2023 10/48
Linear recurrence relations
Definition 4.5
A linear recurrence relation of the form

an = c1 an−1 + c2 an−2 + · · · + cp an−p , cp ̸= 0, (4.4)

with constants ci for 1 ≤ i ≤ p is called a linear homogeneous recurrence

relation with constant coefficients of order p.

Solving linear homogeneous recurrence relations with constant

coefficients: Let us consider a linear homogeneous recurrence relation of
order k having constant coefficients given by
an = c1 an−1 + c2 an−2 + · · · + ck an−k , (4.5)
with initial conditions
a0 = A0 , a1 = A1 , . . . , ak−1 = Ak−1 . (4.6)
ug1.jpg

Benedict Vasco NORMENYO, PhD MATH 359: DISCRETE MATHEMATICS December 4, 2023 11/48
Homogeneous recurrence relations

To solve the recurrence relation (4.5), we seek solutions of the form

an = r n , where r is a constant. We observe that, if the sequence {an }∞
n=0
with an = r n is a solution of (4.5) then

r n = c1 r n−1 + c2 r n−2 + · · · + ck−1 r n−(k−1) + ck r n−k .

Multiplying both sides of the last equation by r k−n , we get

r k = c1 r k−1 + c2 r k−2 + · · · + ck−1 r + ck ,

which we rearrange to obtain

r k − c1 r k−1 − c2 r k−2 − · · · − ck−1 r − ck = 0. (4.7)

Equation (4.7) is called the characteristic equation of the recurrence

relation (4.5). The solutions of the characteristic equation are called the
characteristic roots of the recurrence relation. ug1.jpg

Benedict Vasco NORMENYO, PhD MATH 359: DISCRETE MATHEMATICS December 4, 2023 12/48
Homogeneous recurrence relations

Theorem 4.1
Let c1 , c2 ∈ R. Suppose that r 2 − c1 r − c2 = 0 has two distinct roots r1
and r2 . Then the sequence {an }∞ n=0 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: Let c1 , c2 ∈ R. Suppose that the equation

r 2 − c1 r − c2 = 0 (4.8)

has two distinct roots r1 and r2 . Since r1 and r2 are roots of equation
(4.8), we have that r12 = c1 r1 + c2 and r22 = c1 r2 + c2 .
Now, suppose that the sequence {an }∞ n n
n=0 is given by an = α1 r1 + α2 r2 ,
where α1 and α2 are constants.
ug1.jpg

Benedict Vasco NORMENYO, PhD MATH 359: DISCRETE MATHEMATICS December 4, 2023 13/48
Homogeneous recurrence relations

Then, it follows, for n ≥ 2, 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 ,

from which we deduce that the sequence {an }∞ n=0 given by

an = α1 r1n + α2 r2n , where α1 and α2 are constants, is a solution of the
recurrence relation an = c1 an−1 + c2 an−2 .
Conversely, suppose that the sequence {an }∞ n=0 is a solution of the
recurrence relation an = c1 an−1 + c2 an−2 , where n ≥ 2, and that the initial
conditions a0 = A0 and a1 = A1 hold.
ug1.jpg

Benedict Vasco NORMENYO, PhD MATH 359: DISCRETE MATHEMATICS December 4, 2023 14/48
Homogeneous recurrence relations
Choose
A1 − A0 r2
α1 = , r1 ̸= r2 (4.9)
r1 − r2
and
A0 r1 − A1
α2 = , r1 ̸= r2 . (4.10)
r1 − r2
Consider the sequence {α1 r1n + α2 r2n }∞
n=0 . We observe that

A1 − A0 r2 A0 r1 − A1 A0 (r1 − r2 )
α1 r10 + α2 r20 = + = = A0 (4.11)
r1 − r2 r1 − r2 r1 − r2
and
A1 − A0 r2 A0 r1 − A1 A1 (r1 − r2 )
α1 r11 + α2 r21 = r1 + r2 = = A1 . (4.12)
r1 − r2 r1 − r2 r1 − r2
ug1.jpg

Benedict Vasco NORMENYO, PhD MATH 359: DISCRETE MATHEMATICS December 4, 2023 15/48
Homogeneous recurrence relations

Furthermore, we have seen that {α1 r1n + α2 r2n }∞

n=0 satisfies the recurrence
relation an = c1 an−1 + c2 an−2 , for n ≥ 2. The recurrence relation and the
initial conditions uniquely determine a sequence. Therefore,
an = α1 r1n + α2 r2n .

Example 4.6
A young pair of rabbits (one of each sex) is placed on an island. A pair of
rabbits does not breed until they are 2 months old. After they are 2
months old, each pair of rabbits produces another pair each month. Find a
recurrence relation for the number Fn of pairs of rabbits on the island after
n months, assuming that no rabbits ever die. Hence, find an explicit
formula for Fn .
[NB: The sequence {Fn }∞ n=0 is known as the Fibonacci sequence]

ug1.jpg

Benedict Vasco NORMENYO, PhD MATH 359: DISCRETE MATHEMATICS December 4, 2023 16/48
Homogeneous recurrence relations

SOLUTION:

ug1.jpg

Benedict Vasco NORMENYO, PhD MATH 359: DISCRETE MATHEMATICS December 4, 2023 17/48
Homogeneous recurrence relations
Let Fn be the number of pairs of rabbits after n months. In the beginning,
when n = 0, there was no pair of rabbits on the island, and so F0 = 0.
After the first one month, we get F1 = 1. Since this pair does not breed
during the second month, we see that F2 = 1. We observe that each
newborn pair comes from a pair at least 2 months old, which means that
the number of newborn pairs after n months is Fn−2 . So, we deduce that

F0 = 0, F1 = 1, Fn = Fn−1 + Fn−2 for n ≥ 2,

where Fn−1 is the number pairs of rabbits on the island the previous
month.
The characteristic equation of the recurrence relation Fn = Fn−1 + Fn−2 is
r 2 − r − 1, which yields the characteristic roots
√ √
1+ 5 1− 5
r1 = and r2 = . (4.13)
2 2
ug1.jpg

Benedict Vasco NORMENYO, PhD MATH 359: DISCRETE MATHEMATICS December 4, 2023 18/48
Homogeneous recurrence relations
Theorem 4.1 enables us to write
√ !n √ !n
1+ 5 1− 5
Fn = α1 + α2 , (4.14)
2 2

where α1 and α2 are constants determined by initial conditions F0 = 0 and

F1 = 1. Appealing to the initial conditions F0 = 0 and F1 = 1, we obtain
the equations
α1 + α2 = 0 (4.15)
and √ ! √ !
1+ 5 1− 5
α1 + α2 = 1, (4.16)
2 2
which, when solve simultaneously, yield
1 1
α1 = √ and α2 = − √ . (4.17)
5 5
ug1.jpg

Benedict Vasco NORMENYO, PhD MATH 359: DISCRETE MATHEMATICS December 4, 2023 19/48
Homogeneous recurrence relations
Therefore, the Binet formula for the Fibonacci sequence {Fn }∞
n=0 is
" √ !n √ !n #
1 1+ 5 1− 5
Fn = √ − . (4.18)
5 2 2

Example 4.7
Solve the recurrence relation an = 3an−2 − 2an−1 , n ≥ 2 given that a0 = 1
and a1 = −3.

SOLUTION: The characteristic equation of the recurrence relation

an = 3an−2 − 2an−1 is given by r 2 + 2r − 3, which gives us the
characteristic roots r = −3, 1. Thus, using Theorem 4.1, we get

an = A(−3)n + B, (4.19)

where A and B are constants determined by the initial conditions a0 = 1

and a1 = −3. ug1.jpg

Benedict Vasco NORMENYO, PhD MATH 359: DISCRETE MATHEMATICS December 4, 2023 20/48
Homogeneous recurrence relations
We employ the initial conditions to obtain the equations

A+B =1 (4.20)

and
− 3A + B = −3. (4.21)
We solve equations (4.20) and (4.21) simultaneously to get A = 1 and
B = 0. Hence we find that the solution {an }∞ n=0 to the given recurrence
relation and initial conditions has an = (−3)n .

Theorem 4.2
Let c1 , c2 ∈ R with c2 ̸= 0. Suppose that r 2 − c1 r − c2 = 0 has only one
real root r0 . A sequence {an }∞
n=0 is a solution of the recurrence relation
an = c1 an−1 + c2 an−2 if and only if an = α1 r0n + α2 nr0n , where α1 and α2
are constants determined by initial conditions a0 = A0 and a1 = A1 .
ug1.jpg

Benedict Vasco NORMENYO, PhD MATH 359: DISCRETE MATHEMATICS December 4, 2023 21/48
Homogeneous recurrence relations
PROOF: Let c1 , c2 ∈ R with c2 ̸= 0. Suppose that r 2 − c1 r − c2 = 0 has
only one real root r0 .
Suppose that the sequence {an }∞ n n
n=0 is defined by an = α1 r0 + α2 nr0 ,
where α1 and α2 are constants. Then, for n ≥ 2, we find that
h i h
c1 an−1 + c2 an−2 = c1 α1 r0n−1 + α2 (n − 1)r0n−1 + c2 α1 r0n−2 + α2 (n − 2)r0n−
= α1 r0n−2 [c1 r0 + c2 ] + α2 r0n−2 [c1 (n − 1)r0 + c2 (n − 2)]
= α1 r0n−2 r02 + α2 r0n−2 [n(c1 r0 + c2 ) − (c1 r0 + 2c2 )]
= α1 r0n + α2 r0n−2 [nr02 − (c1 r0 + 2c2 )].

We note that r 2 − 2r0 r + r02 = 0, since r0 is a repeated root of

r 2 − c1 r − c2 = 0. Consequently, we see that c1 = 2r0 and c2 = −r02 . This
leads us to

c1 r0 + 2c2 = (2r0 )r0 + 2(−r02 ) = 2r02 − 2r02 = 0. (4.22)

ug1.jpg

Benedict Vasco NORMENYO, PhD MATH 359: DISCRETE MATHEMATICS December 4, 2023 22/48
Homogeneous recurrence relations

It follows that

c1 an−1 + c2 an−2 = α1 r0n + α2 r0n−2 (nr02 )

= α1 r0n + α2 nr0n
= an .

Hence, the sequence {an }∞ n n

n=0 defined by an = α1 r0 + α2 nr0 , where α1 and
α2 are constants, is a solution of the recurrence relation
an = c1 an−1 + c2 an−2 .
Conversely, suppose that the sequence {an }∞ n=0 is a solution of the
recurrence relation an = c1 an−1 + c2 an−2 , where n ≥ 2, and that the initial
conditions a0 = A0 and a1 = A1 hold. Choose
1
α1 = A0 and α2 = (A1 − A0 r0 ) (4.23)
r0
ug1.jpg

Benedict Vasco NORMENYO, PhD MATH 359: DISCRETE MATHEMATICS December 4, 2023 23/48
Homogeneous recurrence relations

Consider the sequence {α1 r0n + α2 nr0n }∞

n=0 . We find that

α1 r00 + α2 (0)r00 = α1 = A0 (4.24)

and

α1 r01 + α2 (1)r01 = α1 r0 + α2 r0 = A0 r0 + A1 − A0 r0 = A1 . (4.25)

Furthermore, we have seen that {α1 r0n + α2 nr0n }∞n=0 satisfies the
recurrence relation an = c1 an−1 + c2 an−2 , for n ≥ 2. The recurrence
relation and the initial conditions uniquely determine a sequence.
Therefore, an = α1 r0n + α2 nr0n .

ug1.jpg

Benedict Vasco NORMENYO, PhD MATH 359: DISCRETE MATHEMATICS December 4, 2023 24/48
Homogeneous recurrence relations

Example 4.8
Solve the recurrence relation given by an = 2an−1 − an−2 , n ≥ 2 with
initial conditions a0 = 4 and a1 = 1.

SOLUTION: From the recurrence relation an = 2an−1 − an−2 , n ≥ 2, we

find that the characteristic equation is r 2 − 2r + 1 = 0, which yields r = 1.
Thus, we get
an = α1 + nα2 , (4.26)
where we used Theorem 4.2. Using the initial conditions a0 = 4 and
a1 = 1, we arrive at the two equation

4 = α1 and 1 = α1 + α2 , (4.27)

which imply that α1 = 4 and α2 = −3. Hence, the sequence {an }∞ n=0
where an = 4 − 3n is the solution to the given recurrence relation and
initial conditions. ug1.jpg

Benedict Vasco NORMENYO, PhD MATH 359: DISCRETE MATHEMATICS December 4, 2023 25/48
Homogeneous recurrence relations

Example 4.9
Solve the recurrence relation an = 6an−1 − 9an−2 for n ≥ 2, with initial
conditions a0 = 1 and a1 = 6.

SOLUTION: We obtain the characteristic equation r 2 − 6r + 9, which

gives us r = 3. Consequently, we get

an = α1 3n + α2 n3n , (4.28)

using Theorem Theorem: Solution of a recurrence relation with

characteristic root. The initial conditions produce the two equations

α1 = 1 and α1 + α2 = 2, (4.29)

and so α2 = 1. We conclude that the sequence {an }∞ n=0 where

an = (1 + n)3n is the solution to the given recurrence relation and initial
conditions. ug1.jpg

Benedict Vasco NORMENYO, PhD MATH 359: DISCRETE MATHEMATICS December 4, 2023 26/48
Non-homogeneous Recurrence Relations

Consider the linear recurrence relation

an = c1 an−1 + c2 an−2 + · · · + ck an−k + F (n) (4.30)

of degree k, where c1 , c2 , . . . , ck ∈ R and F (n) ̸= 0 is a function of n. The

recurrence relation

an = c1 an−1 + c2 an−2 + · · · + ck an−k (4.31)

is called the associated homogeneous recurrence relation.

ug1.jpg

Benedict Vasco NORMENYO, PhD MATH 359: DISCRETE MATHEMATICS December 4, 2023 27/48
Non-homogeneous Recurrence Relations
Theorem 4.3
If {Pn }∞
n=0 is a particular solution of the non-homogeneous linear
recurrence relation with constant coefficients

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

then every solution is of the form {Pn + Hn }∞ ∞

n=0 , where {Hn }n=0 is a
solution of the associated homogeneous recurrence relation

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

PROOF: Let {Pn }∞ n=0 be a particular solution of the non-homogeneous

linear recurrence relation with constant coefficients
an = c1 an−1 + c2 an−2 + · · · + ck an−k + F (n). (4.32)
ug1.jpg

Benedict Vasco NORMENYO, PhD MATH 359: DISCRETE MATHEMATICS December 4, 2023 28/48
Non-homogeneous Recurrence Relations

Suppose that {bn }∞

n=0 is any solution of the linear recurrence (4.32).
Then, we have that

bn = c1 bn−1 + c2 bn−2 + · · · + ck bn−k + F (n). (4.33)

Subtracting equation (4.32) from equation (4.33), we get

bn −Pn = c1 (bn−1 −Pn−1 )+c2 (bn−2 −Pn−2 )+· · ·+ck (bn−k −Pn−k ). (4.34)

This means means that {bn − Pn }∞ n=0 is a solution of the associated

homogeneous linear recurrence relation, say {Hn }∞n=0 . Hence

bn = Pn + Hn for n = 0, 1, 2, . . . . (4.35)

ug1.jpg

Benedict Vasco NORMENYO, PhD MATH 359: DISCRETE MATHEMATICS December 4, 2023 29/48
Non-homogeneous Recurrence Relations

We shallconsider F (n) of the form

F (n) = ek nk + ek−1 nk−1 + · · · + e1 n + e0 s n , where e0 , e1 , . . . , ek and s
are constants. The following theorem shows us how to choose Pn
consistent with F (n).

Theorem 4.4
Suppose that {an }∞
n=0 satisfies the linear non-homogeneous recurrence
relation
an = c1 an−1 + c2 an−2 + · · · + ck an−k + F (n)
where c1 , c2 , . . . , ck ∈ R and

F (n) = ek nk + ek−1 nk−1 + · · · + e1 n + e0 s n ,

where e0 , e1 , . . . , ek and s are constants.

ug1.jpg

Benedict Vasco NORMENYO, PhD MATH 359: DISCRETE MATHEMATICS December 4, 2023 30/48
Non-homogeneous Recurrence Relations

Theorem 4.4 (cont.)

When s is not a root of the characteristic equation of the associated linear
homogeneous recurrence relation, there is a particular solution {Pn }∞
n=0 of
the form
Pn = Ak nk + Ak−1 nk−1 + · · · + A1 n + A0 s n ,
where A0 , A1 , . . . , Ak are constants.
When s is a solution of the characteristic equation and its multiplicity is
m, there is a particular solution {Pn }∞ n=0 of the form

Pn = nm Ak nk + Ak−1 nk−1 + · · · + A1 n + A0 s n ,

where A0 , A1 , . . . , Ak are constants.

ug1.jpg

Benedict Vasco NORMENYO, PhD MATH 359: DISCRETE MATHEMATICS December 4, 2023 31/48
Non-homogeneous Recurrence Relations
Example 4.10
Find all solutions of the recurrence relation
an = 4an−1 − 4an−2 + (n + 1)2n .

SOLUTION: We are given the recurrence relation

an = 4an−1 − 4an−2 + (n + 1)2n . (4.36)
The characteristic equation of an = 4an−1 − 4an−2 is r 2 − 4r + 4 = 0 with
root r = 2. Solutions of the associated homogeneous recurrence relation
an = 4an−1 − 4an−2 are given by
Hn = α1 2n + α2 n2n . (4.37)
There is a particular solution of the linear recurrence (4.36) of the form
Pn = n2 (An + B)2n , (4.38)
where we used Theorem 4.4. Now, we put Pn = n2 (An + B)2n into
equation (4.36). ug1.jpg

Benedict Vasco NORMENYO, PhD MATH 359: DISCRETE MATHEMATICS December 4, 2023 32/48
Non-homogeneous Recurrence Relations
This leads us to

n2 (An + B)2n = 4(n − 1)2 [A(n − 1) + B]2n−1

− 4(n − 2)2 [A(n − 2) + B]2n−2 + (n + 1)2n ,
(4.39)

from which we obtain

4n2 (An + B) = 8(n − 1)2 [A(n − 1) + B] − 4(n − 2)2 [A(n − 2) + B] + 4(n + 1

(4.40)

when we multiply through equation (4.39) by 22−n . Putting n = 1 in

equation (4.40), we get

4(A + B) = −4[−A + B] + 8, (4.41)

which yields B = 1. ug1.jpg

Benedict Vasco NORMENYO, PhD MATH 359: DISCRETE MATHEMATICS December 4, 2023 33/48
Non-homogeneous Recurrence Relations
Putting n = 2 in equation (4.40), we get
16(2A + B) = 8(A + B), (4.42)
1
which yields A = . Therefore, we obtain
6
1

an = (α1 + nα2 )2n + n2 n + 1 2n . (4.43)
6

Example 4.11
The plane is divided by n straight lines in such a way that every pair of
lines intersect but, but no three lines intersect. Obtain a linear recurrence
relation for the number of regions into which the plane is divided. Hence
find a formula for the number of regions into which n lines divide the plane.

SOLUTION: Let an be the number of regions into which n lines divide

the plane, where the lines intersect pairwise, but no three lines intersect.
We observe that a0 = 1, a1 = 2, a2 = 4, a3 = 7, and so on. ug1.jpg

Benedict Vasco NORMENYO, PhD MATH 359: DISCRETE MATHEMATICS December 4, 2023 34/48
Non-homogeneous Recurrence Relations
The nth line intersects the previous n − 1 lines at n − 1 points, adding n
new regions to the previously existing an−1 . Hence, we get
an = an−1 + n, a0 = 1. (4.44)
We find that solutions of an = an−1 are of the form Hn = C ∈ R. There is
a particular solution of the form Pn = n(An + B). Thus,
n(An + B) = (n − 1)[A(n − 1) + B] + n,
1
which produces A = B = . This implies that
2
n
an = C + (n + 1).
2
Using the initial condition a0 = 0, we obtain A = 1. Therefore, the
number an of regions into which n lines divide the plane, where the lines
intersect pairwise, but no three lines intersect is given by
1
an = [2 + n(n + 1)], n = 0, 1, 2, . . . .
2 ug1.jpg

Benedict Vasco NORMENYO, PhD MATH 359: DISCRETE MATHEMATICS December 4, 2023 35/48
Non-homogeneous Recurrence Relations

Example 4.12
Find all solutions of the recurrence relation

an = 3an−1 − 2an−2 + 5.

SOLUTION: The characteristic equation of an = 3an−1 − 2an−2 is

r 2 − 3r + 2 = 0, which gives the characteristic roots r = 2, 1. Solutions of
an = 3an−1 − 2an−2 take the form Hn = α1 2n + α2 . Seeing that
F (n) = 5(1)n , we know that there is a particular solution of
an = 3an−1 − 2an−2 + 5 of the form Pn = An. Consequently, we obtain

An = 3A(n − 1) − 2A(n − 2) + 5,

which gives us A = −5. Therefore, all solutions of an = 3an−1 − 2an−2 + 5

are of the form α1 2n + α2 − 5n. ug1.jpg

Benedict Vasco NORMENYO, PhD MATH 359: DISCRETE MATHEMATICS December 4, 2023 36/48
Non-homogeneous Recurrence Relations

Example 4.13
Find all solutions of the recurrence relation

gn = 6gn−1 − 9gn−2 + n2 22 .

SOLUTION: The characteristic equation of the recurrence relation

gn = 6gn−1 − 9gn−2 is given by r 2 − 6r + 9 = 0. Thus, the characteristic
root is r = 3. Hence, solutions of gn = 6gn−1 − 9gn−2 are of the form
Hn = A3n + Bn3n , where A and B are constants.
There is a particular solution of gn = 6gn−1 − 9gn−2 + n2 22 of the form

Pn = (an2 + bn + c)2n ,

where a, b and c are constants.

ug1.jpg

Benedict Vasco NORMENYO, PhD MATH 359: DISCRETE MATHEMATICS December 4, 2023 37/48
Non-homogeneous Recurrence Relations
This implies that
h i
an2 + bn + c 2n = 6 a(n − 1)2 + b(n − 1) + c 2n−1
h i
− 9 a(n − 2)2 + b(n − 2) + c 2n−2 + n2 2n ,
(4.45)
which gives us
h i
4 an2 + bn + c = 12 a(n − 1)2 + b(n − 1) + c
h i
− 9 a(n − 2)2 + b(n − 2) + c + n2 2n .
(4.46)
Equating coefficients of n2 , we find that a = 4. We get b = 48 when we
equate coefficients of n. When we equate constant terms, we arrive at
c = 192. All solutions of the given recurrence relation are given by
gn = (A + Bn)3n + (4n2 + 48n + 192)2n , (4.47)
ug1.jpg
where A and B are constants.
Benedict Vasco NORMENYO, PhD MATH 359: DISCRETE MATHEMATICS December 4, 2023 38/48
Generating Functions

Definition 4.6 (Generating Function)

The generating function for the sequence {ak }∞
k=0 of real numbers is the
infinite series
∞
X
2 k
G(x ) = a0 + a1 x + a2 x + · · · + ak x + · · · = ak x k .
k=0

We have seen how to solve a recurrence relation and its initial conditions
by first finding the characteristic equation. Here, we solve a recurrence
relation and its initial conditions by finding an explicit formula for the
associated generating function. We shall work with the generating
functions displayed in Table 1.

ug1.jpg

Benedict Vasco NORMENYO, PhD MATH 359: DISCRETE MATHEMATICS December 4, 2023 39/48
Generating Functions

G(x ) ak
n
(
1− x n+1 X 1, if k ≤ n
= = 1 + x + x2 + · · · + xn
1−x k=0 0, otherwise
∞
1 X
= xk = 1 + x + x2 + · · · 1
1−x k=0
∞
1 X
= ak x k = 1 + ax + a2 x 2 + · · · ak
1 − ax k=0
∞
1 X
= (k + 1)x k = 1 + 2x + 3x 2 + 4x 3 + · · · k +1
(1 − x )2 k=0
∞
(
1 X 1, if r |k
= x rk = 1 + x r + x 2r + x 3r + · · ·
1 − xr k=0 0, otherwise

Table 1: Some useful generating functions ug1.jpg

Benedict Vasco NORMENYO, PhD MATH 359: DISCRETE MATHEMATICS December 4, 2023 40/48
Generating Functions

Example 4.14
Using generating functions solve the recurrence relation an = 3an−1 + 2n
for n ≥ 1 and initial condition a1 = 3.

SOLUTION: When n = 1, we get a1 = 3a0 + 2. This implies that

1
a0 = , where we have used the fact that a1 = 3. Let
3
∞
X
G(x ) = an x n
n=0

be the generating function of the sequence {an }∞

n=0 .

ug1.jpg

Benedict Vasco NORMENYO, PhD MATH 359: DISCRETE MATHEMATICS December 4, 2023 41/48
Generating Functions
Then, we get
∞
X
G(x ) = a0 + an x n
n=1
∞
1 X
= + (3an−1 + 2n)x n
3 n=1
∞ ∞
1 X X
= + 3x an−1 x n−1 + 2x (n − 1 + 1)x n−1 .
3 n−1=0 n−1=0

Replacing n − 1 with n, we obtain

∞ ∞
1 X
n
X
G(x ) = + 3x an x + 2x (n + 1)x n
3 n=0 n=0
1 2x
= + 3xG(x ) + .
3 (1 − x )2
ug1.jpg

Benedict Vasco NORMENYO, PhD MATH 359: DISCRETE MATHEMATICS December 4, 2023 42/48
Generating Functions
It follows that
1 2x
G(x ) = +
3(1 − 3x ) (1 − x )2 (1 − 3x )
1 3 1 1
= + − −
3(1 − 3x ) 2(1 − 3x ) 2(1 − x ) (1 − x )2
11 1 1
= − −
6(1 − 3x ) 2(1 − x ) (1 − x )2
∞ ∞ ∞
11 X 1X X
= 3n x n − xn − (n + 1)x n
6 n=0 2 n=0 n=0
∞
11 3
X
= 3n − n − x n.
n=0
6 2
The solution {an }∞
of the recurrence relation an = 3an−1 + 2n, n ≥ 1
n=1
and initial condition a1 = 3 is given by
11 3
an = 3 n − n − .
6 2 ug1.jpg

Benedict Vasco NORMENYO, PhD MATH 359: DISCRETE MATHEMATICS December 4, 2023 43/48
Generating Functions

Example 4.15
Find an explicit formula for ak given that

a0 = 1, a1 = 4, and ak = ak−1 + 6ak−2 for k ≥ 2,

using generating functions.

SOLUTION: Let the generating function for the sequence {ak }∞

k=0 be
given by
∞
X
G(x ) = ak x k .
k=0

ug1.jpg

Benedict Vasco NORMENYO, PhD MATH 359: DISCRETE MATHEMATICS December 4, 2023 44/48
Generating Functions

It follows that
∞
X
G(x ) = a0 + a1 x + ak x k
k=2
∞
X
= 1 + 4x + (ak−1 + 6ak−2 )x k
k=2
∞
X ∞
X
= 1 + 4x − x + x ak−1 x k−1 + 6x 2 ak−2 x k−2
k−1=0 k−2=0
∞
X ∞
X
= 1 + 3x + x ak x k + 6x 2 ak x k
k=0 k=0
2
= 1 + 3x + xG(x ) + 6x G(x ).

ug1.jpg

Benedict Vasco NORMENYO, PhD MATH 359: DISCRETE MATHEMATICS December 4, 2023 45/48
Generating Functions

Consequently, we deduce that

1 + 3x
G(x ) =
1 − x − 6x 2
1 + 3x
=
(1 − 3x )(1 + 2x )
6 1
= −
5(1 − 3x ) 5(1 + 2x )
∞ ∞
6X 1X
= 3k x k − (−2)k x k
5 k=0 5 k=0
∞
6 1
X
= 3k − (−2)k x k .
k=0
5 5

ug1.jpg

Benedict Vasco NORMENYO, PhD MATH 359: DISCRETE MATHEMATICS December 4, 2023 46/48
Generating Functions

Therefore, the solution {ak }∞

k=0 of the recurrence relation
ak = ak−1 + 6ak−2 , k ≥ 2 and initial conditions a0 = 1 and a1 = 4 is
given by
6 1
ak = 3k − (−2)k .
5 5

ug1.jpg

Benedict Vasco NORMENYO, PhD MATH 359: DISCRETE MATHEMATICS December 4, 2023 47/48
END

OF

RECURRENCE RELATIONS

ug1.jpg

Benedict Vasco NORMENYO, PhD MATH 359: DISCRETE MATHEMATICS December 4, 2023 48/48