DISCRETE MATHEMATICS (3140708)

CHAPTER 3 – Unit 3
RECURRENCE RELATION

CONTENT

❖ Introduction
❖ Recursion
❖ Recurrence relation
❖ Solving recurrence relation

Definition of Recurrence relation

The recurrence relation for the sequence {𝑎𝑛 } is an equation or formula in which 𝑎𝑛 can be
expressed in terms of one or more previous terms 𝑎𝑛−1 , 𝑎𝑛−2 , … , 𝑎0 , 𝑎1.
The recurrence relation is also called difference equation.
Note that the sequence {𝑎𝑛 }𝑛=∞ ∞
𝑛=0 or {𝑎𝑛 }0 can be written as 𝑎0 , 𝑎1 , 𝑎2 , 𝑎3 , 𝑎4 , … , 𝑎𝑛−2 ,
𝑎𝑛−1 , 𝑎𝑛 , 𝑎𝑛+1 , 𝑎𝑛+2 , ….
For example, the following relations are examples of recurrence relation:
1) 𝑎𝑛 = 𝑎𝑛−2 + 𝑎𝑛−1 where 𝑛 ≥ 2

2) 𝑎𝑛+1 = 𝑎𝑛 + 3𝑎𝑛−1 where 𝑛 ≥ 1 and 𝑎0 = 1. Here the given information 𝑎0 = 1 is

called initial condition.
Order of recurrence relation
The difference between highest and lowest subscript of 𝑎 in the relation is called order of the
recurrence relation.
For example,
1) Consider the recurrence relation 𝑎𝑛 = 𝑎𝑛−2 + 𝑎𝑛−1.
Highest subscript of 𝑎 is 𝑛.
Lowest subscript of 𝑎 is 𝑛 − 2.
Difference = 𝑛 − (𝑛 − 2) = 2
Hence, the order of the given recurrence relation is 𝟐.

2) Consider the recurrence relation 𝑎𝑛+4 + 2𝑎𝑛+3 + 3𝑎𝑛+2 + 2𝑎𝑛+1 + 𝑎𝑛 = 0.

Highest subscript = 𝑛 + 4
Lowest subscript = 𝑛
Difference = 𝑛 + 4 − 𝑛 = 4
Hence, the order of the given recurrence relation is 𝟒.
Degree of recurrence relation
The highest power of term with highest subscript of 𝑎 is called degree of the recurrence
relation.
For example,
3
1) The given recurrence relation is 𝑎𝑛4 − 5𝑎𝑛−1 = 0.
Highest subscript of 𝑎 is 𝑛 in the first term.
The power of 𝑎𝑛 is 4.
Hence, the degree of the given recurrence relation is 𝟒.

3 2
2) The given recurrence relation is 𝑎𝑛+3 + 3𝑎𝑛+2 + 3𝑎𝑛+1 = 𝑓(𝑛).
Highest subscript of 𝑎 is 𝑛 + 3 in the first term.
The power of 𝑎𝑛+3 is 3.
Hence, the degree of the given recurrence relation is 𝟑.

Homogeneous linear recurrence relation of order 𝒏

The recurrence relation of the form
𝐶𝑛 𝑎𝑛 + 𝐶𝑛−1 𝑎𝑛−1 + 𝐶𝑛−2 𝑎𝑛−2 + ⋯ + 𝐶2 𝑎2 + 𝐶1 𝑎1 + 𝐶0 𝑎0 = 𝟎
where 𝐶𝑛 , 𝐶𝑛−1 , 𝐶𝑛−2 , …, 𝐶2 , 𝐶1 , 𝐶0 are coefficients (constants) is called the
homogeneous linear recurrence relation of order 𝑛.

Nonhomogeneous linear recurrence relation of order 𝒏

The recurrence relation of the form
𝐶𝑛 𝑎𝑛 + 𝐶𝑛−1 𝑎𝑛−1 + 𝐶𝑛−2 𝑎𝑛−2 + ⋯ + 𝐶2 𝑎2 + 𝐶1 𝑎1 + 𝐶0 𝑎0 = 𝒇(𝒏)
where 𝐶𝑛 , 𝐶𝑛−1 , 𝐶𝑛−2 , …, 𝐶2 , 𝐶1 , 𝐶0 are coefficients (constants) is called the
nonhomogeneous linear recurrence relation of order 𝑛.

Solution to the recurrence relation

An explicit formula for 𝑎𝑛 which satisfy the recurrence relation with initial conditions is
called a solution to the recurrence relation.
1) Solution to the homogeneous linear recurrence relation
The solution to the homogeneous linear recurrence relation is given by
(ℎ)
𝑎𝑛 = 𝑎𝑛
(ℎ)
where 𝑎𝑛 is called homogeneous solution.
 2) Solution of nonhomogeneous linear recurrence relation
The solution to the nonhomogeneous linear recurrence relation is given by
(ℎ) (𝑝)
𝑎𝑛 = 𝑎𝑛 + 𝑎𝑛
(ℎ) (𝑝)
where 𝑎𝑛 is called homogeneous solution and 𝑎𝑛 is called particular solution.

Characteristic equation (Auxiliary equation)

Let 𝐶𝑛 𝑎𝑛 + 𝐶𝑛−1 𝑎𝑛−1 + 𝐶𝑛−2 𝑎𝑛−2 + ⋯ + 𝐶2 𝑎2 + 𝐶1 𝑎1 + 𝐶0 𝑎0 = 𝑓(𝑛) be the
nonhomogeneous recurrence relation of order 𝑛.
To write the characteristic equation,
set 𝑎𝑛 = 𝛼 𝑛 ,
set 𝑎𝑛−1 = 𝛼 𝑛−1 ,
set 𝑎𝑛−2 = 𝛼 𝑛−2 ,
…
set 𝑎2 = 𝛼 2 ,
set 𝑎1 = 𝛼 1 = 𝛼,
set 𝑎0 = 𝛼 0 = 1,
set 𝑓(𝑛) = 0,
then, the characteristic equation is given by
𝐶𝑛 𝛼 𝑛 + 𝐶𝑛−1 𝛼 𝑛−1 + 𝐶𝑛−2 𝛼 𝑛−2 + ⋯ + 𝐶2 𝛼 2 + 𝐶1 𝛼 + 𝐶0 = 0
For example,
1) Let 𝑎𝑛 − 3𝑎𝑛−1 + 2𝑎𝑛−2 = 𝑓(𝑛) be the recurrence relation.
The order of given recurrence relation is 𝑛 − (𝑛 − 2) = 2.
Set 𝑎𝑛 = 𝛼 2 .
Set 𝑎𝑛−1 = 𝛼.
Set 𝑎𝑛−2 = 1.
Set 𝑓(𝑛) = 0.
Then, the characteristic equation is 𝛼 2 − 3𝛼 + 2 = 0.

2) Let 𝑎𝑛+3 − 3𝑎𝑛+2 − 9𝑎𝑛+1 + 27𝑎𝑛 = 0 be the recurrence relation.

The order of given recurrence relation is 3.
Set 𝑎𝑛+3 = 𝛼 3 .
Set 𝑎𝑛+2 = 𝛼 2 .
Set 𝑎𝑛+1 = 𝛼.
Set 𝑎𝑛 = 1.
Then, the characteristic equation is 𝛼 3 − 3𝛼 2 − 9𝛼 + 27 = 0.
Roots of characteristic equation
1) Let 𝑎𝛼 2 + 𝑏𝛼 + 𝑐 = 0 be the quadratic characteristic equation. Then, the roots are
given by

−𝑏 ± √𝑏 2 − 4𝑎𝑐
𝛼=
2𝑎

2) Let 𝑎𝛼 3 + 𝑏𝛼 2 + 𝑐𝛼 + 𝑑 = 0 be the cubic characteristic equation. Then, the roots

can be obtained by synthetic division method.

