Discrete Mathematics and Combinatorics 2024

CHAPTER 3

Advanced Counting Method and Recurrence Relation

3.1. The inclusion- exclusion principle

When two tasks can be done at the same time, we can’t use the sum rule to count the number of ways
to do one of the two tasks. Adding the number of ways to do one of the two tasks. Adding the number
of ways to do each task leads to an over count, since the ways to do both tasks are counted twice.
Question: Let 𝐴 𝑎𝑛𝑑 𝐵 be any two finite sets. How is |𝐴 ∪ 𝐵| related |𝐴| 𝑎𝑛𝑑 |𝐵| ?
Theorem 1 (Inclusion-exclusion principle)
Suppose a task 𝐴 can be done in 𝑚 ways, task 𝐵 in 𝑛 ways and both can be accomplished in 𝑘 different
ways. Then task 𝐴 𝑜𝑟 𝐵 can be done in 𝑚 + 𝑛 − 𝑘
We can phrase this counting principle in terms of sets. Let 𝐴 𝑎𝑛𝑑 𝐵 be two finite sets. Then
|𝐴 ∪ 𝐵| = |𝐴| + |𝐵| − |𝐴 ∩ 𝐵|
Example 1:- Find the number of positive integers ≤ 300 and divisible by 2 or 3.
Solution: Let 𝐴 = {𝑥 ∈ ℕ: 𝑥 ≤ 300 𝑎𝑛𝑑 𝑑𝑖𝑣𝑖𝑠𝑖𝑏𝑙𝑒 𝑏𝑦 2}
𝐵 = {𝑥 ∈ ℕ: 𝑥 ≤ 300 𝑎𝑛𝑑 𝑑𝑖𝑣𝑖𝑠𝑖𝑏𝑙𝑒 𝑏𝑦 3}
Then 𝐴 ∩ 𝐵 consists of positive integers ≤ 300 that are divisible by 2 and 3. That is, divisible by 6.
Thus,
𝐴 = {2,4, … ,300}
𝐵 = {3,6, … ,300} and 𝐴 ∩ 𝐵 = {6,12, … ,300}.
Clearly,|𝐴| = 150, |𝐵| = 100 𝑎𝑛𝑑 |𝐴 ∩ 𝐵| = 50 . By theorem 1.
|𝐴 ∪ 𝐵| = |𝐴| + |𝐵| − |𝐴 ∩ 𝐵| = 150 + 100 − 50 = 200
Thus, there are 200 positive integers ≤ 300 and divisible by 2or 3.
Example 2:- Find the number of positive integers ≤ 3000 and not divisible by 7 or 8.
Solution: Let 𝐴 = {𝑥 ∈ ℕ: 𝑥 ≤ 3000 𝑎𝑛𝑑 𝑑𝑖𝑣𝑖𝑠𝑖𝑏𝑙𝑒 𝑏𝑦 7}
𝐵 = {𝑥 ∈ ℕ: 𝑥 ≤ 3000 𝑎𝑛𝑑 𝑑𝑖𝑣𝑖𝑠𝑖𝑏𝑙𝑒 𝑏𝑦 8}
We need to find |𝐴′ ∩ 𝐵 ′ |
|𝐴′ ∩ 𝐵 ′ | = |(𝐴 ∪ 𝐵)′ | = |𝑈| − |𝐴 ∪ 𝐵| , Where 𝑈 be the universal set.

Hu 1|Page
Discrete Mathematics and Combinatorics 2024
= |𝑈| − |𝐴| − |𝐵| + |𝐴 ∩ 𝐵|
3000 3000 3000
= 3000 − − +
7 8 56

= 3000 − 428 − 375 + 53 = 2250

Corollary 1:- Let 𝐴, 𝐵 𝑎𝑛𝑑 𝐶 be three finite sets.
Then |𝐴 ∪ 𝐵 ∪ 𝐶| = |𝐴| + |𝐵| + |𝐶| − |𝐴 ∩ 𝐵| − |𝐴 ∩ 𝐶| − |𝐵 ∩ 𝐶| + |𝐴 ∩ 𝐵 ∩ 𝐶|
3.2 Definition and examples of recurrence relation
Definition 1:- A recurrence relation for a sequence {𝑎𝑛 }∞
𝑛=0 is an equation that expresses 𝑎𝑛 in terms of

one or more preceding terms 𝑎0 , 𝑎1 , … , 𝑎𝑛−2 , 𝑎𝑛−1 . Moreover, the sequence is called the solution to the
recurrence relation if it satisfies the recurrence relation.
The following are examples of recurrence relations :
𝑎𝑛 = 2𝑎𝑛−1 + 1 , 𝑛 ≥ 2 … … … … . (1)
𝑎𝑛 = 5𝑎𝑛−1 − 6𝑎𝑛−2 , 𝑛 ≥ 3 … … … … … … (2)
For (1) we would need one initial value to find a particular or single 𝑎𝑛 . For example, if 𝑎0 = 1 then
𝑎1 = 3 and 𝑎2 = 7.
For (2) we would need two initial values to find a particular or single 𝑎𝑛 . For example, if 𝑎0 = 1 and
𝑎1 = 5 then 𝑎2 = 19 and 𝑎3 = 65.
Example 1:- Verify that the solution of the recurrence relation 𝑎𝑛 = 2𝑎𝑛−1 + 1 , 𝑛 ≥ 2 with 𝑎0 = 0
is 𝑎𝑛 = 2𝑛 − 1
Solution: We have to do two things
(a) Check that the given formula gives the correct initial value
(b) Check that the given formula solves the recurrence relation.
Putting 𝑛 = 0 in 𝑎𝑛 = 2𝑛 − 1 gives 𝑎0 = 1 − 1 as required.
To do (b) we evaluate 2𝑎𝑛−1 + 1 using the given formula and show that it is equal to 𝑎𝑛 .
Now 𝑎𝑛−1 = 2𝑛−1 – 1 so
2𝑎𝑛−1 + 1 = 2(2𝑛−1 – 1) + 1 = 2𝑛 – 1
Recurrence relations have many applications. Suppose that you put £100 into a savings account yielding
4% compounded annually. Let 𝑎𝑛 be the amount (in pounds) in the account after 𝑛 years. Then 𝑎𝑛 is
equal to the amount in the account after 𝑛 − 1 years plus the interest for the 𝑛th year. For example, 𝑎1
is equal to 100 plus the interest which is 4. Hence 𝑎1 = 104.