Nature of roots
Roots may be either
1) Real and equal or
2) Real and distinct or
3) Complex
Important point
According to the nature of the roots of characteristic equation, we can write homogeneous
(ℎ)
solution 𝑎𝑛 .
Homogeneous solution
(ℎ)
The homogeneous solution is denoted by 𝑎𝑛 . If the right-hand side of the given recurrence
(ℎ)
relation is 0 then the solution to the recurrence relation is 𝑎𝑛 = 𝑎𝑛 .
Step 1: Write the characteristic equation.
Step 2: Find the roots of the characteristic equation.
Step 3:
A) Assume that 𝛼1 , 𝛼2 , 𝛼3 , 𝛼4 , …, 𝛼𝑛 are the real and distinct roots. Then, the
homogeneous solution is given by
(ℎ)
𝑎𝑛 = 𝐴1 (𝛼1 )𝑛 + 𝐴2 (𝛼2 )𝑛 + 𝐴3 (𝛼3 )𝑛 + ⋯ + 𝐴𝑛 (𝛼𝑛 )𝑛

B) Assume that 𝛼1 , 𝛼2 , 𝛼3 , 𝛼4 , …, 𝛼𝑛 are the real and equal roots. Then, the
homogeneous solution is given by
(ℎ)
𝑎𝑛 = (𝐴1 + 𝐴2 𝑛 + 𝐴3 𝑛2 + 𝐴4 𝑛3 + ⋯ + 𝐴𝑛 𝑛𝑛−1 )(𝛼)𝑛
Here 𝛼 is a root of the characteristic equation.

C) Assume that 𝛼1 = 𝑎 + 𝑏𝑖 and 𝛼2 = 𝑎 − 𝑏𝑖 are the complex roots. Then, the

homogeneous solution is given by
(ℎ)
𝑎𝑛 = 𝐴1 (𝑎 + 𝑖𝑏)𝑛 + 𝐴2 (𝑎 − 𝑖𝑏)𝑛
Note that √−1 = 𝑖. For example, √−49 = ±7 𝑖 , √−7 = ±√7 𝑖.
 D) Assume that 𝛼1 , 𝛼2 are real and distinct roots, 𝛼3 , 𝛼4 , 𝛼5 are real and equal roots,
𝛼6 = 𝑎 + 𝑏𝑖 , 𝛼7 = 𝑎 − 𝑏𝑖 are complex roots. Then, the homogeneous solution is
given by
(ℎ)
𝑎𝑛 = 𝐴1 (𝛼1 )𝑛 + 𝐴2 (𝛼2 )𝑛 + (𝐴3 + 𝐴4 𝑛 + 𝐴5 𝑛2 )(𝛼)𝑛 + 𝐴6 (𝑎 + 𝑏𝑖)𝑛 + 𝐴7 (𝑎 − 𝑏𝑖)𝑛
Here 𝛼 is equal to 𝛼3 or 𝛼4 or 𝛼5 . That is, 𝛼 = 𝛼3 = 𝛼4 = 𝛼5 .
Step 4: If initial conditions are given then use them to find the values of 𝐴1 , 𝐴2 , ….
Step 5: Substitute the obtained values of 𝐴1 , 𝐴2 , … into the general solution 𝑎𝑛 .

Question
Solve the recurrence relation 𝑎𝑛 − 7𝑎𝑛−1 + 12𝑎𝑛−2 = 0.
Answer
Step 1:
The order of given recurrence relation is 𝑛 − (𝑛 − 2) = 2.
Set 𝑎𝑛 = 𝛼 2 .
Set 𝑎𝑛−1 = 𝛼.
Set 𝑎𝑛−2 = 1.
Then, the characteristic equation is 𝛼 2 − 7𝛼 + 12 = 0.
Step 2:
Compare the equation 𝛼 2 − 7𝛼 + 12 = 0 with the general equation 𝑎𝛼 2 + 𝑏𝛼 + 𝑐 = 0, we
have 𝑎 = 1 , 𝑏 = −7 , 𝑐 = 12. Then, the roots are given by

−𝑏 ± √𝑏 2 − 4𝑎𝑐
𝛼=
2𝑎
−(−7) ± √(−7)2 − 4(1)(12)
𝛼=
2(1)

7 ± √49 − 48
𝛼=
2
7 ± √1
𝛼=
2
7±1
𝛼=
2
7−1 7+1
𝛼1 = , 𝛼2 =
2 2
𝛼1 = 3 , 𝛼2 = 4
The roots 𝛼1 = 3 and 𝛼2 = 4 are real and distinct.
Step 3:
The solution to the given recurrence relation is given by
(ℎ)
𝑎𝑛 = 𝐴1 (𝛼1 )𝑛 + 𝐴2 (𝛼2 )𝑛
(ℎ)
𝑎𝑛 = 𝐴1 (3)𝑛 + 𝐴2 (4)𝑛
𝑎𝑛 = 𝐴1 (3)𝑛 + 𝐴2 (4)𝑛

Question
Solve the recurrence relation 𝑎𝑛 − 6𝑎𝑛−1 + 9𝑎𝑛−2 = 0.
Answer
Step 1:
The order of given recurrence relation is 𝑛 − (𝑛 − 2) = 2.
Set 𝑎𝑛 = 𝛼 2 .
Set 𝑎𝑛−1 = 𝛼.
Set 𝑎𝑛−2 = 1.
Then, the characteristic equation is 𝛼 2 − 6𝛼 + 9 = 0.
Step 2:
Compare the equation 𝛼 2 − 6𝛼 + 9 = 0 with the general equation 𝑎𝛼 2 + 𝑏𝛼 + 𝑐 = 0, we
have 𝑎 = 1 , 𝑏 = −6 , 𝑐 = 9. Then, the roots are given by

−𝑏 ± √𝑏 2 − 4𝑎𝑐
𝛼=
2𝑎
−(−6) ± √(−6)2 − 4(1)(9)
𝛼=
2(1)

6 ± √36 − 36
𝛼=
2
6 ± √0
𝛼=
2
6±0
𝛼=
2
6−0 6+0
𝛼1 = , 𝛼2 =
2 2
𝛼1 = 3 , 𝛼2 = 3
The roots 𝛼1 = 3 and 𝛼2 = 3 are real and equal.
Step 3:
Let 𝛼 = 3. The solution to the given recurrence relation is given by
(ℎ)
𝑎𝑛 = (𝐴1 + 𝐴2 𝑛)(𝛼)𝑛
(ℎ)
𝑎𝑛 = (𝐴1 + 𝐴2 𝑛)(3)𝑛
𝑎𝑛 = (𝐴1 + 𝐴2 𝑛)(3)𝑛

Question
Solve the recurrence relation 𝑎𝑛 + 𝑎𝑛−1 + 𝑎𝑛−2 = 0.
Answer
Step 1:
The order of given recurrence relation is 𝑛 − (𝑛 − 2) = 2.
Set 𝑎𝑛 = 𝛼 2 .
Set 𝑎𝑛−1 = 𝛼.
Set 𝑎𝑛−2 = 1.
Then, the characteristic equation is 𝛼 2 + 𝛼 + 1 = 0.
Step 2:
Compare the equation 𝛼 2 + 𝛼 + 1 = 0 with the general equation 𝑎𝛼 2 + 𝑏𝛼 + 𝑐 = 0, we
have 𝑎 = 1 , 𝑏 = 1 , 𝑐 = 1. Then, the roots are given by

−𝑏 ± √𝑏 2 − 4𝑎𝑐
𝛼=
2𝑎
−1 ± √12 − 4(1)(1)
𝛼=
2(1)

−1 ± √1 − 4
𝛼=
2
−1 ± √−3
𝛼=
2
−1 ± √3 𝑖
𝛼=
2
−1 + √3 𝑖 −1 − √3 𝑖
𝛼1 = , 𝛼2 =
2 2
The roots 𝛼1 and 𝛼2 are complex.
Step 3:
The solution to the given recurrence relation is given by
(ℎ)
𝑎𝑛 = 𝐴1 (𝑎 + 𝑖𝑏)𝑛 + 𝐴2 (𝑎 − 𝑖𝑏)𝑛
𝑛 𝑛
(ℎ) −1 + √3 𝑖 −1 − √3 𝑖
𝑎𝑛 = 𝐴1 ( ) + 𝐴2 ( )
2 2
𝑛 𝑛
−1 + √3 𝑖 −1 − √3 𝑖
𝑎𝑛 = 𝐴1 ( ) + 𝐴2 ( )
2 2
Question
Solve the recurrence relation 𝑎𝑛+3 − 3𝑎𝑛+2 − 9𝑎𝑛+1 + 27𝑎𝑛 = 0.
Answer
Step 1:
The order of given recurrence relation is (𝑛 + 3) − 𝑛 = 3.
Set 𝑎𝑛+3 = 𝛼 3 .
Set 𝑎𝑛+2 = 𝛼 2 .
Set 𝑎𝑛+1 = 𝛼.
Set 𝑎𝑛 = 1.
Then, the characteristic equation is 𝛼 3 − 3𝛼 2 − 9𝛼 + 27 = 0.
Step 2:
Find the roots of characteristic equation using synthetic division.
First, find the value of 𝛼 such that 𝛼 3 − 3𝛼 2 − 9𝛼 + 27 is equal to 0.
Let 𝜶 = 𝟑. Then, 𝛼 3 − 3𝛼 2 − 9𝛼 + 27 = 33 − 3(3)2 − 9(3) + 27 = 𝟎.
Now, use the synthetic division to find other two roots.
𝛼3 𝛼2 𝛼 𝑐
𝜶=𝟑 1 −3 −9 27
𝟎 3 0 −27
1 0 −9 𝟎

Now, we have 𝑎 = 1 , 𝑏 = 0 , 𝑐 = −9. Then, the roots are given by

−𝑏 ± √𝑏 2 − 4𝑎𝑐
𝛼=
2𝑎
−0 ± √02 − 4(1)(−9)
𝛼=
2(1)
0 ± √0 + 36
𝛼=
2
 0 ± √36
𝛼=
2
0±6
𝛼=
2
0−6 0+6
𝛼1 = , 𝛼2 =
2 2
𝜶𝟏 = −𝟑 , 𝜶𝟐 = 𝟑
So, we have 𝛼1 = −3 , 𝛼2 = 3 and 𝛼3 = 3. The roots 𝛼2 and 𝛼3 are real and equal. The
root 𝛼1 is real and distinct.
Step 3:
Let 𝛼 = 𝛼2 = 𝛼3 = 3. Then, the solution to the given recurrence relation is given by
(ℎ)
𝑎𝑛 = 𝐴1 (𝛼1 )𝑛 + (𝐴2 + 𝐴3 𝑛)(𝛼)𝑛
(ℎ)
𝑎𝑛 = 𝐴1 (−3)𝑛 + (𝐴2 + 𝐴3 𝑛)(3)𝑛
𝑎𝑛 = 𝐴1 (−3)𝑛 + (𝐴2 + 𝐴3 𝑛)(3)𝑛

Question
Solve the recurrence relation 𝑎𝑛 = 𝑎𝑛−1 + 2𝑎𝑛−2 where 𝑛 ≥ 2 with the initial conditions
𝑎0 = 0 and 𝑎1 = 1.
Answer
Rewrite the given recurrence relation by taking all terms on the left-hand side such that the
right-hand side becomes zero. That is, we have 𝑎𝑛 − 𝑎𝑛−1 − 2𝑎𝑛−2 = 0.
Step 1:
The order of given recurrence relation is 𝑛 − (𝑛 − 2) = 2.
Set 𝑎𝑛 = 𝛼 2 .
Set 𝑎𝑛−1 = 𝛼.
Set 𝑎𝑛−2 = 1.
Then, the characteristic equation is 𝛼 2 − 𝛼 − 2 = 0.
Step 2:
Compare the equation 𝛼 2 − 𝛼 − 2 = 0 with the general equation 𝑎𝛼 2 + 𝑏𝛼 + 𝑐 = 0, we
have 𝑎 = 1 , 𝑏 = −1 , 𝑐 = −2. Then, the roots are given by

−𝑏 ± √𝑏 2 − 4𝑎𝑐
𝛼=
2𝑎
−(−1) ± √(−1)2 − 4(1)(−2)
𝛼=
2(1)
 1 ± √1 + 8
𝛼=
2
1 ± √9
𝛼=
2
1±3
𝛼=
2
1−3 1+3
𝛼1 = , 𝛼2 =
2 2
𝛼1 = −1 , 𝛼2 = 2
The roots 𝛼1 = −1 and 𝛼2 = 2 are real and distinct.
Step 3:
The solution to the given recurrence relation is given by
(ℎ)
𝑎𝑛 = 𝐴1 (𝛼1 )𝑛 + 𝐴2 (𝛼2 )𝑛
(ℎ)
𝑎𝑛 = 𝐴1 (−1)𝑛 + 𝐴2 (2)𝑛
𝑎𝑛 = 𝐴1 (−1)𝑛 + 𝐴2 (2)𝑛
Step 4:
Use the given initial conditions to find the values of 𝐴1 and 𝐴2 .
First, substitute 𝑛 = 0 into the obtained solution. Then, we have,
𝑎0 = 𝐴1 (−1)0 + 𝐴2 (2)0
⇒ 𝑎0 = 𝐴1 + 𝐴2 ……… (1)
Now, substitute 𝑛 = 1 into the obtained solution. Then, we have,
𝑎1 = 𝐴1 (−1)1 + 𝐴2 (2)1
⇒ 𝑎1 = −𝐴1 + 2𝐴2 ……… (2)
Substitute the given values 𝑎0 = 0 and 𝑎1 = 1 into the equations (1) and (2). Then, we have,
𝐴1 + 𝐴2 = 0
−𝐴1 + 2𝐴2 = 1
Adding these two equations, we get,
𝟏
3𝐴2 = 1 ⇒ 𝑨𝟐 =
𝟑
Substitute the value of 𝐴2 into the equation 𝐴1 + 𝐴2 = 0. Then, we have,
1 𝟏
𝐴1 + = 0 ⇒ 𝑨𝟏 = −
3 𝟑
Step 5:
Substitute the values of 𝐴1 and 𝐴2 into the obtained solution. Then, we have,
𝟏 𝟏
𝑎𝑛 = − (−𝟏)𝒏 + (𝟐)𝒏
𝟑 𝟑
This is the required solution of the given recurrence relation.

Question (JULY 2023 – 07 Marks)

Solve the recurrence relation which represents the Fibonacci sequence 𝐹𝑛 = 𝐹𝑛−1 + 𝐹𝑛−2
with 𝐹0 = 𝐹1 = 1.
Answer
Rewrite the given recurrence relation by taking all terms on the left-hand side such that the
right-hand side becomes zero. That is, we have 𝐹𝑛 − 𝐹𝑛−1 − 𝐹𝑛−2 = 0.
Step 1:
The order of given recurrence relation is 𝑛 − (𝑛 − 2) = 2.
Set 𝐹𝑛 = 𝛼 2 .
Set 𝐹𝑛−1 = 𝛼.
Set 𝐹𝑛−2 = 1.
Then, the characteristic equation is 𝛼 2 − 𝛼 − 1 = 0.
Step 2:
Compare the equation 𝛼 2 − 𝛼 − 1 = 0 with the general equation 𝑎𝛼 2 + 𝑏𝛼 + 𝑐 = 0, we
have 𝑎 = 1 , 𝑏 = −1 , 𝑐 = −1. Then, the roots are given by

−𝑏 ± √𝑏 2 − 4𝑎𝑐
𝛼=
2𝑎
−(−1) ± √(−1)2 − 4(1)(−1)
𝛼=
2(1)
1 ± √1 + 4
𝛼=
2
1 ± √5
𝛼=
2
1 − √5 1 + √5
𝛼1 = , 𝛼2 =
2 2
1−√5 1+√5
The roots 𝛼1 = and 𝛼2 = are real and distinct.
2 2
Step 3:
The solution to the given recurrence relation is given by
(ℎ)
𝐹𝑛 = 𝐴1 (𝛼1 )𝑛 + 𝐴2 (𝛼2 )𝑛
𝑛 𝑛
(ℎ) 1 − √5 1 + √5
𝐹𝑛 = 𝐴1 ( ) + 𝐴2 ( )
2 2
𝑛 𝑛
1 − √5 1 + √5
𝐹𝑛 = 𝐴1 ( ) + 𝐴2 ( )
2 2
Step 4:
Use the given initial conditions to find the values of 𝐴1 and 𝐴2 .
First, substitute 𝑛 = 0 into the obtained solution. Then, we have,
0 0
1 − √5 1 + √5
𝐹0 = 𝐴1 ( ) + 𝐴2 ( )
2 2