Hu 2|Page
Discrete Mathematics and Combinatorics 2024
In general, 𝑎𝑛 = 𝑎𝑛−1 + (0.04)𝑎𝑛−1 so that
𝑎𝑛 = (1.04)𝑎𝑛−1 , 𝑛 ≥ 1
with 𝑎0 = 100.
Solving this we obtain
𝑎1 = 100(1.04)
𝑎2 = (1.04)𝑎1 = 100(1.04)2
𝑎3 = (1.04)𝑎2 = 100(1.04)3
and in general
𝑎𝑛 = 100(1.04)𝑛 .
3.3 Linear recurrence relation with constant coefficient

A wide variety of recurrence relations occur in models. Some of those recurrence relations can be solved
using iteration or some other technique. However, one important class of recurrence relation can be
explicitly solved in a systematic way. These are recurrence relations that express the terms of the
sequence as linear combination of previous terms.
Definition 1:- A linear recurrence relation with constant coefficient of degree (order) 𝑘 is a recurrence
relation of the form
𝑎𝑛 + 𝑐1 𝑎𝑛−1 + 𝑐2 𝑎𝑛−2 + ⋯ + 𝑐𝑘 𝑎𝑛−𝑘 = 𝑓(𝑛) … … … … … (1)
where 𝑐1 , 𝑐2 , … , 𝑐𝑘 are constants and 𝑐𝑘 ≠ 0.
If 𝑓(𝑛) is identically zero (𝑓(𝑛) = 0) in the recurrence relation (1) defined above, then the recurrence
relation (1) is called homogeneous, otherwise it is called non-homogeneous.

3.4. Solution of linear recurrence relation with constant coefficient

Solving linear homogeneous recurrence relation with constant coefficient.

The basic approach for solving linear homogeneous recurrence relations is to look for the solutions of
the form 𝑎𝑛 = 𝑟 𝑛 , where 𝑟 is constant. Note that 𝑎𝑛 = 𝑟 𝑛 is the solution of the recurrence relation
𝑎𝑛 + 𝑐1 𝑎𝑛−1 + 𝑐2 𝑎𝑛−2 + ⋯ + 𝑐𝑘 𝑎𝑛−𝑘 = 0 … … … … (2)
if and only if
𝑟 𝑛 + 𝑐1 𝑟 𝑛−1 + 𝑐2 𝑟 𝑛−2 + ⋯ + 𝑐𝑘 𝑟 𝑛−𝑘 = 0.
When both side of the equation is divided by 𝑟 𝑛−𝑘 we obtain the equation
Hu 3|Page
Discrete Mathematics and Combinatorics 2024
𝑟 𝑘 + 𝑐1 𝑟 𝑘−1 + 𝑐2 𝑟 𝑘−2 + ⋯ + 𝑐𝑘−1 𝑟 + 𝑐𝑘 = 0 . …………… (3)
Consequently the sequence {𝑎𝑛 }∞ 𝑛
𝑛=0 with 𝑎𝑛 = 𝑟 is the solution if and only if 𝑟 is the solution of the

last equation (3), which is called the characteristic equation of the recurrence relation (2). The solutions
of the characteristic equation (3) are called characteristic roots of the recurrence relation (2). As we
will see, these characteristic roots can be used to give an explicit formula for all the solutions of the
recurrence relation (2).
Let us first see the rule to find all the possible solutions (general solution) homogeneous recurrence
relation with constant coefficients of degree 1.
All the possible solutions or general solution to the linear homogenous recurrence relation with
constant coefficient of degree 1
𝑎𝑛 + 𝑐𝑎𝑛−1 = 0
is 𝑎𝑛 = 𝑝(−𝑐)𝑛 , where 𝑝 is a constant.
Example 1:- Find the solution of the recurrence relation
𝑎𝑛 − 5𝑎𝑛−1 = 0
with initial condition 𝑎0 = 7
Solution. The general solution is 𝑎𝑛 = 𝑝(5𝑛 ) .
Since 𝑎0 = 7,
⟹ 𝑎0 = 𝑝(50 ) = 7
Thus,
𝑝 = 7 and hence the solution is 𝑎𝑛 = 7(5𝑛 ) .
Now we will develop rules that deal with linear homogeneous recurrence relation with constant
coefficients of degree 2. Then corresponding general rules when the degree may be greater that two will
be stated.
Theorem 1:- Consider a linear homogeneous recurrence relation with constant coefficient of degree 2
𝑎𝑛 + 𝑐1 𝑎𝑛−1 + 𝑐2 𝑎𝑛−2 = 0 … … … …. (4)
for 𝑛 ≥ 2, where 𝑐1 and 𝑐2 are constants, and consider its characteristic equation
𝑟 2 + 𝑐1 𝑟 + 𝑐2 = 0 . … … … ..(5)
i. If the characteristic equation (5) has two distinct roots 𝑟1 and 𝑟2 , then the sequence {𝑎𝑛 }∞
𝑛=0 is the

solution of the recurrence relation (4) if and only if

𝑎𝑛 = 𝑑1 𝑟1 𝑛 + 𝑑2 𝑟2 𝑛 … … … … … … …(6)

Hu 4|Page
Discrete Mathematics and Combinatorics 2024
where 𝑑1 and 𝑑1 are constants.
ii. If the characteristic equation (5) has only one root 𝑟0 , then the sequence {𝑎𝑛 }∞
𝑛=0 is the solution of

the recurrence relation (4) if and only if

𝑎𝑛 = 𝑑1 𝑟0 𝑛 + 𝑑2 𝑛 𝑟0 𝑛 … … … … … … .. (7)
where 𝑑1 and 𝑑1 are constants.
Example 2:- Find the general solution of
𝑎𝑛 − 𝑎𝑛−1 − 2𝑎𝑛−2 = 0 , for 𝑛 ≥ 2
Solution: The characteristic equation of the given recurrence relation is 𝑟 2 − 𝑟 − 2 = 0.
Then, find the roots of the characteristic equation using quadratic formula (factorization).
𝑟2 − 𝑟 − 2 = 0
⇒ (𝑟 + 1)(𝑟 − 2) = 0
So 𝑟 = −1 and 𝑟 = 2. Thus, the characteristic equation has two distinct roots 𝑟 = −1 and 𝑟 = 2
Hence, the general solution is
𝑎𝑛 = 𝑑1 (−1)𝑛 + 𝑑2 (2)𝑛
where 𝑑1 and 𝑑2 are constants.
Example 3:- Find the solution of
𝑎𝑛 = −7𝑎𝑛−1 − 12𝑎𝑛−2 , for 𝑛 ≥ 2
with initial condition 𝑎1 = 0 and 𝑎1 = 5.
Solution: 𝑎𝑛 = −7𝑎𝑛−1 − 12𝑎𝑛−2
⇒ 𝑎𝑛 + 7𝑎𝑛−1 + 12𝑎𝑛−2 = 0
Thus, the characteristic equation is
𝑟 2 + 7𝑟 + 12 = 0.
And finding the roots of the characteristic equation using quadratic formula or factorization, we have
𝑟 = 3 and = 4 .
Hence, the general solution is
𝑎𝑛 = 𝑑1 (3)𝑛 + 𝑑2 (4)𝑛 , where 𝑑1 and 𝑑2 are constants.
Putting 𝑛 = 0 and 𝑛 = 1 in 𝑎𝑛 = 𝑑1 (3)𝑛 + 𝑑2 (4)𝑛 and using the initial conditions gives, we have
𝑑1 + 𝑑2 = 0 and
3𝑑1 + 4𝑑2 = 5.
Solving these gives 𝑑1 = −5 and 𝑑2 = 5.