⇒ 𝐹0 = 𝐴1 + 𝐴2 ……… (1)
Now, substitute 𝑛 = 1 into the obtained solution. Then, we have,
1 1
1 − √5 1 + √5
𝐹1 = 𝐴1 ( ) + 𝐴2 ( )
2 2
1−√5 1+√5
⇒ 𝐹1 = ( ) 𝐴1 + ( ) 𝐴2 ……… (2)
2 2

Substitute the given values 𝐹0 = 1 and 𝐹1 = 1 into the equations (1) and (2). Then, we have,
𝐴1 + 𝐴2 = 1

1 − √5 1 + √5
( ) 𝐴1 + ( ) 𝐴2 = 1
2 2
Solving these two equations, we get,

𝟏 − √𝟓
𝑨𝟏 = −
𝟐√𝟓
𝟏 + √𝟓
𝑨𝟐 =
𝟐√𝟓
Step 5:
Substitute the values of 𝐴1 and 𝐴2 into the obtained solution. Then, we have,
𝑛 𝑛
1 − √5 1 − √5 1 + √5 1 + √5
𝑎𝑛 = − ( )( ) +( )( )
2√5 2 2√5 2
 𝒏+𝟏 𝒏+𝟏
𝟏𝟏 + √𝟓 𝟏 − √𝟓
⇒ 𝑎𝑛 = [( ) −( ) ]
√𝟓 𝟐 𝟐

This is the required solution of the given recurrence relation.

Question (FEB 2024 – 07 Marks)

Solve: 𝑎𝑛 = 11𝑎𝑛−1 − 39𝑎𝑛−2 + 45𝑎𝑛−3 , where 𝑎0 = 5 , 𝑎1 = 11 , 𝑎2 = 25.

Answer
Rewrite the given recurrence relation by taking all terms on the left-hand side such that the
right-hand side becomes zero. That is, we have 𝑎𝑛 − 11𝑎𝑛−1 + 39𝑎𝑛−2 − 45𝑎𝑛−3 = 0.
Step 1:
The order of given recurrence relation is 𝑛 − (𝑛 − 3) = 3.
Set 𝑎𝑛 = 𝛼 3 .
Set 𝑎𝑛−1 = 𝛼 2 .
Set 𝑎𝑛−2 = 𝛼.
Set 𝑎𝑛−3 = 1.
Then, the characteristic equation is 𝛼 3 − 11𝛼 2 + 39𝛼 − 45 = 0.
Step 2:
Find the roots of characteristic equation using synthetic division.
First, find the value of 𝛼 such that 𝛼 3 − 11𝛼 2 + 39𝛼 − 45 is equal to 0.
Let 𝜶 = 𝟑. Then, 𝛼 3 − 11𝛼 2 + 39𝛼 − 45 = 33 − 11(3)2 + 39(3) − 45 = 𝟎.
Now, use the synthetic division to find other two roots.
𝛼3 𝛼2 𝛼 𝑐
𝜶=𝟑 1 −11 39 −45
𝟎 3 −24 45
1 −8 15 𝟎

Now, we have 𝑎 = 1 , 𝑏 = −8 , 𝑐 = 15. Then, the roots are given by

−𝑏 ± √𝑏 2 − 4𝑎𝑐
𝛼=
2𝑎
−(−8) ± √(−8)2 − 4(1)(15)
𝛼=
2(1)
8 ± √64 − 60
𝛼=
2
 8 ± √4
𝛼=
2
8±2
𝛼=
2
8+2 8−2
𝛼1 = , 𝛼2 =
2 2
𝜶𝟏 = 𝟓 , 𝜶𝟐 = 𝟑
So, we have 𝛼1 = 5 , 𝛼2 = 3 and 𝛼3 = 3. The roots 𝛼2 and 𝛼3 are real and equal. The root
𝛼1 is real and distinct.
Step 3:
Let 𝛼 = 𝛼2 = 𝛼3 = 3. Then, the solution to the given recurrence relation is given by
(ℎ)
𝑎𝑛 = 𝐴1 (𝛼1 )𝑛 + (𝐴2 + 𝐴3 𝑛)(𝛼)𝑛
(ℎ)
𝑎𝑛 = 𝐴1 (5)𝑛 + (𝐴2 + 𝐴3 𝑛)(3)𝑛
𝑎𝑛 = 𝐴1 (5)𝑛 + (𝐴2 + 𝐴3 𝑛)(3)𝑛
Step 4:
Use the given initial conditions to find the values of 𝐴1 , 𝐴2 and 𝐴3 .
First, substitute 𝑛 = 0 into the obtained solution. Then, we have,
𝑎0 = 𝐴1 (5)0 + (𝐴2 + 𝐴3 ∙ 0)(3)0
⇒ 𝑎0 = 𝐴1 + 𝐴2 ……… (1)
Now, substitute 𝑛 = 1 into the obtained solution. Then, we have,
𝑎1 = 𝐴1 (5)1 + (𝐴2 + 𝐴3 ∙ 1)(3)1
⇒ 𝑎1 = 5𝐴1 + 3𝐴2 + 3𝐴3 ……… (2)
Now, substitute 𝑛 = 2 into the obtained solution. Then, we have,
𝑎2 = 𝐴1 (5)2 + (𝐴2 + 𝐴3 ∙ 2)(3)2
⇒ 𝑎2 = 25𝐴1 + 9𝐴2 + 18𝐴3 ……… (3)
Substitute the given values 𝑎0 = 5 , 𝑎1 = 11 and 𝑎2 = 25 into the equations (1), (2) and (3).
Then, we have,
𝐴1 + 𝐴2 = 5
5𝐴1 + 3𝐴2 + 3𝐴3 = 11
25𝐴1 + 9𝐴2 + 18𝐴3 = 25
Solving these three equations, we get,
𝑨𝟏 = 𝟏 , 𝑨𝟐 = 𝟒 and 𝑨𝟑 = −𝟐
Step 5:
Substitute the values of 𝐴1 , 𝐴2 and 𝐴3 into the obtained solution. Then, we have,
𝑎𝑛 = (𝟓)𝒏 + (𝟒 − 𝟐𝒏)(𝟑)𝒏
This is the required solution of the given recurrence relation.

Particular solution
(𝑝)
The particular solution is denoted by 𝑎𝑛 . If the right-hand side of the given recurrence
(ℎ) (𝑝)
relation is non-zero then the solution to the recurrence relation is 𝑎𝑛 = 𝑎𝑛 + 𝑎𝑛 .

Undetermined coefficient method

The function on the right-hand side of the recurrence relation is denoted by 𝑓(𝑛). There is no
general method for finding the particular solution of a recurrence relation for every function
𝑓(𝑛).
(𝑝)
We will use undetermined coefficient method to find the particular solution 𝑎𝑛 .
This method is useful when the function 𝑓(𝑛) consists of special forms. Depending on certain
forms of 𝑓(𝑛), we consider a trial solution containing a number of unknown constant
coefficients which are to be determined by substitution in the recurrence relation.
The trial solutions to be used in each case are shown in the following table:
Right-hand side = Form of 𝒇(𝒏) (𝒑)
Trial particular solution = 𝒂𝒏
𝑏 (constant) 𝐴
𝑏𝑛 + 𝑐 where 𝑏 is constant 𝐴 + 𝐵𝑛
𝑏𝑛 + 𝑐𝑛2 where 𝑏 and 𝑐 are constants 𝐴 + 𝐵𝑛 + 𝐶𝑛2
𝑏 𝑛 where 𝑏 is not a root of characteristic equation 𝐴 ∙ 𝑏𝑛