Hu 5|Page
Discrete Mathematics and Combinatorics 2024
Hence,
𝑎𝑛 = −5(3)𝑛 + 5(4)𝑛 is the solution.
Example 4:- Find the solution of
9
𝑎𝑛 − 3𝑎𝑛−1 + 4 𝑎𝑛−2 = 0 , for 𝑛 ≥ 2

with 𝑎0 = 1 and 𝑎1 = 10.

Solution: The characteristic equation of the given recurrence relation is
9
𝑟 2 − 3𝑟 + 4 = 0. Finding the roots of the characteristic equation using quadratic formula
9
3±√32 −4(1)( ) 3±√9−9 3
4
𝑟= = =2.
2(1) 2
3
So the characteristic equation has double root 𝑟 = 2 . Hence, the general solution is
3 𝑛 3 𝑛
𝑎𝑛 = 𝑑1 (2 ) + 𝑑2 𝑛 (2 ) ,where 𝑑1 and 𝑑2 are constants.
3 𝑛 3 𝑛
Putting 𝑛 = 0 and 𝑛 = 1 in 𝑎𝑛 = 𝑑1 (2 ) + 𝑑2 𝑛 (2 ) and using the initial conditions gives, we have
3 3
𝑑1 = 1 and 𝑑1 + 2 𝑑2 = 10.
2
17
Solving these gives 𝑑1 = 1 and 𝑑2 = .
3
3 𝑛 17 3 𝑛
Hence, 𝑎𝑛 = (2 ) + 𝑛 (2 ) is the solution.
3

We will now state the general result about the solution of linear homogeneous recurrence relation with
constant coefficients of degree 𝑘, where the degree 𝑘 ≥ 2 under the assumption that the characteristic
equation has 𝑘 distinct roots 𝑟1 , 𝑟2 , … , 𝑟𝑘 or the characteristic equation has t distinct roots 𝑟1 , 𝑟2 , … , 𝑟𝑡
with multiplicity 𝑚1 , 𝑚2 , … , 𝑚𝑡 respectively, so that 𝑚𝑖 ≥ 1, for 𝑖 = 1,2, … , 𝑡 and 𝑚1 + 𝑚2 + ⋯ +
𝑚𝑡 = 𝑘.
Theorem 2:- Consider the linear homogeneous recurrence relation with constant coefficient of degree
k 𝑎𝑛 + 𝑐1 𝑎𝑛−1 + 𝑐2 𝑎𝑛−2 + ⋯ + 𝑐𝑘 𝑎𝑛−𝑘 = 0 ………… (8)
and consider its characteristic equation I
𝑟 𝑘 + 𝑐1 𝑟 𝑘−1 + 𝑐2 𝑟 𝑘−2 + ⋯ + 𝑐𝑘−1 𝑟 + 𝑐𝑘 = 0. … … … .. (9)
i. If the characteristic equation (9) has 𝑘 distinct roots 𝑟1 , 𝑟2 , … , 𝑟𝑘 , then the sequence {𝑎𝑛 }∞
𝑛=0 is

the solution of the recurrence relation (8) if and only if

𝑎𝑛 = 𝑑1 𝑟1 𝑛 + 𝑑2 𝑟2 𝑛 + ⋯ + 𝑑𝑘 𝑟𝑘 𝑛 … … .. (10) where 𝑑1 , 𝑑2 , … , 𝑑𝑘 are constants.

Hu 6|Page
Discrete Mathematics and Combinatorics 2024
ii. If the characteristic equation (9) has t distinct roots 𝑟1 , 𝑟2 , … , 𝑟𝑡 with multiplicity 𝑚1 , 𝑚2 , … , 𝑚𝑡
respectively, so that 𝑚𝑖 ≥ 1, for 𝑖 = 1,2, … , 𝑡 and 𝑚1 + 𝑚2 + ⋯ + 𝑚𝑡 = 𝑘, then the sequence
{𝑎𝑛 }∞
𝑛=0 is the solution of the recurrence relation (8) if and only if

𝑎𝑛 = (𝛼10 + 𝛼11 𝑛 + ⋯ + 𝛼1(𝑚1 −1) 𝑛𝑚1 −1 )𝑟1𝑛 + (𝛼20 + 𝛼21 𝑛 + ⋯ + 𝛼2(𝑚2 −1) 𝑛𝑚2 −1 )𝑟2 𝑛 + ⋯ +
(𝛼𝑡0 + 𝛼𝑡1 𝑛 + ⋯ + 𝛼𝑡(𝑚𝑡−1) 𝑛𝑚𝑡 −1 )𝑟𝑡 𝑛 … … … … … .. (11)
where 𝛼𝑖𝑗 are constants for 0 ≤ 𝑖 ≤ 𝑡 and 0 ≤ 𝑗 ≤ 𝑚𝑖 − 1.
Note that: The solution (10) or (11) are all possible solutions of the recurrence relation (8). And we
call the solution general solution of the recurrence relation (8).
Example 5:- Find the general solution of the recurrence relation
3 23
𝑎𝑛 + 2 𝑎𝑛−1 − 𝑎𝑛−2 + 28𝑎𝑛−3 − 10𝑎𝑛−4 = 0 , for 𝑛 ≥ 4.
2

Solution: The characteristic equation the given recurrence relation is

3 23 2
𝑟4 + 2 𝑟3 − 𝑟 + 28𝑟 − 10 = 0.
2
1
⟹ (𝑟 − 2)2 (𝑟 − 2) (𝑟 + 5) = 0
1 1
So that 𝑟 = 2 , 𝑟 = 2 and 𝑟 = −5 with the multiplicity of 2 is 2, the multiplicity of is 2 and the
2

multiplicity of −5 is 1.
Hence the general solution of the recurrence relation
3 23
𝑎𝑛 + 2 𝑎𝑛−1 − 𝑎𝑛−2 + 28𝑎𝑛−3 − 10𝑎𝑛−4 = 0 , for 𝑛 ≥ 4
2
1 𝑛
is 𝑎𝑛 = (𝑑1 + 𝑑2 𝑛)(2 )𝑛 + 𝑑3 (2) + 𝑑3 (−5)𝑛 where 𝑑1 , 𝑑2 , 𝑑3 and 𝑑4 are constants.

Solving linear non-homogeneous recurrence relation with constant coefficient

We have seen how to solve linear homogeneous recurrence relation with constant coefficients. Is there
a relatively simple technique for solving a linear, but not homogeneous, recurrence relation with constant
coefficients, such as 𝑎𝑛 = 3𝑎𝑛−1 + 2𝑛 ? We will see that the answer is yes for a certain family of such
recurrence relations.
The recurrence relation 𝑎𝑛 = 3𝑎𝑛−1 + 2𝑛 is an example of linear nonhomogeneous recurrence
relations with constant coefficients, that is recurrence relation of the form
𝑎𝑛 + 𝑐1 𝑎𝑛−1 + 𝑐2 𝑎𝑛−2 + ⋯ + 𝑐𝑘 𝑎𝑛−𝑘 = 𝑓(𝑛)

Hu 7|Page
Discrete Mathematics and Combinatorics 2024
where 𝑐1 , 𝑐2 , … , 𝑐𝑘 are constants and 𝑐𝑘 ≠ 0 and 𝑓(𝑛) is a function not identically zero depending only
on 𝑛. The recurrence relation
𝑎𝑛 + 𝑐1 𝑎𝑛−1 + 𝑐2 𝑎𝑛−2 + ⋯ + 𝑐𝑘 𝑎𝑛−𝑘 = 0
is called the associated homogenous recurrence relation. It plays an important role in the solution of the
non-homogeneous recurrence relation.
Theorem 3:- Consider the linear non-homogeneous recurrence relations with constant coefficients of
degree 𝑘
𝑎𝑛 + 𝑐1 𝑎𝑛−1 + 𝑐2 𝑎𝑛−2 + ⋯ + 𝑐𝑘 𝑎𝑛−𝑘 = 𝑓(𝑛) … … … .. (12)
and its associated homogenous recurrence relation
𝑎𝑛 + 𝑐1 𝑎𝑛−1 + 𝑐2 𝑎𝑛−2 + ⋯ + 𝑐𝑘 𝑎𝑛−𝑘 = 0 … … … …. (13)
∞
Then every solution of the recurrence relation (12) is of the form {𝑎𝑛𝑝 + 𝑎𝑛ℎ }𝑛=0 , where 𝑎𝑛𝑝 is the

particular solution of the recurrence relation (12) and 𝑎𝑛ℎ is the solution of the recurrence relation (13).
Problem: How can we find or choose the particular solution 𝑎𝑛𝑝 for the linear nonhomogeneous
recurrence relation (12)?
𝑓(𝑛) Choice of 𝑎𝑛𝑝
𝑞𝑚 𝑛𝑚 + 𝑞𝑚−1 𝑛𝑛−1 + ⋯ + 𝑞1 𝑛 + 𝑞0 𝑝𝑚 𝑛𝑚 + 𝑝𝑚−1 𝑛𝑛−1 + ⋯ + 𝑝1 𝑛 + 𝑝0
𝛼(𝑏 𝑛 ) 𝛽(𝑏 𝑛 )
(𝑞𝑚 𝑛𝑚 + 𝑞𝑚−1 𝑛𝑛−1 + ⋯ + 𝑞1 𝑛 + 𝑞0 )𝑏 𝑛 (𝑝𝑚 𝑛𝑚 + 𝑝𝑚−1 𝑛𝑛−1 + ⋯ + 𝑝1 𝑛 + 𝑝0 )𝑏 𝑛

Rules:
If 𝑓(𝑛) is one of the terms on the left side of the table choose the particular solution 𝑎𝑛𝑝 from the right
side of the table and determine the underdetermined coefficients by using the original equation in (12).
If 𝑏 is the root of the characteristic equation to the recurrence relation (13) with multiplicity 𝑚, then
multiply 𝑎𝑛𝑝 by 𝑛𝑚 .
That is if 𝑏 is the root of the characteristic equation to the recurrence relation (13) with multiplicity
𝑚, choose the particular solution 𝑎𝑛𝑝 = 𝛽𝑛𝑚 (𝑏 𝑛 ) for the case
𝑓(𝑛) = 𝛼(𝑏 𝑛 ) and choose the particular solution
𝑎𝑛𝑝 = 𝑛𝑚 (𝑝𝑚 𝑛𝑚 + 𝑝𝑚−1 𝑛𝑛−1 + ⋯ + 𝑝1 𝑛 + 𝑝0 )𝑏 𝑛
for the case 𝑓(𝑛) = (𝑞𝑚 𝑛𝑚 + 𝑞𝑚−1 𝑛𝑛−1 + ⋯ + 𝑞1 𝑛 + 𝑞0 )𝑏 𝑛 .

Hu 8|Page
Discrete Mathematics and Combinatorics 2024
Example 6:-Find a particular solution of the recurrence relation
𝑎𝑛 − 4𝑎𝑛−1 = − 15 , for 𝑛 ≥ 1
Solution. The given recurrence relation is of the form 𝑎𝑛 − 4𝑎𝑛−1 = 𝑓(𝑛) , where 𝑓(𝑛) = −15.
We choose particular solution 𝑎𝑛𝑝 = 𝑞 , where 𝑞 is a constant.
Then, we have to find 𝑞 by substituting 𝑎𝑛𝑝 in to the given recurrence relation, that is
𝑎𝑛𝑝 − 4𝑎𝑛−1
𝑝
= − 15.
Observe that 𝑎𝑛𝑝 = 𝑞 and 𝑎𝑛−1
𝑝
= 𝑞. Thus, we have −4𝑞 = − 15 .
⟹ −3𝑞 = −15 ⟹𝑞=5
𝑝
Hence, 𝑎𝑛 = 5 is the particular solution of the recurrence relation.
Example 7:- Find a particular solution of the recurrence relation
𝑎𝑛 = 6𝑎𝑛−1 + 7𝑎𝑛−2 + 7𝑛 , for 𝑛 ≥ 2
Solution.
The given recurrence relation is of the form 𝑎𝑛 − 6𝑎𝑛−1 − 7𝑎𝑛−2 = 𝑓(𝑛) , where 𝑓(𝑛) = 7𝑛 .
The associated homogeneous recurrence relation to the given recurrence relation is
𝑎𝑛 − 6𝑎𝑛−1 − 7𝑎𝑛−2 = 0
and its characteristic equation is 𝑟 2 − 6𝑟 − 7 = 0.
Thus,
6±√(−6)2 −4(1)(−7) 6±√64 6±8
𝑟= = =
2(1) 2 2