Question
Solve the given recurrence relation by finding particular solution using Undetermined
coefficient method.
𝑎𝑛+2 − 3𝑎𝑛+1 + 2𝑎𝑛 = 5𝑛
Answer
Step 1:
The order of given recurrence relation is (𝑛 + 2) − 𝑛 = 2.
Set 𝑎𝑛+2 = 𝛼 2 .
Set 𝑎𝑛+1 = 𝛼.
Set 𝑎𝑛 = 1.
Then, the characteristic equation is 𝛼 2 − 3𝛼 + 2 = 0.
Step 2:
Compare the equation 𝛼 2 − 3𝛼 + 2 = 0 with the general equation 𝑎𝛼 2 + 𝑏𝛼 + 𝑐 = 0, we
have 𝑎 = 1 , 𝑏 = −3 , 𝑐 = 2. Then, the roots are given by

−𝑏 ± √𝑏 2 − 4𝑎𝑐
𝛼=
2𝑎
−(−3) ± √(−3)2 − 4(1)(2)
𝛼=
2(1)

3 ± √9 − 8
𝛼=
2
3 ± √1
𝛼=
2
3±1
𝛼=
2
3−1 3+1
𝛼1 = , 𝛼2 =
2 2
𝛼1 = 1 , 𝛼2 = 2
The roots 𝛼1 = 1 and 𝛼2 = 2 are real and distinct.
Step 3:
The solution to the given recurrence relation is given by
(ℎ)
𝑎𝑛 = 𝐴1 (𝛼1 )𝑛 + 𝐴2 (𝛼2 )𝑛
(ℎ)
𝑎𝑛 = 𝑨𝟏 (𝟏)𝒏 + 𝑨𝟐 (𝟐)𝒏
Step 4:
Use the method of undetermined coefficients to find the particular solution.
The right-hand side of the given recurrence relation is 5𝑛 . So, let us consider 𝑓(𝑛) = 5𝑛 .
(𝑝)
Depending on the form of 𝑓(𝑛), we consider a trial solution 𝑎𝑛 = 𝐴 ∙ 5𝑛 where 𝐴 is
unknown coefficient.
(𝑝)
Replace 𝑛 by 𝑛 + 1 in 𝑎𝑛 ,
(𝑝)
𝑎𝑛+1 = 𝐴 ∙ 5𝑛+1
(𝑝)
Replace 𝑛 by 𝑛 + 2 in 𝑎𝑛 ,
(𝑝)
𝑎𝑛+2 = 𝐴 ∙ 5𝑛+2
Step 5:
Substitute all obtained expressions into the given recurrence relation.
𝑎𝑛+2 − 3𝑎𝑛+1 + 2𝑎𝑛 = 5𝑛
⟹ 𝐴 ∙ 5𝑛+2 − 3(𝐴 ∙ 5𝑛+1 ) + 2𝐴 ∙ 5𝑛 = 5𝑛
⟹ 𝐴 ∙ 5𝑛 52 − 3𝐴 ∙ 5𝑛 51 + 2𝐴 ∙ 5𝑛 = 5𝑛
⟹ 25𝐴 ∙ 5𝑛 − 15𝐴 ∙ 5𝑛 + 2𝐴 ∙ 5𝑛 = 5𝑛
⟹ (25𝐴 − 15𝐴 + 2𝐴) ∙ 5𝑛 = 5𝑛
⟹ 12𝐴 ∙ 5𝑛 = 5𝑛
Step 6:
Compare coefficients of 5𝑛 , we get
1
12𝐴 = 1 ⟹ 𝐴 =
12
(𝑝)
Substitute the obtained value of 𝐴 in 𝑎𝑛 , we get

(𝑝) 𝟏
𝑎𝑛 = ∙ 𝟓𝒏
𝟏𝟐
Step 7
The general solution is

(ℎ) (𝑝) 𝟏
𝑎𝑛 = 𝑎𝑛 + 𝑎𝑛 = 𝑨𝟏 (𝟏)𝒏 + 𝑨𝟐 (𝟐)𝒏 + ∙ 𝟓𝒏
𝟏𝟐

Question (OCT 2020 – 07 Marks)

Solve the recurrence relation 𝑎𝑛 + 5𝑎𝑛−1 + 6𝑎𝑛−2 = 3𝑛2 using the method of undetermined
coefficients.
Answer
Step 1:
The order of given recurrence relation is 𝑛 − (𝑛 − 2) = 2.
Set 𝑎𝑛 = 𝛼 2 .
Set 𝑎𝑛−1 = 𝛼.
Set 𝑎𝑛−2 = 1.
Then, the characteristic equation is 𝛼 2 + 5𝛼 + 6 = 0.
Step 2:
Compare the equation 𝛼 2 + 5𝛼 + 6 = 0 with the general equation 𝑎𝛼 2 + 𝑏𝛼 + 𝑐 = 0, we
have 𝑎 = 1 , 𝑏 = 5 , 𝑐 = 6. Then, the roots are given by
 −𝑏 ± √𝑏 2 − 4𝑎𝑐
𝛼=
2𝑎
−5 ± √52 − 4(1)(6)
𝛼=
2(1)

−5 ± √25 − 24
𝛼=
2
−5 ± √1
𝛼=
2
−5 ± 1
𝛼=
2
−5 − 1 −5 + 1
𝛼1 = , 𝛼2 =
2 2
𝛼1 = −3 , 𝛼2 = −2
The roots 𝛼1 = −3 and 𝛼2 = −2 are real and distinct.
Step 3:
The solution to the given recurrence relation is given by
(ℎ)
𝑎𝑛 = 𝐴1 (𝛼1 )𝑛 + 𝐴2 (𝛼2 )𝑛
(ℎ)
𝑎𝑛 = 𝑨𝟏 (−𝟑)𝒏 + 𝑨𝟐 (−𝟐)𝒏
Step 4:
Use the method of undetermined coefficients to find the particular solution.
The right-hand side of the given recurrence relation is 3𝑛2 . So, let us consider 𝑓(𝑛) = 3𝑛2 .
(𝑝)
Depending on the form of 𝑓(𝑛), we consider a trial solution 𝑎𝑛 = 𝐴 + 𝐵𝑛 + 𝐶𝑛2 where 𝐴,
𝐵 and 𝐶 are unknown coefficients.
(𝑝)
Replace 𝑛 by 𝑛 − 1 in 𝑎𝑛 ,
(𝑝)
𝑎𝑛−1 = 𝐴 + 𝐵(𝑛 − 1) + 𝐶(𝑛 − 1)2
= 𝐴 + 𝐵𝑛 − 𝐵 + 𝐶(𝑛2 − 2𝑛 + 1)
= 𝐴 + 𝐵𝑛 − 𝐵 + 𝐶𝑛2 − 2𝐶𝑛 + 𝐶
= (𝐴 − 𝐵 + 𝐶) + (𝐵 − 2𝐶)𝑛 + 𝐶𝑛2
(𝑝)
Replace 𝑛 by 𝑛 − 2 in 𝑎𝑛 ,
(𝑝)
𝑎𝑛−2 = 𝐴 + 𝐵(𝑛 − 2) + 𝐶(𝑛 − 2)2
= 𝐴 + 𝐵𝑛 − 2𝐵 + 𝐶(𝑛2 − 4𝑛 + 4)
= 𝐴 + 𝐵𝑛 − 2𝐵 + 𝐶𝑛2 − 4𝐶𝑛 + 4𝐶
 = (𝐴 − 2𝐵 + 4𝐶) + (𝐵 − 4𝐶)𝑛 + 𝐶𝑛2