So 𝑟 = 7 and 𝑟 = −1.
𝑓(𝑛) = 7𝑛 , and 𝑏 = 7 is the root of the characteristic equation with multiplicity 1. Thus we choose
particular solution 𝑎𝑛𝑝 = 𝑞𝑛(7𝑛 ) , where 𝑞 is a constant.
Then, we have to find 𝑞 by substituting 𝑎𝑛𝑝 in to the given recurrence relation, that is
𝑎𝑛𝑝 − 6𝑎𝑛−1
𝑝 𝑝
− 7𝑎𝑛−2 = 7𝑛 .
Observe that 𝑎𝑛𝑝 = 𝑞𝑛(7𝑛 ) , 𝑎𝑛−1
𝑝 𝑝
= 𝑞(𝑛 − 1)(7𝑛−1 ) and 𝑎𝑛−2 = 𝑞(𝑛 − 2)(7𝑛−2 ) .
Thus,
[𝑞𝑛(7𝑛 )] − 6[𝑞(𝑛 − 1)(7𝑛−1 )] − 7[𝑞(𝑛 − 2)(7𝑛−2 )] = 7𝑛
⟹ 𝑞𝑛(7𝑛 ) − 6𝑞𝑛7𝑛−1 + 6𝑞7𝑛−1 − 7𝑞𝑛7𝑛−2 + 14𝑞7𝑛−2 = 7𝑛

Hu 9|Page
Discrete Mathematics and Combinatorics 2024
6 6 1 2
⟹ 𝑞𝑛(7𝑛 ) − 7 𝑞𝑛(7𝑛 ) + 7 𝑞(7𝑛 ) − 7 𝑞𝑛(7𝑛 ) + 7 𝑞7𝑛−2 = 7𝑛
8 8 7
⟹ 𝑞(7𝑛 ) = 7𝑛 ⟺ 7𝑞 = 1 ⟺ 𝑞 = 8
7
7
Hence, 𝑎𝑛𝑝 = 8 𝑛(7𝑛 ) is the particular solution of the recurrence relation.

Example 8:- . Find the general solution of the recurrence relation

𝑎𝑛 = 𝑎𝑛−1 + 𝑎𝑛−2 + 5𝑛 − 6 , for 𝑛 ≥ 2
Solution. 𝑎𝑛 = 𝑎𝑛−1 + 𝑎𝑛−2 + 5𝑛 − 6
⟹ 𝑎𝑛 − 𝑎𝑛−1 − 𝑎𝑛−2 = 5𝑛 − 6
⟹ 𝑎𝑛 − 𝑎𝑛−1 − 𝑎𝑛−2 = 𝑓(𝑛) , where 𝑓(𝑛) = 5𝑛 − 6
The associated homogeneous recurrence relation to the given recurrence relation is
𝑎𝑛 − 𝑎𝑛−1 − 𝑎𝑛−2 = 0
and its characteristic equation is 𝑟 2 − 𝑟 − 1 = 0.
Thus,
1±√(−1)2 −4(1)(−1) 1±√5
𝑟= =
2(1) 2

1+√5 1−√5
So 𝑟 = and 𝑟 = .
2 2

Hence, the general solution to the associated homogeneous recurrence relation is

𝑛 𝑛
𝑔 1+√5 1−√5
𝑎𝑛 = 𝑑1 ( ) + 𝑑2 ( )
2 2

where 𝑑1 and 𝑑2 are constants.

𝑓(𝑛) = 5𝑛 − 6, so we choose the particular solution to the given nonhomogeneous recurrence relation
to be 𝑎𝑛𝑝 = 𝑞1 𝑛 + 𝑞2 , where 𝑞1 and 𝑞2 are constants to be determined by substituting 𝑎𝑛𝑝 in to the
given recurrence relation.
Thus,
𝑎𝑛𝑝 − 𝑎𝑛−1
𝑝 𝑝
and 𝑎𝑛𝑝 = 𝑞1 𝑛 + 𝑞2 , 𝑎𝑛−1
𝑝 𝑝
− 𝑎𝑛−2 = 𝑓(𝑛). = 𝑞1 (𝑛 − 1) + 𝑞2 and 𝑎𝑛−2 = 𝑞1 (𝑛 − 2) +
𝑞2 . Thus,
𝑎𝑛𝑝 − 𝑎𝑛−1
𝑝 𝑝
− 𝑎𝑛−2 = 𝑓(𝑛)
⟹ (𝑞1 𝑛 + 𝑞2 )– (𝑞1 (𝑛 − 1) + 𝑞2 ) − (𝑞1 (𝑛 − 2) + 𝑞2 ) = 𝑓(𝑛)
⟹ 𝑞1 𝑛 + 𝑞2 − 𝑞1 𝑛 + 𝑞1 − 𝑞2 − 𝑞1 𝑛 + 2𝑞1 − 𝑞2 = 5𝑛 − 6
⟹ −𝑞1 𝑛 + (𝑞2 + 3𝑞1 ) = 5𝑛 − 6

Hu 10 | P a g e
Discrete Mathematics and Combinatorics 2024
⟺ −𝑞1 = 5 and 𝑞2 + 3𝑞1 = −6
Thus, 𝑞1 = −5 and 𝑞2 = 9.
Hence, the particular solution to the given nonhomogeneous recurrence relation is
𝑎𝑛𝑝 = −5𝑛 + 9.
Therefore, the general solution to the non-homogeneous recurrence relation
𝑔
𝑎𝑛 = 𝑎𝑛−1 + 𝑎𝑛−2 + 5𝑛 − 6 is 𝑎𝑛 = 𝑎𝑛 + 𝑎𝑛𝑝 .
That is the general solution to the non-homogeneous recurrence relation
𝑎𝑛 = 𝑎𝑛−1 + 𝑎𝑛−2 + 5𝑛 − 6 is
𝑛 𝑛
1+√5 1−√5
𝑎𝑛 = 𝑑1 ( ) + 𝑑2 ( ) − 5𝑛 + 9 where 𝑑1 and 𝑑2 are constants.
2 2