Step 5:
Substitute all obtained expressions into the given recurrence relation.
𝑎𝑛 + 5𝑎𝑛−1 + 6𝑎𝑛−2 = 3𝑛2
⟹ 𝐴 + 𝐵𝑛 + 𝐶𝑛2 + 5[(𝐴 − 𝐵 + 𝐶) + (𝐵 − 2𝐶)𝑛 + 𝐶𝑛2 ]
+6[(𝐴 − 2𝐵 + 4𝐶) + (𝐵 − 4𝐶)𝑛 + 𝐶𝑛2 ] = 3𝑛2
⟹ 𝐴 + 𝐵𝑛 + 𝐶𝑛2 + (5𝐴 − 5𝐵 + 5𝐶) + (5𝐵 − 10𝐶)𝑛 + 5𝐶𝑛2
+(6𝐴 − 12𝐵 + 24𝐶) + (6𝐵 − 24𝐶)𝑛 + 6𝐶𝑛2 = 3𝑛2
⟹ 𝐴 + 𝐵𝑛 + 𝐶𝑛2 + (5𝐴 − 5𝐵 + 5𝐶) + (5𝐵 − 10𝐶)𝑛 + 5𝐶𝑛2
+(6𝐴 − 12𝐵 + 24𝐶) + (6𝐵 − 24𝐶)𝑛 + 6𝐶𝑛2 = 3𝑛2
⟹ (𝐴 + 5𝐴 − 5𝐵 + 5𝐶 + 6𝐴 − 12𝐵 + 24𝐶) + (𝐵 + 5𝐵 − 10𝐶 + 6𝐵 − 24𝐶)𝑛
+(𝐶 + 5𝐶 + 6𝐶)𝑛2 = 3𝑛2
⟹ (𝟏𝟐𝑨 − 𝟏𝟕𝑩 + 𝟐𝟗𝑪) + (𝟏𝟐𝑩 − 𝟑𝟒𝑪)𝑛 + (𝟏𝟐𝑪)𝑛2 = 𝟎 + 𝟎𝑛 + 𝟑𝑛2
Step 6:
Compare coefficients of 𝑛2 , we get
3 𝟏
12𝐶 = 3 ⟹ 𝐶 = ⟹𝑪=
12 𝟒
Compare coefficients of 𝑛, we get
12𝐵 − 34𝐶 = 0
1
⟹ 12𝐵 − 34 ( ) = 0
4
17
⟹ 12𝐵 − =0
2
17 𝟏𝟕
⟹ 12𝐵 = ⟹𝑩=
2 𝟐𝟒
Compare constant terms (terms without 𝑛), we get
12𝐴 − 17𝐵 + 29𝐶 = 0
17 1
⟹ 12𝐴 − 17 ( ) + 29 ( ) = 0
24 4
289 174
⟹ 12𝐴 − + =0
24 24
174 − 289
⟹ 12𝐴 + ( )=0
24
 115
⟹ 12𝐴 − =0
24
115 𝟏𝟏𝟓
⟹ 12𝐴 = ⟹𝑨=
24 𝟐𝟖𝟖
(𝑝)
Substitute the obtained values of 𝐴, 𝐵 and 𝐶 in 𝑎𝑛 , we get

(𝑝) 𝟏𝟏𝟓 𝟏𝟕 𝟏
𝑎𝑛 = + 𝒏 + 𝒏𝟐
𝟐𝟖𝟖 𝟐𝟒 𝟒
Step 7
The general solution is

(ℎ) (𝑝) 𝟏𝟏𝟓 𝟏𝟕 𝟏

𝑎𝑛 = 𝑎𝑛 + 𝑎𝑛 = 𝑨𝟏 (−𝟑)𝒏 + 𝑨𝟐 (−𝟐)𝒏 + + 𝒏 + 𝒏𝟐
𝟐𝟖𝟖 𝟐𝟒 𝟒

Question (SEP 2021 – 07 Marks)

Solve the recurrence relation 𝑎𝑛+2 − 5𝑎𝑛+1 + 6𝑎𝑛 = 2.

Answer
Step 1:
The order of given recurrence relation is (𝑛 + 2) − 𝑛 = 2.
Set 𝑎𝑛+2 = 𝛼 2 .
Set 𝑎𝑛+1 = 𝛼.
Set 𝑎𝑛 = 1.
Then, the characteristic equation is 𝛼 2 − 5𝛼 + 6 = 0.
Step 2:
Compare the equation 𝛼 2 − 5𝛼 + 6 = 0 with the general equation 𝑎𝛼 2 + 𝑏𝛼 + 𝑐 = 0, we
have 𝑎 = 1 , 𝑏 = −5 , 𝑐 = 6. Then, the roots are given by

−𝑏 ± √𝑏 2 − 4𝑎𝑐
𝛼=
2𝑎
−(−5) ± √(−5)2 − 4(1)(6)
𝛼=
2(1)

5 ± √25 − 24
𝛼=
2
5 ± √1
𝛼=
2
5±1
𝛼=
2
 5−1 5+1
𝛼1 = , 𝛼2 =
2 2
𝛼1 = 2 , 𝛼2 = 3
The roots 𝛼1 = 2 and 𝛼2 = 3 are real and distinct.
Step 3:
The solution to the given recurrence relation is given by
(ℎ)
𝑎𝑛 = 𝐴1 (𝛼1 )𝑛 + 𝐴2 (𝛼2 )𝑛
(ℎ)
𝑎𝑛 = 𝑨𝟏 (𝟐)𝒏 + 𝑨𝟐 (𝟑)𝒏
Step 4:
Use the method of undetermined coefficients to find the particular solution.
The right-hand side of the given recurrence relation is 2. So, let us consider 𝑓(𝑛) = 𝟐.
(𝑝)
Depending on the form of 𝑓(𝑛), we consider a trial solution 𝑎𝑛 = 𝑨 where 𝐴 is unknown
coefficient.
(𝑝)
Replace 𝑛 by 𝑛 + 2 in 𝑎𝑛 ,
(𝑝)
𝑎𝑛+2 = 𝐴
(𝑝)
Replace 𝑛 by 𝑛 + 1 in 𝑎𝑛 ,
(𝑝)
𝑎𝑛+1 = 𝐴
Step 5:
Substitute all obtained expressions into the given recurrence relation.
𝑎𝑛+2 − 5𝑎𝑛+1 + 6𝑎𝑛 = 2
⟹ 𝐴 − 5𝐴 + 6𝐴 = 2
⟹ 2𝐴 = 2
2
⟹𝐴= ⟹𝐴=1
2
(𝑝)
Substitute the obtained value of 𝐴 in 𝑎𝑛 , we get
(𝑝)
𝑎𝑛 = 𝟏
Step 6
(ℎ) (𝑝)
The general solution is 𝑎𝑛 = 𝑎𝑛 + 𝑎𝑛 = 𝑨𝟏 (𝟐)𝒏 + 𝑨𝟐 (𝟑)𝒏 + 𝟏.
Question (DEC 2022 – 07 Marks)

Solve the recurrence relation 𝑎𝑛+2 − 5𝑎𝑛+1 + 6𝑎𝑛 = 2 with initial condition 𝑎0 = 1 and
𝑎1 = −1 using method of undetermined coefficients.
Answer
Step 1:
The order of given recurrence relation is (𝑛 + 2) − 𝑛 = 2.
Set 𝑎𝑛+2 = 𝛼 2 .
Set 𝑎𝑛+1 = 𝛼.
Set 𝑎𝑛 = 1.
Then, the characteristic equation is 𝛼 2 − 5𝛼 + 6 = 0.
Step 2:
Compare the equation 𝛼 2 − 5𝛼 + 6 = 0 with the general equation 𝑎𝛼 2 + 𝑏𝛼 + 𝑐 = 0, we
have 𝑎 = 1 , 𝑏 = −5 , 𝑐 = 6. Then, the roots are given by

−𝑏 ± √𝑏 2 − 4𝑎𝑐
𝛼=
2𝑎
−(−5) ± √(−5)2 − 4(1)(6)
𝛼=
2(1)

5 ± √25 − 24
𝛼=
2
5 ± √1
𝛼=
2
5±1
𝛼=
2
5−1 5+1
𝛼1 = , 𝛼2 =
2 2
𝛼1 = 2 , 𝛼2 = 3
The roots 𝛼1 = 2 and 𝛼2 = 3 are real and distinct.
Step 3:
The solution to the given recurrence relation is given by
(ℎ)
𝑎𝑛 = 𝐴1 (𝛼1 )𝑛 + 𝐴2 (𝛼2 )𝑛
(ℎ)
𝑎𝑛 = 𝑨𝟏 (𝟐)𝒏 + 𝑨𝟐 (𝟑)𝒏
Step 4:
Use the method of undetermined coefficients to find the particular solution.
The right-hand side of the given recurrence relation is 2. So, let us consider 𝑓(𝑛) = 𝟐.
(𝑝)
Depending on the form of 𝑓(𝑛), we consider a trial solution 𝑎𝑛 = 𝑨 where 𝐴 is unknown
coefficient.
 (𝑝)
Replace 𝑛 by 𝑛 + 2 in 𝑎𝑛 ,
(𝑝)
𝑎𝑛+2 = 𝐴
(𝑝)
Replace 𝑛 by 𝑛 + 1 in 𝑎𝑛 ,
(𝑝)
𝑎𝑛+1 = 𝐴
Step 5:
Substitute all obtained expressions into the given recurrence relation.
𝑎𝑛+2 − 5𝑎𝑛+1 + 6𝑎𝑛 = 2
⟹ 𝐴 − 5𝐴 + 6𝐴 = 2
⟹ 2𝐴 = 2
2
⟹𝐴= ⟹𝐴=1
2
(𝑝)
Substitute the obtained value of 𝐴 in 𝑎𝑛 , we get
(𝑝)
𝑎𝑛 = 𝟏
Step 6
(ℎ) (𝑝)
The general solution is 𝑎𝑛 = 𝑎𝑛 + 𝑎𝑛 = 𝑨𝟏 (𝟐)𝒏 + 𝑨𝟐 (𝟑)𝒏 + 𝟏.
Step 7
Use the given initial conditions to find the values of 𝐴1 and 𝐴2 .
First, substitute 𝑛 = 0 into the obtained solution. Then, we have,
𝑎0 = 𝐴1 (2)0 + 𝐴2 (3)0 + 1
⇒ 𝑎0 = 𝐴1 + 𝐴2 + 1 ……… (1)
Now, substitute 𝑛 = 1 into the obtained solution. Then, we have,
𝑎1 = 𝐴1 (2)1 + 𝐴2 (3)1 + 1
⇒ 𝑎1 = 2𝐴1 + 3𝐴2 + 1 ……… (2)
Substitute the given values 𝑎0 = 1 and 𝑎1 = −1 into the equations (1) and (2). Then, we
have,
𝐴1 + 𝐴2 + 1 = 1 ⟹ 𝑨𝟏 + 𝑨𝟐 = 𝟎
2𝐴1 + 3𝐴2 + 1 = −1 ⟹ 𝟐𝑨𝟏 + 𝟑𝑨𝟐 = −𝟐
Solving these two equations, we get, 𝑨𝟏 = 𝟐 and 𝑨𝟐 = −𝟐.
Step 8:
Substitute the values of 𝐴1 and 𝐴2 into the obtained solution. Then, we have,
𝑎𝑛 = 𝟐(𝟐)𝒏 − 𝟐(𝟑)𝒏 + 𝟏
This is the required solution of the given recurrence relation.

Question (FEB 2021 – 07 Marks)

Solve the recurrence relation 𝑎𝑛 − 4𝑎𝑛−1 + 4𝑎𝑛−2 = 𝑛 + 3𝑛 using method of undetermined

coefficients.
Answer
Step 1:
The order of given recurrence relation is 𝑛 − (𝑛 − 2) = 2.
Set 𝑎𝑛 = 𝛼 2 .
Set 𝑎𝑛−1 = 𝛼.
Set 𝑎𝑛−2 = 1.
Then, the characteristic equation is 𝛼 2 − 4𝛼 + 4 = 0.
Step 2:
Compare the equation 𝛼 2 − 4𝛼 + 4 = 0 with the general equation 𝑎𝛼 2 + 𝑏𝛼 + 𝑐 = 0, we
have 𝑎 = 1 , 𝑏 = −4 , 𝑐 = 4. Then, the roots are given by

−𝑏 ± √𝑏 2 − 4𝑎𝑐
𝛼=
2𝑎
−(−4) ± √(−4)2 − 4(1)(4)
𝛼=
2(1)

4 ± √16 − 16
𝛼=
2
4 ± √0
𝛼=
2
4±0
𝛼=
2
4−0 4+0
𝛼1 = , 𝛼2 =
2 2
𝛼1 = 2 , 𝛼2 = 2
The roots 𝛼1 = 2 and 𝛼2 = 2 are real and equal.
Step 3:
Let 𝛼 = 2. The solution to the given recurrence relation is given by
(ℎ)
𝑎𝑛 = (𝐴1 + 𝐴2 𝑛)(𝛼)𝑛
 (ℎ)
𝑎𝑛 = (𝑨𝟏 + 𝑨𝟐 𝒏)(𝟐)𝒏
Step 4:
Use the method of undetermined coefficients to find the particular solution.
The right-hand side of the given recurrence relation is 𝑛 + 3𝑛 .
So, let us consider 𝑓(𝑛) = 𝒏 + 𝟑𝒏 .
(𝑝)
Depending on the form of 𝑓(𝑛), we consider a trial solution 𝑎𝑛 = 𝑨 + 𝑩𝒏 + 𝑪 ∙ 𝟑𝒏 where
𝐴, 𝐵 and 𝐶 are unknown coefficients.
(𝑝)
Replace 𝑛 by 𝑛 − 1 in 𝑎𝑛 ,
(𝑝)
𝑎𝑛−1 = 𝐴 + 𝐵(𝑛 − 1) + 𝐶 ∙ 3𝑛−1
= 𝐴 + 𝐵𝑛 − 𝐵 + 𝐶 ∙ 3𝑛 ∙ 3−1
𝐶 𝑛
= (𝐴 − 𝐵) + 𝐵𝑛 + ∙3
3
(𝑝)
Replace 𝑛 by 𝑛 − 2 in 𝑎𝑛 ,
(𝑝)
𝑎𝑛−2 = 𝐴 + 𝐵(𝑛 − 2) + 𝐶 ∙ 3𝑛−2
= 𝐴 + 𝐵𝑛 − 2𝐵 + 𝐶 ∙ 3𝑛 ∙ 3−2
𝐶 𝑛
= (𝐴 − 2𝐵) + 𝐵𝑛 + ∙3
9
Step 5:
Substitute all obtained expressions into the given recurrence relation.
𝑎𝑛 − 4𝑎𝑛−1 + 4𝑎𝑛−2 = 𝑛 + 3𝑛
𝐶 𝑛 𝐶
⟹ 𝐴 + 𝐵𝑛 + 𝐶 ∙ 3𝑛 − 4 [(𝐴 − 𝐵) + 𝐵𝑛 + ∙ 3 ] + 4 [(𝐴 − 2𝐵) + 𝐵𝑛 + ∙ 3𝑛 ] = 𝑛 + 3𝑛
3 9
4 4
⟹ 𝐴 + 𝐵𝑛 + 𝐶 ∙ 3𝑛 − 4𝐴 + 4𝐵 − 4𝐵𝑛 − 𝐶 ∙ 3𝑛 + 4𝐴 − 8𝐵 + 4𝐵𝑛 + 𝐶 ∙ 3𝑛 = 𝑛 + 3𝑛
3 9
4 4
⟹ (𝐴 − 4𝐵) + (𝐵)𝑛 + (𝐶 − 𝐶 + 𝐶) 3𝑛 = 𝑛 + 3𝑛
3 9
𝑪
⟹ (𝑨 − 𝟒𝑩) + (𝑩)𝑛 + ( ) 3𝑛 = 𝟎 + (𝟏)𝑛 + (𝟏)3𝑛
𝟗
Step 6:
Compare coefficients of 3𝑛 , we get
𝐶
=1⟹𝑪=𝟗
9
Compare coefficients of 𝑛, we get 𝑩 = 𝟏.
Compare constant terms (terms without 𝑛), we get
𝐴 − 4𝐵 = 0
⟹ 𝐴 − 4(1) = 0
⟹𝐴−4=0⟹𝑨=𝟒
(𝑝)
Substitute the obtained values of 𝐴, 𝐵 and 𝐶 in 𝑎𝑛 , we get
(𝑝)
𝑎 𝑛 = 𝟒 + 𝒏 + 𝟗 ∙ 𝟑𝒏
Step 7:
(ℎ) (𝑝)
The general solution is 𝑎𝑛 = 𝑎𝑛 + 𝑎𝑛 = (𝑨𝟏 + 𝑨𝟐 𝒏)(𝟐)𝒏 + 𝟒 + 𝒏 + 𝟗 ∙ 𝟑𝒏 .