Example 9:- Find the solution of the recurrence relation

𝑎𝑛 − 6𝑎𝑛−1 + 9𝑎𝑛−2 = 2(3𝑛 ) , for 𝑛 ≥ 2
with initial condition 𝑎0 = −1 and 𝑎1 = 5.
Solution. We are given a recurrence relation
𝑎𝑛 − 6𝑎𝑛−1 + 9𝑎𝑛−2 = 𝑓(𝑛), where 𝑓(𝑛) = 2(3𝑛 ).
The associated homogeneous recurrence relation to the given recurrence relation is
𝑎𝑛 − 6𝑎𝑛−1 + 9𝑎𝑛−2 = 0
and its characteristic equation is 𝑟 2 − 6𝑟 + 9 = 0.
Thus, 𝑟 2 − 6𝑟 + 9 = 0
⟹ (𝑟 − 3)2 = 0
So the characteristic equation has double root and is 𝑟 = 3.
Hence, the general solution to the associated homogeneous recurrence relation is
𝑔
𝑎𝑛 = 𝑑1 (3 )𝑛 + 𝑑2 𝑛(3)𝑛
where 𝑑1 and 𝑑2 are constants.
𝑓(𝑛) = 2(3𝑛 ), and 𝑏 = 3 is the root of the characteristic equation and the multiplicity of 3 is 2, so we
𝑝
choose the particular solution to the given nonhomogeneous recurrence relation to be 𝑎𝑛 = 𝑞𝑛2 (3𝑛 ) ,
where 𝑞 is constant to be determined by substituting 𝑎𝑛𝑝 in to the given recurrence relation.
𝑎𝑛𝑝 − 6𝑎𝑛−1
𝑝 𝑝
= 2(3𝑛 ) . But, 𝑎𝑛𝑝 = 𝑞𝑛2 (3𝑛 ), 𝑎𝑛−1
𝑝
That is + 9𝑎𝑛−2 = 𝑞(𝑛 − 1)2 (3𝑛−1 )

Hu 11 | P a g e
Discrete Mathematics and Combinatorics 2024
𝑝
and 𝑎𝑛−2 = 𝑞(𝑛 − 2)2 (3𝑛−2 ).
Thus,
𝑎𝑛𝑝 − 6𝑎𝑛−1
𝑝 𝑝
+ 9𝑎𝑛−2 = 2(3𝑛 )
⟹ [𝑞𝑛2 (3𝑛 )] − 6[𝑞(𝑛 − 1)2 (3𝑛−1 )] + 9[𝑞(𝑛 − 2)2 (3𝑛−2 )] = 2(3𝑛 )
⟹ 𝑞𝑛2 (3𝑛 ) − 6[𝑞(𝑛2 − 2𝑛 + 1)(3𝑛−1 )] +9[𝑞(𝑛2 − 4𝑛 + 4)(3𝑛−2 )] = 2(3𝑛 )
⟹ 𝑞𝑛2 (3𝑛 ) − 6𝑞𝑛2 (3𝑛−1 ) + 12𝑞𝑛(3𝑛−1 ) − 6𝑞(3𝑛−1 ) + 9𝑞𝑛2 (3𝑛−2 ) − 36𝑞𝑛(3𝑛−2 ) +
36𝑞(3𝑛−2 ) = 2(3𝑛 )
⟹ 𝑞𝑛2 (3𝑛 ) − 2𝑞𝑛2 (3𝑛 ) + 4𝑞𝑛(3𝑛 ) − 2𝑞(3𝑛 ) + 𝑞𝑛2 (3𝑛 ) − 4𝑞𝑛(3𝑛 ) + 4𝑞(3𝑛 ) = 2(3𝑛 )
⟹ 2𝑞3𝑛 = 2(3𝑛 ) ⟺ 𝑞 = 1
Hence, the particular solution to the given nonhomogeneous recurrence relation is
𝑎𝑛𝑝 = 𝑛2 (3𝑛 ).
Therefore, the general solution to the nonhomogeneous recurrence relation 𝑎𝑛 − 6𝑎𝑛−1 + 9𝑎𝑛−2 =
𝑔
2(3𝑛 ) is 𝑎𝑛 = 𝑎𝑛 + 𝑎𝑛𝑝 .
That is the general solution to the nonhomogeneous recurrence relation 𝑎𝑛 − 6𝑎𝑛−1 + 9𝑎𝑛−2 = 2(3𝑛 )
is 𝑎𝑛 = 𝑑1 (3𝑛 ) + 𝑑2 𝑛(3𝑛 ) + 𝑛2 (3𝑛 ) where 𝑑1 and 𝑑2 are constants.
Then, putting 𝑛 = 0 and 𝑛 = 1 in 𝑎𝑛 = 𝑑1 (3𝑛 ) + 𝑑2 𝑛(3𝑛 ) + 𝑛2 (3𝑛 ) and using the initial conditions
gives, we have
𝑑1 = −1 and
3𝑑1 + 3𝑑2 + 3 = 5.
That is 𝑑1 = −1 and 3𝑑1 + 3𝑑2 = 2.
5
Solving these gives 𝑑1 = −1 and 𝑑2 = 3.

Hence,
5
𝑎𝑛 = −(3𝑛 ) + 3 𝑛(3𝑛 ) + 𝑛2 (3𝑛 )

is the solution.
Example 10:- Find the general solution of the recurrence relation
𝑎𝑛 + 9𝑎𝑛−1 + 20𝑎𝑛−2 = (𝑛2 + 𝑛 − 1 )5𝑛 , for 𝑛 ≥ 2
Solution. We are given a recurrence relation
𝑎𝑛 − 10𝑎𝑛−1 + 25𝑎𝑛−2 = 𝑓(𝑛), where 𝑓(𝑛) = (𝑛2 + 𝑛 − 1 )5𝑛 .
The associated homogeneous recurrence relation to the given recurrence relation is

Hu 12 | P a g e
Discrete Mathematics and Combinatorics 2024
𝑎𝑛 − 10𝑎𝑛−1 + 25𝑎𝑛−2 = 0
and its characteristic equation is 𝑟 2 − 10𝑟 + 25 = 0.
Thus, 𝑟 2 − 10𝑟 + 25 = 0
⟹ (𝑟 − 5)2 = 0
So the characteristic equation has double roots and is 𝑟 = 5.
Hence, the general solution to the associated homogeneous recurrence relation is
𝑔
𝑎𝑛 = 𝑑1 (5 )𝑛 + 𝑑2 𝑛(5)𝑛
where 𝑑1 and 𝑑2 are constants.
𝑓(𝑛) = (𝑛2 + 𝑛 − 1 )5𝑛 , and 𝑏 = 5 is the root of the characteristic equation and the multiplicity of 5 is
2, so we choose the particular solution to the given nonhomogeneous recurrence relation to be 𝑎𝑛𝑝 =
𝑛2 (𝑞2 𝑛2 + 𝑞1 𝑛 + 𝑞0 )5𝑛 , where 𝑞2 , 𝑞1 and 𝑞0 are constants to be determined by substituting 𝑎𝑛𝑝 in to
the given recurrence relation.
𝑎𝑛𝑝 − 10𝑎𝑛−1
𝑝 𝑝
That is + 25𝑎𝑛−2 = (𝑛2 + 𝑛 − 1 )5𝑛 .
But, 𝑎𝑛𝑝 = 𝑛2 (𝑞2 𝑛2 + 𝑞1 𝑛 + 𝑞0 )5𝑛 , 𝑎𝑛−1
𝑝
= (𝑛 − 1)2 (𝑞2 (𝑛 − 1)2 + 𝑞1 (𝑛 − 1) + 𝑞0 )5𝑛−1 and
𝑝
𝑎𝑛−2 = (𝑛 − 2)2 (𝑞2 (𝑛 − 2)2 + 𝑞1 (𝑛 − 2) + 𝑞0 )5𝑛−2.
Thus,
𝑝 𝑝 𝑝
𝑎𝑛 − 10𝑎𝑛−1 + 25𝑎𝑛−2 = (𝑛2 + 𝑛 − 1 )5𝑛
⟹ [𝑛2 (𝑞2 𝑛2 + 𝑞1 𝑛 + 𝑞0 )5𝑛 ] − 10[(𝑛 − 1)2 (𝑞2 (𝑛 − 1)2 + 𝑞1 (𝑛 − 1) + 𝑞0 )5𝑛−1 ] +
25[(𝑛 − 2)2 (𝑞2 (𝑛 − 2)2 + 𝑞1 (𝑛 − 2) + 𝑞0 )5𝑛−2 ] = (𝑛2 + 𝑛 − 1 )5𝑛
The rest of the steps of the solution are left as an exercise.
Example: - Find the general solution of the recurrence relation
𝑎𝑛 − 𝑎𝑛−1 − 10𝑎𝑛−2 + 8𝑎𝑛−3 = 𝑓(𝑛) , for 𝑛 ≥ 3
where a. 𝑓(𝑛) = 6𝑛 b. 𝑓(𝑛) = (−1)𝑛 (4)𝑛
Solution. The associated homogeneous recurrence relation to the given recurrence relation is 𝑎𝑛 −
𝑎𝑛−1 − 10𝑎𝑛−2 + 8𝑎𝑛−3 = 0 , for 𝑛 ≥ 3
and its characteristic equation is 𝑟 3 − 𝑟 2 − 10𝑟 + 8 = 0.
Thus
𝑟 3 − 𝑟 2 − 10𝑟 + 8 = 0
⟹ (𝑟 − 1)(𝑟 − 2)(𝑟 + 4) = 0

Hu 13 | P a g e
Discrete Mathematics and Combinatorics 2024
⟺ 𝑟 = 1 , 𝑟 = 2 , 𝑟 = −4
So the characteristic equation three distinct root 𝑟 = 1 , 𝑟 = 2 and 𝑟 = −4.
Hence, the general solution to the associated homogeneous recurrence relation is
𝑔
𝑎𝑛 = 𝑑1 (1 )𝑛 + 𝑑2 (2)𝑛 + 𝑑3 (−4)𝑛
where 𝑑1 , 𝑑2 and 𝑑3 are constants.
a. 𝑓(𝑛) = 6𝑛, so we choose the particular solution to the given non-homogeneous recurrence
relation to be 𝑎𝑛𝑝 = 𝑞1 𝑛 + 𝑞0 , where 𝑞1 and 𝑞0 are constants to be determined by substituting
𝑎𝑛𝑝 in to the given recurrence relation.

Thus,
𝑎𝑛𝑝 − 𝑎𝑛−1
𝑝 𝑝 𝑝
− 10𝑎𝑛−2 + 8𝑎𝑛−3 = 𝑓(𝑛) , where 𝑓(𝑛) = 6𝑛
⟹ [𝑞1 (𝑛 − 1) + 𝑞0 ] − [𝑞1 𝑛 + 𝑞0 ] − 10[𝑞1 (𝑛 − 2) + 𝑞0 ] + 8[𝑞1 (𝑛 − 3) + 𝑞0 ] = 6𝑛
⟹ −2𝑞1 𝑛 − 3𝑞1 − 𝑞0 = 6𝑛
⟺ −2𝑞1 = 6 and −3𝑞1 − 𝑞0 = 0
⟺ 𝑞1 = −3 and 𝑞0 = 9
Thus, 𝑎𝑛𝑝 = −3𝑛 + 9 is the particular solution of the given recurrence relation.
Hence, the general solution is
𝑎𝑛 = 𝑑1 (1𝑛 ) + 𝑑2 (2𝑛 ) + 𝑑3 (−4)𝑛 − 3𝑛 + 9
where 𝑑1 , 𝑑2 and 𝑑3 are constants.
b. 𝑓(𝑛) = (−1)𝑛 (4)𝑛 = (−4)𝑛 , and 𝑏 = −4 is the root of the characteristic equation and the
multiplicity of −4 is 1, so we choose the particular solution to the given non-homogeneous
recurrence relation to be 𝑎𝑛𝑝 = 𝑞𝑛(−4)𝑛 , where 𝑞 is constant to be determined by substituting
𝑎𝑛𝑝 in to the given recurrence relation.

Thus,
𝑎𝑛𝑝 − 𝑎𝑛−1
𝑝 𝑝 𝑝
− 10𝑎𝑛−2 + 8𝑎𝑛−3 = 𝑓(𝑛) , where 𝑓(𝑛) = (−4)𝑛 .
The rest of the steps are left as an exercise.