Important note
(𝑝) (ℎ) (𝑝)
If there is any term of 𝑎𝑛 matching with the term of 𝑎𝑛 then modify 𝑎𝑛 by multiplying
suitable power of 𝑛. In other words, if there is same term in homogeneous solution and
particular solution then modify the particular solution by multiplying suitable power of 𝑛 at
initial step. (SEE NEXT QUESTION)

Question
Solve the recurrence relation 𝑎𝑛+2 − 2𝑎𝑛+1 + 𝑎𝑛 = 3𝑛 + 5.
Answer
Step 1:
The order of given recurrence relation is (𝑛 + 2) − 𝑛 = 2.
Set 𝑎𝑛+2 = 𝛼 2 .
Set 𝑎𝑛+1 = 𝛼.
Set 𝑎𝑛 = 1.
Then, the characteristic equation is 𝛼 2 − 2𝛼 + 1 = 0.
Step 2:
Compare the equation 𝛼 2 − 2𝛼 + 1 = 0 with the general equation 𝑎𝛼 2 + 𝑏𝛼 + 𝑐 = 0, we
have 𝑎 = 1 , 𝑏 = −2 , 𝑐 = 1. Then, the roots are given by

−𝑏 ± √𝑏 2 − 4𝑎𝑐
𝛼=
2𝑎
−(−2) ± √(−2)2 − 4(1)(1)
𝛼=
2(1)
2 ± √4 − 4
𝛼=
2
 2 ± √0
𝛼=
2
2±0
𝛼=
2
2−0 2+0
𝛼1 = , 𝛼2 =
2 2
𝛼1 = 1 , 𝛼2 = 1
The roots 𝛼1 = 1 and 𝛼2 = 1 are real and equal.
Step 3:
Let 𝛼 = 1. The solution to the given recurrence relation is given by
(ℎ)
𝑎𝑛 = (𝐴1 + 𝐴2 𝑛)(𝛼)𝑛
(ℎ)
𝑎𝑛 = (𝐴1 + 𝐴2 𝑛)(1)𝑛
(ℎ)
𝑎𝑛 = 𝐴1 ⋅ 𝟏 + 𝐴2 ⋅ 𝒏
Step 4:
Use the method of undetermined coefficients to find the particular solution.
The right-hand side of the given recurrence relation is 𝑓(𝑛) = 3𝑛 + 5.
(𝑝)
Depending on the form of 𝑓(𝑛), we consider a trial solution 𝑎𝑛 = 𝐴 + 𝐵𝑛 where 𝐴 and 𝐵
are unknown coefficients.
(𝑝)
𝑎𝑛 = 𝐴 + 𝐵𝑛 = 𝐴 ⋅ 𝟏 + 𝐵 ⋅ 𝒏.
(ℎ) (𝑝) (𝑝)
Since 𝟏 and 𝒏 are matching terms (or functions) in 𝑎𝑛 and 𝑎𝑛 , we need to modify 𝑎𝑛 by
multiplying 𝒏 to the matching term (or function). So, we have,
(𝑝)
𝑎𝑛 = 𝐴 ⋅ 𝒏 + 𝐵 ⋅ 𝒏𝟐
(ℎ) (𝑝)
Since 𝒏 is matching term (or function) in 𝑎𝑛 and modified 𝑎𝑛 , again we need to modify
(𝑝)
𝑎𝑛 by multiplying 𝒏 to the matching term (or function). So, we have,
(𝑝)
𝑎𝑛 = 𝐴 ⋅ 𝒏𝟐 + 𝐵 ⋅ 𝒏𝟑
(ℎ) (𝑝)
Note that now there is no matching term in 𝑎𝑛 and modified 𝑎𝑛 . That is, the appropriate
trial solution is
(𝑝)
𝑎𝑛 = 𝐴 ⋅ 𝒏𝟐 + 𝐵 ⋅ 𝒏𝟑
Step 5:
(𝑝)
Replace 𝑛 by 𝑛 + 1 in 𝑎𝑛 ,
(𝑝)
𝑎𝑛+1 = 𝐴(𝑛 + 1)2 + 𝐵(𝑛 + 1)3
 = 𝐴(𝑛2 + 2𝑛 + 1) + 𝐵(𝑛3 + 1 + 3𝑛2 + 3𝑛)
= 𝐴𝑛2 + 2𝐴𝑛 + 𝐴 + 𝐵𝑛3 + 𝐵 + 3𝐵𝑛2 + 3𝐵𝑛
= 𝐵𝑛3 + (𝐴 + 3𝐵)𝑛2 + (2𝐴 + 3𝐵)𝑛 + (𝐴 + 𝐵)
(𝑝)
Replace 𝑛 by 𝑛 + 2 in 𝑎𝑛 ,
(𝑝)
𝑎𝑛+2 = 𝐴(𝑛 + 2)2 + 𝐵(𝑛 + 2)3
= 𝐴(𝑛2 + 4𝑛 + 4) + 𝐵(𝑛3 + 8 + 6𝑛2 + 12𝑛)
= 𝐴𝑛2 + 4𝐴𝑛 + 4𝐴 + 𝐵𝑛3 + 8𝐵 + 6𝐵𝑛2 + 12𝐵𝑛
= 𝐵𝑛3 + (𝐴 + 6𝐵)𝑛2 + (4𝐴 + 12𝐵)𝑛 + (4𝐴 + 8𝐵)
Step 6:
Substitute all obtained expressions into the given recurrence relation.
𝑎𝑛+2 − 2𝑎𝑛+1 + 𝑎𝑛 = 3𝑛 + 5
⟹ 𝐵𝑛3 + (𝐴 + 6𝐵)𝑛2 + (4𝐴 + 12𝐵)𝑛 + (4𝐴 + 8𝐵)
−2[𝐵𝑛3 + (𝐴 + 3𝐵)𝑛2 + (2𝐴 + 3𝐵)𝑛 + (𝐴 + 𝐵)] + 𝐴𝑛2 + 𝐵𝑛3 = 3𝑛 + 5
⟹ 𝐵𝑛3 + (𝐴 + 6𝐵)𝑛2 + (4𝐴 + 12𝐵)𝑛 + (4𝐴 + 8𝐵)
−2𝐵𝑛3 − (2𝐴 + 6𝐵)𝑛2 − (4𝐴 + 6𝐵)𝑛 − (2𝐴 + 2𝐵) + 𝐴𝑛2 + 𝐵𝑛3 = 3𝑛 + 5
⟹ (𝐵 − 2𝐵 + 𝐵)𝑛3 + (𝐴 + 6𝐵 − 2𝐴 − 6𝐵 + 𝐴)𝑛2 + (4𝐴 + 12𝐵 − 4𝐴 − 6𝐵)𝑛
+4𝐴 + 8𝐵 − 2𝐴 − 2𝐵 = 3𝑛 + 5
⟹ (0)𝑛3 + (0)𝑛2 + (6𝐵)𝑛 + 2𝐴 + 6𝐵 = 3𝑛 + 5
⟹ 𝟔𝑩𝑛 + 𝟐𝑨 + 𝟔𝑩 = 𝟑𝑛 + 𝟓
Step 7:
Compare the coefficient of 𝑛, we get,
3 𝟏
6𝐵 = 3 ⟹ 𝐵 = ⟹𝑩=
6 𝟐
Compare constant terms (terms without 𝑛), we get,
2𝐴 + 6𝐵 = 5
1
⟹ 2𝐴 + 6 ( ) = 5
2
⟹ 2𝐴 + 3 = 5
⟹ 2𝐴 = 2 ⟹ 𝑨 = 𝟏
(𝑝)
Substitute the obtained values of 𝐴 and 𝐵 into 𝑎𝑛 , we get
 (𝑝) 𝟏
𝑎𝑛 = 𝒏𝟐 + 𝒏𝟑
𝟐
Step 8:
(ℎ) (𝑝) 𝟏
The general solution is 𝑎𝑛 = 𝑎𝑛 + 𝑎𝑛 = 𝑨𝟏 + 𝑨𝟐 𝒏 + 𝒏𝟐 + 𝟐 𝒏𝟑 .

TRY YOURSELF