Hu 14 | P a g e
Discrete Mathematics and Combinatorics 2024
Exercise
1. Let 𝐴 𝑎𝑛𝑑 𝐵 be two sets such that |𝐴| = 2𝑎 − 𝑏 , |𝐵| = 2𝑎, |𝐴 ∩ 𝐵| = 𝑎 − 𝑏 and |𝑈| = 3𝑎 +
2𝑏. Find the cardinality of each set.
a) 𝐴 ∪ 𝐵 b) 𝐴 − 𝐵 c) 𝐵 ′ d) 𝐴′ − 𝐴′
2. Let 𝐴 𝑎𝑛𝑑 𝐵 be finite disjoint set, where |𝐴| = 𝑎,|𝐵| = 𝑏. Find the cardinality of each set
a) 𝐴∪𝐵 b) 𝐴 − 𝐵 c) 𝐵 − 𝐴
3. According to a survey among 160 college students, 95 students takes a course in English , 72
takes a course in French, 67 takes a course in German , 35 take a course in English and in
French , 37 takes a course in French and in German, 40 takes a course in German and in
English and 25 take a course in all three language. Find the number of students in the survey
who take a course in
a) English but not German b) English, French or German

4. Find the number of positive integer ≤ 2076 and divisible by

a) 3 𝑜𝑟 4 c) 3 𝑜𝑟 4 𝑏𝑖𝑡 𝑛𝑜𝑡 12
b) 2,3𝑜𝑟 5 𝑏𝑢𝑡 𝑛𝑜𝑡 30 d) 3, 4 𝑜𝑟 5 𝑏𝑢𝑡 𝑛𝑜𝑡 60
5. Consider the set

A = {2,4,6, . . . ,114}.
a) How many elements are there in A?
b) How many are divisible by 3?
c) How many are divisible by 15
d) How many are divisible by either 3, 5 or both?
e) How many are neither divisible by 3 nor 5
f) How many are divisible by exactly one of 3 or 5?
6. Let 𝑎𝑛 = 2𝑎𝑛−1 + 𝑎𝑛−2 with 𝑎0 = 1 and 𝑎1 = 1. Find 𝑎2 , 𝑎3 , 𝑎4 and 𝑎5 .
7. Verify that the solution of the recurrence relation 𝑎𝑛 = 3𝑎𝑛−1 with 𝑎0 = 4 is 𝑎𝑛 = 4(3)𝑛 .
8. Verify that the solution of 𝑎𝑛 = 5𝑎𝑛−1 − 12 with 𝑎0 = 13 is 𝑎𝑛 = 10(5)𝑛 + 3.
9. Solve the recurrence relations together with the initial conditions given.
a. 𝑎𝑛 + 6𝑎𝑛−1 = 0 , fo𝑟 𝑛 ≥ 1 , 𝑎0 = −4
b. 𝑎𝑛 − 7𝑎𝑛−1 + 12𝑎𝑛−2 = 0 , for 𝑛 ≥ 2 , 𝑎0 = 1 , 𝑎1 = 0 .

Hu 15 | P a g e
Discrete Mathematics and Combinatorics 2024
c. 𝑎𝑛 + 8𝑎𝑛−1 + 16𝑎𝑛−2 = 0 , for 𝑛 ≥ 2 , 𝑎0 = 1 , 𝑎1 = 1 .
5 25
d. 𝑎𝑛 − 2 𝑎𝑛−1 + 16 𝑎𝑛−2 = 0 , for 𝑛 ≥ 2 , 𝑎0 = 2 , 𝑎1 = 1 .

e. 𝑎𝑛 = 7𝑎𝑛−1 − 10𝑎𝑛−2 , for 𝑛 ≥ 2 , 𝑎0 = 2 , 𝑎1 = 1 .

f. 𝑎𝑛 = 2𝑎𝑛−1 − 𝑎𝑛−2 , for 𝑛 ≥ 2 , 𝑎0 = 4 , 𝑎1 = 1 .
g. 𝑎𝑛 + 6𝑎𝑛−1 + 9𝑎𝑛−2 = 0 , for 𝑛 ≥ 2 , 𝑎0 = 3 , 𝑎1 = −3
h. 𝑎𝑛+2 = −4𝑎𝑛−1 + 5𝑎𝑛 , for 𝑛 ≥ 0 , 𝑎0 = 2 , 𝑎1 = 8 .
i. 𝑎𝑛 = 5𝑎𝑛−2 − 4𝑎𝑛−4 = 0 for 𝑛 ≥ 4 with 𝑎0 = 3 , 𝑎1 = 2 , 𝑎2 = 6 and 𝑎3 = 8.
10. Find the general solution (all solutions) of the recurrence relation
a. 𝑎𝑛 + 6𝑎𝑛−1 = 0 , for 𝑛 ≥ 1 .
b. 𝑎𝑛 + 10𝑎𝑛−1 + 25𝑎𝑛−2 = 0 , for 𝑛 ≥ 2
c. 𝑎𝑛 − 2𝑎𝑛−1 − 𝑎𝑛−2 + 2𝑎𝑛−3 = 0 , for 𝑛 ≥ 3
1 2
d. 𝑎𝑛 + 𝑎𝑛−1 − 𝑎𝑛−2 = 0 , for 𝑛 ≥ 2
3 9
e. 𝑎𝑛 − 2𝑎𝑛−1 − 𝑎𝑛−2 + 2𝑎𝑛−3 = 0 , for 𝑛 ≥ 3
11. Find the general solution (all the solutions) of the recurrence relation
a. 𝑎𝑛 = 6𝑎𝑛−1 + 2𝑛 , for 𝑛 ≥ 1
b. 𝑎𝑛 = −2𝑎𝑛−1 − 𝑎𝑛−2 + 10𝑛2 − 2𝑛 + 3 , for 𝑛 ≥ 2
c. 𝑎𝑛 − 5𝑎𝑛−1 − 6𝑎𝑛−2 = 5𝑛 + 3𝑛 , for 𝑛 ≥ 2
12. Solve the recurrence relation together with the initial conditions given.
a. 𝑎𝑛 − 4𝑎𝑛−1 = −𝑛2 , for 𝑛 ≥ 1 , 𝑎0 = 1
b. 𝑎𝑛 − 5𝑎𝑛−1 + 6𝑎𝑛−2 = 42(4𝑛 ) , for 𝑛 ≥ 2 , 𝑎0 = 4 , 𝑎1 = 1 .
c. 𝑎𝑛 + 6𝑎𝑛−1 + 9𝑎𝑛−2 = 𝑛2𝑛 , for 𝑛 ≥ 2 , 𝑎0 = 3 , 𝑎1 = −3 .
d. 𝑎𝑛 − 2𝑎𝑛−1 + 𝑎𝑛−2 = (𝑛2 + 3)(5𝑛 ) , for 𝑛 ≥ 2 , 𝑎0 = 3 , 𝑎1 = −3 .

Hu 16 | P a g e