©Dr.

Vishal Patil
Asst Professor-JU
RECURRENCE RELATIONS
MODULE-3
DISCRETE MATHEMATICS & GRAPH THEORY

24-03-2023 DISCRETE MATHEMATICS & GRAPH THEORY 1

 CONTENT

❑Recurrence Relations:

❑First - Order Linear Recurrence Relation.

©Dr. Vishal Patil

❑Second - Order Linear Homogeneous Recurrence Relations with Constant Coefficients.

Asst Professor-JU
❑Non-Homogeneous Recurrence Relations.

❑Method of Generating Functions

24-03-2023 DISCRETE MATHEMATICS & GRAPH THEORY 2

 Recurrence Relation
First, we consider for solution recurrence relations of the form
---------(1)
where c is a known constant and 𝑓(𝑛) is a known function. Such a relation is called a

©Dr. Vishal Patil

Asst Professor-JU
linear recurrence relation of first-order with constant coefficient.

If 𝑓(𝑛) = 0 , the relation is called homogeneous; otherwise, it is called non-

homogeneous (or inhomogeneous).

The relation (1) can be solved in a trivial way. First, we note that this relation may be
rewritten as (by changing n to n + 1)
--------(2)
For n=0,1,2,3,..., this relation yields, respectively.
24-03-2023 DISCRETE MATHEMATICS & GRAPH THEORY 3
 ©Dr. Vishal Patil
Asst Professor-JU
and so on. Examining these, we obtain, by induction,

-----(3)
This is the general solution of the recurrence relation (2) which is equivalent to the relation ( If f(n) = 0, that is if
the recurrence relation is homogeneous, the solution (3) becomes
-----(4)
The solutions (3) and (4) yield particular solutions if an is specified. The specified 𝑎𝑜 is called the initial condition.
24-03-2023 DISCRETE MATHEMATICS & GRAPH THEORY 4
 1. Solve the recurrence relation 𝑎𝑛+1 = 4𝑎𝑛 , for given that 𝑎0 = 3.

The given relation is homogeneous. Its general solution is

---------(i)

©Dr. Vishal Patil

Asst Professor-JU
It is given that 𝑎0 = 3. Putting this into (i), we get

---------(ii)

This is the particular solution of the given relation, satisfying the initial condition 𝑎0 = 3

24-03-2023 DISCRETE MATHEMATICS & GRAPH THEORY 5

 2. Solve the recurrence relation 𝑎𝑛 = 7𝑎𝑛−1 , where 𝑛 ≥ 1, given that a₂
= 98.
The given relation may be rewritten 𝑎𝑛+1 = 7𝑎𝑛 , för 𝑛 ≥ 0. The general solution of
homogeneous relation is

©Dr. Vishal Patil

Asst Professor-JU
---------(i)

It is given that a₂ = 98. Using this in (i) we get 98 = 𝑎₂ = 72 𝑎0 so that 𝑎0 = 2. Putting into the general
solution (i) we get the particular solution

𝑎𝑛 = 2 × 7𝑛 ---------(ii)

This is the solution of the given relation under the condition a₂ = 98..

24-03-2023 DISCRETE MATHEMATICS & GRAPH THEORY 6

 3. Solve the recurrence relation 𝑎𝑛 − 3𝑎𝑛−1 = 5 × 7𝑛 for 𝑛 ≥ 1 given
that 𝑎0 = 2

©Dr. Vishal Patil

Asst Professor-JU
24-03-2023 DISCRETE MATHEMATICS & GRAPH THEORY 7
 3. Solve the recurrence relation 𝑎𝑛 − 3𝑎𝑛−1 = 5 × 3𝑛 for 𝑛 ≥ 1 given
that 𝑎0 = 2
The given relation may be rewritten as

©Dr. Vishal Patil

Asst Professor-JU
The general solution for this relation

This is the required solution.

Substituting for 𝑎0 and 𝑓(𝑛), 𝑛 = 1,2, … 𝑛 in this, we get 4. Solve the recurrence relation 𝒂𝒏 − 𝟑𝒂𝒏−𝟏 = 𝟓 × 𝟕𝒏
for 𝒏 ≥ 𝟏, given that 𝒂𝟎 = 2 . (Homework)

24-03-2023 DISCRETE MATHEMATICS & GRAPH THEORY 8

 5. The number of virus affected files in a system is 1000 (to start with) and
this increases 250% every two hours. Use a recurrence relation to determine the
number of virus affected files in the system after one day.
In the beginning, the number of virus affected files is 1000. Let us denote this by 𝑎0 Let

©Dr. Vishal Patil

𝑎𝑛 denote the number of virus affected files after 24 hours. Then the number increases by 𝑎𝑛 x 250/100,

Asst Professor-JU
in the next two hours. Thus, after 2n + 2 hours, the number is

This is the recurrence relation for the number of virus affected files. Solving this relation, we get

This gives the number of virus affected files after 24 hours. From this, we get (for n =12)

This is the number of virus affected files after one day (24 hours).
24-03-2023 DISCRETE MATHEMATICS & GRAPH THEORY 9
 6. Suppose that there are n ≥ 2 person sat a party and that each of these
persons shakes hands (exactly once) with all of the other persons present. Using a
recurrence relation find the number of hand shakes.
Let 𝑎𝑛−2 denote the number of hand shakes among the n ≥ 2 persons present. (If n=2,
the number of handshakes is 1: that is 𝑎𝑜 = 1). If a new person joins the party, he will shake hands with

©Dr. Vishal Patil

Asst Professor-JU
each of the 𝑛 persons already present. Thus, the number of hand shakes increases by 𝑛 when the number
of persons changes to 𝑛 + 1 from 𝑛. Thus,

Setting f(m) = m + 1, this reads

The general solution of this nonhomogeneous recurrence relation is

24-03-2023 DISCRETE MATHEMATICS & GRAPH THEORY 10

 Since 𝑎𝑜 = 1, this becomes

©Dr. Vishal Patil

Asst Professor-JU
This is the number of handshakes in the party when 𝑛 ≥ 2 persons are present."

24-03-2023 DISCRETE MATHEMATICS & GRAPH THEORY 11

 7. There are 3 pegs fixed vertically on a table, and n circular disks having
holes at their centers and having increasing diameters are slipped onto one of these
pegs, with the largest disk at the bottom. The disks are to be transferred, one at a time,
onto another peg with the condition that at no time a larger disk is put on a smaller disk.
Determine the number of moves for the transfer of all the n disks, so that at the end the

©Dr. Vishal Patil

disks are in their original order.

Asst Professor-JU
Let 𝑎𝑛 be the number of moves required to transfer 𝑛 disks. Evidently, 𝑎0 = 0. Let us
denote the peg on which the disks are originally located as 𝑃1 . To effect the transfer, for 𝑛 ≥ 1, we fin
transfer the top 𝑛 − 1 disks to a vacant peg, say 𝑃2 , in the prescribed manner. This involves 𝑎𝑛−1 moves.
Then we transfer the 𝑛𝑡ℎ disk to the other vacant peg. say 𝑃3 . This involves 1 move. Lastly, we transfer the
𝑛 − 1 disks from peg 𝑃₂ to the peg 𝑃3 , in the prescribed manner. This involves 𝑎𝑛−1 moves. Thus, the total
number of moves involved in the transfer of 𝑛 disks is
24-03-2023 DISCRETE MATHEMATICS & GRAPH THEORY 12
or, equivalently

©Dr. Vishal Patil

Asst Professor-JU
The general solution for this nonhomogeneous recurrence relation is

This is the required number of moves.

24-03-2023 DISCRETE MATHEMATICS & GRAPH THEORY 13

The Second-Order Linear Homogeneous Recurrence Relation with constant Coefficients
We now consider a method of solving recurrence relations of the form

𝑪𝒏 𝒂𝒏 + 𝑪𝒏−𝟏 𝒂𝒏−𝟏 + 𝑪𝒏−𝟐 𝒂𝒏−𝟐 = 𝟎, 𝒏 ≥ 𝟐.----------(1)

©Dr. Vishal Patil

Asst Professor-JU
where 𝐶𝑛, 𝐶𝑛 − 1 𝑎𝑛𝑑 𝐶𝑛 − 2 are real constants with 𝐶𝑛 ≠ 0. A relation of this types is called second-
order linear homogeneous recurrence relation with constant coefficients.
We seek a solution of relation (1) in the form 𝑎𝑛 = 𝑐𝑘 𝑛 where 𝑐 ≠ 0 and 𝑘 ≠ 0. Putting 𝑎𝑛 = 𝑐𝑘 𝑛 in (1) we get ,

𝐶𝑛 𝑐𝑘 𝑛 + 𝐶𝑛−1 𝑐𝑘 𝑛−1 + 𝐶𝑛−2 𝑐𝑘 𝑛−2 = 0, 𝑛 ≥ 2.

𝑪𝒏 𝒄𝒌𝟐 + 𝑪𝒏−𝟏 𝒌𝟏 + 𝑪𝒏−𝟐 = 𝟎, 𝒏 ≥ 𝟐.----------(2)

Thus, 𝑎𝑛 = 𝑐𝑘 𝑛 is a solution of (1) if 𝑘 satisfies the quadratic equation (2). This quadratic equation is
called the auxiliary equation or the characteristic equation for the relation (1).Now, the following three
cases arise
24-03-2023 DISCRETE MATHEMATICS & GRAPH THEORY 14
 Solution of The Second Order Linear Recurrence Relation
To find the solution, we follow the Characteristic Roots Technique.
Let given recurrence relation 𝑎𝑛 + 𝛼𝑎𝑛−1 + 𝛽𝑎𝑛−2 = 0, then the characteristic polynomial is 𝑥 2 + 𝛼𝑥 + 𝛽, giving
the characteristic equation 𝒙𝟐 + 𝜶𝒙 + 𝜷 = 𝟎

1. If 𝑥1 & 𝑥2 are two distinct roots of the characteristic polynomial (i.e., solution to the characteristic equation), then

©Dr. Vishal Patil

Asst Professor-JU
the solution to the recurrence relation is
𝒂𝒏 = 𝒂𝒙𝒏𝟏 + 𝒃𝒙𝒏𝟐 Where 𝑎 & 𝑏 are constant determined by the initial conditions

2. If 𝑥1 & 𝑥2 are real and equal roots of the characteristic polynomial (i.e., solution to the characteristic equation),
then the solution to the recurrence relation is, 𝒂𝒏 = 𝒂𝒙𝒏 + 𝒏𝒃𝒙𝒏

3. If 𝑥1 & 𝑥2 are Complex roots [𝑥 = 𝑝 ± 𝑖𝑞 of the characteristic polynomial (i.e., solution to the characteristic
equation), then the solution to the recurrence relation is
𝒂𝒏 = 𝒓𝒏 [𝒂 𝒄𝒐𝒔 𝒏𝜽 + 𝒃 𝒔𝒊𝒏 𝒏𝜽]
𝑞
Where 𝑟 = 𝑝2 + 𝑞 2 & 𝜃 = tan−1 𝑝 Where 𝑎 & 𝑏 are constant determined by the initial conditions
24-03-2023 DISCRETE MATHEMATICS & GRAPH THEORY 15
 1. Solve the recurrence relation 𝒂𝒏 = 𝟕𝒂𝒏−𝟏 − 𝟏𝟎𝒂𝒏−𝟐 with 𝒂𝟎 = 𝟐 and
𝒂𝟏 = 𝟑.
Rewrite the recurrence relation To find 𝑎 & 𝑏, plug in 𝑛 = 0 & 𝑛 = 1 to get a
𝑎𝑛 − 7𝑎𝑛−1 + 10𝑎𝑛−2 = 0 system of two equation with two unknowns

©Dr. Vishal Patil

Asst Professor-JU
Now form the characteristic equation 𝑎0 = 𝑎20 + 𝑏50
𝑥 2 − 7𝑥 + 10 = 0 2 = 𝑎 + 𝑏 −−−−− −(1)

And we solve for x i.e., 𝑎1 = 𝑎21 + 𝑏51

𝑥−2 𝑥−5 =0 3 = 2𝑎 + 5𝑏 −−−− −(2)

So 𝑥 = 2 & 𝑥 = 5 are characteristic roots. Thus, the solution to Solving this system gives 𝑎 = 7 and 𝑏 = − 1
3 3
recurrence relation will have the form
so the solution to the recurrence relation is
𝑎𝑛 = 𝑎𝑥1𝑛 + 𝑏𝑥2𝑛
7 𝑛 1 𝑛
𝑎𝑛 = 2 − 5
𝑎𝑛 = 𝑎2𝑛 + 𝑏5𝑛 3 3
24-03-2023 DISCRETE MATHEMATICS & GRAPH THEORY 16
• 2. Solve the recurrence relation 𝒃𝒏 = 𝟐𝒃𝒏−𝟏 − 𝒃𝒏−𝟐 given 𝒃𝟏 = 𝟏. 𝟓 & 𝒃𝟐 = 𝟑
Let us rewrite the given recurrence relation as
𝑏𝑛 − 2𝑏𝑛−1 + 𝑏𝑛−2 = 0
Now we form the characteristic equation
𝑥 2 − 2𝑥 + 1 = 0

©Dr. Vishal Patil

Asst Professor-JU
2
And we solve for x i.e., 𝑥−1 =0
So 𝑥 = 1, & 𝑥 = 1 are characteristic roots. Thus, the solution to recurrence relation will have the form
𝑏𝑛 = 𝑎𝑥 𝑛 + 𝑛𝑏𝑥 𝑛
𝑏𝑛 = 𝑎1𝑛 + 𝑛𝑏1𝑛
To find 𝑎 & 𝑏, plug in 𝑛 = 1 & 𝑛 = 2 to get a system of two equation with two unknowns
𝑏1 = 𝑎11 + 1𝑏11
1.5 = 𝑎 + 𝑏 −−−− −(1)
𝑏2 = 𝑎12 + 2𝑏12
3 = 𝑎 + 2𝑏 −−−− −(2)
Solving this system gives 𝑎 = 0 and 𝑏 = 1.5 so the solution to the recurrence relation is
𝑏𝑛 = (0)1𝑛 +𝑛 1.5 1𝑛
𝑏𝑛 = 1.5𝑛
24-03-2023 DISCRETE MATHEMATICS & GRAPH THEORY 17
3. Solve the recurrence relation 𝒂𝒏 = 𝟔𝒂𝒏−𝟏 − 𝟗𝒂𝒏−𝟐 with the initial conditions 𝒂𝟎 = 𝟏 and 𝒂𝟏 = 𝟒
Solution
Let us rewrite the given recurrence relation as
𝑎𝑛 − 6𝑎𝑛−1 + 9𝑎𝑛−2 = 0
Now we form the characteristic equation
𝑥 2 − 6𝑥 + 9 = 0

©Dr. Vishal Patil

Asst Professor-JU
And we solve for x i.e.,
2
𝑥−3 =0
So 𝑥 = 3, & 𝑥 = 3 are characteristic roots. Thus, the solution to recurrence relation will have the form
𝑎𝑛 = 𝑎𝑥 𝑛 + 𝑛𝑏𝑥 𝑛
𝑎𝑛 = 𝑎3𝑛 + 𝑛𝑏3𝑛
To find 𝑎 & 𝑏, plug in 𝑛 = 0 & 𝑛 = 1 to get a system of two equation with two unknowns
𝑎0 = 𝑎30 + (0)𝑏30
1=𝑎
𝑎1 = 𝑎31 + 1𝑏31
4 = 1 3 + 3𝑏
1
𝑏=
3
1
solving this system gives 𝑎 = 1 and 𝑏 = 3 so the solution to the recurrence relation is
𝑛
1 𝑛 18
𝑎𝑛 = 3 + 𝑛3
4. Solve the recurrence relation 𝒂𝒏 = 𝟑𝒂𝒏−𝟏 − 𝟐𝒂𝒏 ∀𝒏 ≥ 𝟐 given 𝒂𝟏 = 𝟓 & 𝒂𝟐 = 𝟑 [homework]
5. Solve the recurrence relation 𝑫𝒏 = 𝒃𝑫𝒏−𝟏 − 𝒃𝟐 𝑫𝒏−𝟐 ∀𝒏 ≥ 𝟑 given
𝑫𝟏 = 𝒃 > 𝟎 & 𝑫𝟐 = 𝟎
Solution
Let us rewrite the given recurrence relation as
𝐷𝑛 − 𝑏𝐷𝑛−1 + 𝑏2 𝐷𝑛−2 = 0

©Dr. Vishal Patil

Asst Professor-JU
Now we form the characteristic equation
𝑥 2 − 𝑏𝑥 + 𝑏2 = 0
And we solve for x i.e.,
−𝑏 ± 𝑏2 − 4𝑎𝑐
𝑥 =
2𝑎
− −𝑏 ± −𝑏 2 − 4 1 𝑏2
𝑥 =
2 1
𝑏 ± 𝑏2 − 4 𝑏2
𝑥 =
2 1
𝑏±𝑏 1−4
𝑥 =
2
𝑏 ± 𝑏𝑖 3
𝑥 =
2 19
 1 3
𝑥 = 2𝑏 ± 𝑖 𝑏 Thus, the solution to recurrence relation will have the form
2

𝐷𝑛 = 𝑟 𝑛 [𝑎 cos 𝑛𝜃 + 𝑏 sin 𝑛𝜃]

To find 𝑎 & 𝑏, put in 𝑛 = 1 & 𝑛 = 2 to get a system of two equation with two unknowns

©Dr. Vishal Patil

Asst Professor-JU
2 2
1 3 𝑏2 3𝑏2 4 2
𝑟= 𝑝2 + 𝑞2 = 𝑏 + 𝑏 = + = 𝑏 =𝑏
2 2 4 4 4

3
𝑞 𝑏 𝜋
𝜃 = tan −1 = tan −1 2 = tan−1 3 =
𝑝 1 3
2 𝑏
𝐷𝑛 = 𝑟 𝑛 [𝐴 cos 𝑛𝜃 + 𝐵 sin 𝑛𝜃]
𝐷1 = 𝑟[𝐴 cos 𝜃 + 𝐵 sin 𝜃]
𝜋 𝜋
𝑏 = 𝑏 𝐴 cos + 𝐵 sin
3 3
20
 1 3
1=𝐴 +𝐵
2 2
2 = 𝐴 + 3𝐵 −−−− −(1)
𝐷𝑛 = 𝑟 𝑛 [𝐴 cos 𝑛𝜃 + 𝐵 sin 𝑛𝜃]
𝐷2 = 𝑟 2 [𝐴 cos 2𝜃 + 𝐵 sin 2𝜃]

©Dr. Vishal Patil

Asst Professor-JU
𝜋 𝜋
0= 𝑏2 𝐴 cos 2 + 𝐵 sin 2
3 3

1 3
0=𝐴 − +𝐵
2 2

0 = −𝐴 + 𝐵 3 −−−− −(2)

1
solving this system gives 𝐴 = 1 and 𝐵 = so the solution to the recurrence relation is
3

𝜋 1 𝜋
𝐷𝑛 = 𝑏𝑛 [cos 𝑛 + sin 𝑛 ]
3 3 3
21
6. Solve the recurrence relation 𝑭𝒏+𝟐 = 𝑭𝒏+𝟏 + 𝑭𝒏 ∀𝒏 ≥ 𝟎 given 𝑭𝟎 = 𝟎, 𝑭𝟏 = 𝟏
Solution
Let us rewrite the given recurrence relation as
𝐹𝑛+2 − 𝐹𝑛+1 − 𝐹𝑛 = 0
𝐹𝑛 − 𝐹𝑛−1 − 𝐹𝑛−2 = 0

©Dr. Vishal Patil

Now we form the characteristic equation

Asst Professor-JU
𝑥2 − 𝑥 − 1 = 0
And we solve for x i.e.,
−𝑏 ± 𝑏2 − 4𝑎𝑐
𝑥=
2𝑎
− −1 ± −1 2 − 4 1 −1
𝑥=
2
1± 5
𝑥=
2
1+ 5 1− 5
So 𝑥 = 2
, &𝑥 = 2
are characteristic roots. Thus, the solution to recurrence relation will have the form
𝐹𝑛 = 𝑎𝑥1𝑛 + 𝑏𝑥2𝑛
𝑛 𝑛
1+ 5 1− 5
𝐹𝑛 = 𝑎 +𝑏
2 2 22
To find 𝑎 & 𝑏, put in 𝑛 = 0 & 𝑛 = 1 to get a system of two equation with two unknowns

0 0
1+ 5 1− 5
𝐹0 = 𝑎 +𝑏
2 2
0 = 𝑎 + 𝑏 −−−− −(1)

©Dr. Vishal Patil

Asst Professor-JU
1 1
1+ 5 1− 5
𝐹1 = 𝑎 +𝑏
2 2

1+ 5 1− 5
1=𝑎 +𝑏 −−−− −(2)
2 2
1 −1
solving this system gives 𝑎 = and 𝑏 = so the solution to the recurrence relation is
5 5

𝑛 𝑛
1 1+ 5 −1 1 − 5
𝐹𝑛 = +
5 2 5 2

𝑛 𝑛
1 1+ 5 1− 5
𝐹𝑛 = − 23
5 2 2
 Nonhomogeneous Recurrence Relations of second and higher orders

In this Section we illustrate a method of solving second and higher order linear nonhomogeneous recurrence relations with constant
coefficients, which are of the form.
𝑐𝑛 𝑎𝑛 + 𝑐𝑛−1 𝑎𝑛−1 + 𝑐𝑛−2 𝑎𝑛−2 + ⋯ + 𝑐𝑛−𝑘 𝑎𝑛−𝑘 = 𝑓 𝑛 𝑓𝑜𝑟 𝑛 ≥ 𝑘 ≥ 2. (1)

©Dr. Vishal Patil

Asst Professor-JU
where 𝑐𝑛 , 𝑐𝑛−1 , ….,𝑐𝑛−𝑘 are real constants with 𝑐𝑛 ≠ 0, and 𝑓 𝑛 is a given real-valued function of 𝑛. A general solution of the
recurrence relation (1) is given by

(ℎ) (𝑝)
𝑎𝑛 = 𝑎𝑛 + 𝑎𝑛 2

(ℎ) (𝑝)
where 𝑎𝑛 is the general solution of the homogeneous part of the relation (1), namely the relation (1) with 𝑓 𝑛 = 0 and 𝑎𝑛 is any
particular solution of the relation (1).*

24-03-2023 DISCRETE MATHEMATICS & GRAPH THEORY 24

 (ℎ)
The part 𝑎𝑛 of the solution (2) can be obtained by the method illustrated in Sections before. But, the determination of a
(𝑝)
for arbitrary 𝑓 𝑛 is a tedious task. It is only in some special cases that we can find 𝑎𝑛 in a straight forward way. The
following are some of these special cases.

(1) Suppose 𝒇 𝒏 is a polynomial of degree 𝒒 and 1 is not a root of the characteristic equation of the homogeneous

©Dr. Vishal Patil

Asst Professor-JU
(𝒑)
part of the relation (1). In this case, 𝒂𝒏 1 taken in the form

(𝒑)
𝒂𝒏 = 𝑨𝟎 + 𝑨𝟏 𝒏 + 𝑨𝟐 𝒏𝟐 + ⋯ + 𝑨𝒒 𝒏𝒒 (𝟑)

(𝑝)
where 𝐴0 , 𝐴1 , 𝐴2 , …, 𝐴𝑞 are constants to be evaluated by using the fact that 𝑎𝑛 = 𝑎𝑛 satisfies the relation (1).

(2) Suppose 𝒇 𝒏 is a polynomial of degree 𝒒 and 1 is a root of multiplicity 𝒎 of the characteristic equation of the
(𝒑)
homogeneous part of the relation (1). In this case, 𝒂𝒏 is taken in the form

(𝒑)
𝒂𝒏 = 𝒏𝒎 𝑨𝟎 + 𝑨𝟏 𝒏 + 𝑨𝟐 𝒏𝟐 + ⋯ + 𝑨𝒒 𝒏𝒒 (𝟒)

(𝑝)
where 𝐴0 , 𝐴1 , 𝐴2 , …, 𝐴𝑞 are constants to be evaluated by using the fact that 𝑎𝑛 = 𝑎𝑛 satisfies the relation (1).
24-03-2023 DISCRETE MATHEMATICS & GRAPH THEORY 25
(3) Suppose 𝒇 𝒏 = 𝒂𝒃𝒏 where 𝒂 is a constant and 𝒃 is not a root of the characteristic equation of the
(𝒑)
homogeneous part of the relation (1). Then 𝒂𝒏 is taken in the form

(𝒑)
𝒂𝒏 = 𝑨𝟎 𝒃𝒏 (𝟓)

©Dr. Vishal Patil

Asst Professor-JU
(𝑝)
where 𝐴0 is a constant to be evaluated by using the fact that 𝑎𝑛 = 𝑎𝑛 satisfies the relation (1).

(4) Suppose 𝒇 𝒏 = 𝒂𝒃𝒏 where 𝒂 is a constant and 𝒃 is a root of multiplicity 𝒎 of the characteristic equation of
(𝒑)
the homogeneous part of the relation (1). Then 𝒂𝒏 is taken in the form

(𝒑)
𝒂𝒏 = 𝑨𝟎 𝒏𝒎 𝒃𝒏 (𝟔)

(𝑝)
where 𝐴0 is a constant to be evaluated by using the fact that 𝑎𝑛 = 𝑎𝑛 satisfies the relation (1).

24-03-2023 DISCRETE MATHEMATICS & GRAPH THEORY 26

 Solve the recurrence relation.

𝑎𝑛 − 𝑎𝑛−1 − 2𝑎𝑛−2 = 4 And 𝑎0 = 0, 𝑎1 = −1

For the homogeneous part of the given relation, the characteristic equation is
(𝒑)
𝒌𝟐 − 𝒌 − 𝟐 = 𝟎 𝒐𝒓 𝒌+𝟏 𝒌−𝟐 =𝟎 𝒂𝒏 = −𝟐 (𝒊𝒊𝒊)

©Dr. Vishal Patil

Therefore, the general solution for 𝑎𝑛 is

Asst Professor-JU
Whose roots are -1, 2. Therefore,
𝒉 𝒉
𝒉 𝒏
𝒂𝒏 = 𝒂𝒏 + 𝒂𝒏
𝒂𝒏 = 𝑨 −𝟏 𝒏 + 𝑩(𝟐 ቁ 𝒊
= 𝑨(−𝟏)𝒏 + 𝑩(𝟐𝒏 ) − 𝟐 (𝒊𝒗)
where A and B are arbitrary constants.
(𝑝) It is given that 𝑎0 = 0 and 𝑎1 = −1.
Keeping the RHS of the given relation in mind, we seek 𝑎𝑛 in the form
(𝒑) Using these initial conditions in (iv), we get
𝒂𝒏 = 𝑨𝟎 (𝒊𝒊)
𝟎 = 𝑨 + 𝑩 − 𝟐 𝒂𝒏𝒅 − 𝟏 = −𝑨 + 𝟐𝑩 − 𝟐
(𝑝)
Putting this 𝑎𝑛 for 𝑎𝑛 , 𝑎𝑛−1 , 𝑎𝑛−2 in the given relation, we get
These give 𝐴 = 𝐵 = 1. Putting these into (iv),
𝑨𝟎 − 𝑨𝟎 − 𝟐𝑨𝟎 = 𝟒
we get 𝒂𝒏 = (−𝟏)𝒏 + 𝟐𝒏 − 𝟐
which yields 𝐴0 = −2, Putting this into (ii), we get
This is the required solution.
24-03-2023 DISCRETE MATHEMATICS & GRAPH THEORY 27
 Solve the recurrence relation

𝑎𝑛+2 + 4𝑎𝑛+1 + 4𝑎𝑛 = 7, 𝑛 ≥ 0 Given 𝑎0 = 1, 𝑎1 = 2

whose roots are - 2, - 2 Therefore,
The given relation may be rewritten as (𝒉)
𝒂𝒏 = 𝑨 + 𝑩𝒏 (−𝟐)𝒏 (𝒊𝒊)

©Dr. Vishal Patil

Asst Professor-JU
𝒂𝒏 + 𝟒𝒂𝒏−𝟏 + 𝟒𝒂𝒏−𝟐 = 𝟕, for 𝒏 ≥ 𝟐 (𝒊)
where A and B are arbitrary constants.
For the homogeneous part of this relation,
(𝑝)
Keeping the RHS of the relation (i) in mind, we seek 𝑎𝑛 in the form
the characteristic equation is
(𝒑)
𝒂𝒏 = 𝑨𝟎 (𝒊𝒊𝒊)
𝒌𝟐 + 𝟒𝒌 + 𝟒 = 𝟎, or (𝒌 + 𝟐)𝟐 = 𝟎
(𝑝)
whose roots are - 2, - 2 Therefore, Putting this 𝑎𝑛 for 𝑎𝑛 , 𝑎𝑛−1 , 𝑎𝑛−2 in the relation (i), we get

(𝒉) 𝑨𝟎 + 𝟒𝑨𝟎 + 𝟒𝑨𝟎 = 𝟕

𝒂𝒏 = 𝑨 + 𝑩𝒏 (−𝟐)𝒏 (𝒊𝒊)
which yields 𝐴0 = 7/9. Putting this into (iii), we get
where A and B are arbitrary constants.
(𝒑) 𝟕
𝒂𝒏 = (𝒊𝒗)
𝟗
24-03-2023 DISCRETE MATHEMATICS & GRAPH THEORY 28
Therefore, the general solution for 𝑎𝑛 is
(𝒉) (𝒑)
𝒂𝒏 = 𝒂𝒏 + 𝒂𝒏

𝟕
- = 𝑨 + 𝑩𝒏 (−𝟐)𝒏 + (𝒗)
𝟗

©Dr. Vishal Patil

Asst Professor-JU
It is given that 𝑎0 = 1 and 𝑎1 = 2. Using these initial conditions in (v), we get

𝟕 𝟕
𝟏=𝑨+ , 𝟐 = 𝑨 + 𝑩 −𝟐 +
𝟗 𝟗

2 5
These give 𝐴 = and 𝐵 = − 6. Putting these into (v), we get
9

𝟐 𝟓 𝒏
𝟕
𝒂𝒏 = − 𝒏 (−𝟐) +
𝟗 𝟔 𝟗

This is the required solution.

24-03-2023 DISCRETE MATHEMATICS & GRAPH THEORY 29

 Solve the recurrence relation

𝑎𝑛+2 − 10𝑎𝑛+1 + 21𝑎𝑛 = 3𝑛2 − 2, 𝑛 ≥ 0.

For the homogeneous part of the given recurrence relation, the characteristic equation is" 𝑘 2 − 10𝑘 + 21 = 0 whose

©Dr. Vishal Patil

roots are 3 and 7. Therefore,

Asst Professor-JU
(ℎ)
𝑎𝑛 = 𝐴 × 3𝑛 + 𝐵 × 7𝑛 (𝑖) where A and B are arbitrary constants.
(𝑝)
Since the RHS of the given relation is a polynomial of degree 2, we seek 𝑎𝑛 in the form
(𝑝)
𝑎𝑛 = 𝐴0 + 𝐴1 𝑛 + 𝐴2 𝑛2 (𝑖𝑖)
(𝑝)
Putting this 𝑎𝑛 for 𝑎𝑛 in the given relation, we obtain

𝑨𝟎 + 𝑨𝟏 𝒏 + 𝟐 + 𝑨𝟐 (𝒏 + 𝟐)𝟐 − 𝟏𝟎 𝑨𝟎 + 𝑨𝟏 𝒏 + 𝟏 + 𝑨𝟐 𝒏 + 𝟏 𝟐
+ 𝟐𝟏 𝑨𝟎 + 𝑨𝟏 𝒏 + 𝑨𝟐 𝒏𝟐 = 𝟑𝒏𝟐 − 𝟐

Or 𝑨𝟐 𝒏𝟐 + (𝟒𝑨𝟐 +𝑨𝟏 )𝒏 + (𝟒𝑨𝟐 + 𝟐𝑨𝟏 + 𝑨𝟎 ) − 𝟏𝟎 𝑨𝟐 𝒏𝟐 + (𝟐𝑨𝟐 +𝑨𝟏 )𝒏 + (𝑨𝟐 + 𝑨𝟏 + 𝑨𝟎 ) +

𝟐𝟏 𝑨𝟐 𝒏𝟐 + 𝑨𝟏 𝒏 + 𝑨𝟎 = 𝟑𝒏𝟐 − 𝟐
24-03-2023 DISCRETE MATHEMATICS & GRAPH THEORY 30
Equating the corresponding terms on the two sides, we get

12𝐴2 = 3, −16𝐴2 + 12𝐴1 = 0, −6𝐴2 − 8𝐴1 + 12𝐴0 = −2

These give 𝐴2 = 1/4, 𝐴1 = 1/3, 𝐴0 = 47/9. Putting these into (ii), we get

©Dr. Vishal Patil

(𝑝) 1 2 1 47
(iii)

Asst Professor-JU
𝑎𝑛 = 𝑛 + .3 𝑛 +
4 9

Accordingly, the general solution for the given relation is

(ℎ) (𝑝)
𝑎𝑛 = 𝑎𝑛 + 𝑎𝑛

𝟏 𝟐 𝟏 𝟒𝟕
= 𝑨 × 𝟑𝒏 + 𝑩 × 𝟕𝒏 + 𝒏 + 𝒏+
𝟒 𝟑 𝟗

24-03-2023 DISCRETE MATHEMATICS & GRAPH THEORY 31

 Solve the recurrence relation
2 2
𝑎𝑛+2 − 5𝑎𝑛+1 + 6𝑎𝑛2 = 7𝑛 for 𝑛 ≥ 0 Given 𝑎0 = 𝑎1 = 1

Setting 𝑏𝑛 = 𝑎𝑛2 the given relation reads

©Dr. Vishal Patil

𝑏𝑛+2 − 5𝑏𝑛+1 + 6𝑏𝑛 = 7𝑛 (𝑖)

Asst Professor-JU
For the homogeneous part of this relation, the characteristic equation is

𝑘 2 − 5𝑘 + 6 = 0, or 𝑘 − 3 𝑘 − 2 = 0

whose roots are 3 and 2. Therefore,

(ℎ)
𝑏𝑛 = 𝐴 × 3𝑛 + 𝐵 × 2𝑛 (𝑖𝑖)

where A and B are arbitrary constants.

24-03-2023 DISCRETE MATHEMATICS & GRAPH THEORY 32

Since the RHS of (i) is a polynomial of degree 1, we take

(𝑝)
𝑏𝑛 = 𝐴0 + 𝐴1 𝑛 (𝑖𝑖𝑖)

Putting this for 𝑏𝑛 in (i), we get

©Dr. Vishal Patil

Asst Professor-JU
𝐴0 + 𝐴1 (𝑛 + 2) − 5 𝐴0 + 𝐴1 𝑛 + 1 + 6 𝐴0 + 𝐴1 𝑛 = 7𝑛

Equating the corresponding terms on both sides, we get

𝐴1 − 5𝐴1 + 6𝐴1 = 7 and (2𝐴1 +𝐴0 ))-5(𝐴1 +𝐴0 )+6𝐴0 =0

These give 𝐴1 = 7/2 and 𝐴0 = 21/4. Putting these into (iii), we get

(𝑝) 7 21
𝑏𝑛 = 2
𝑛 + 4
(𝑖𝑣)

24-03-2023 DISCRETE MATHEMATICS & GRAPH THEORY 33

Therefore, the general solution for 𝑏𝑛 is

(ℎ) (𝑝)
𝑏𝑛 = 𝑏𝑛 + 𝑏𝑛

7 21
= 𝐴 × 3𝑛 + 𝐵 × 2𝑛 + 𝑛 + (𝑣)
2 4

It is given that 𝑎0 = 𝑎1 = 1. These give 𝑏0 = 𝑎02 = 1, 𝑏1 = 𝑎12 = 1. Using these in (v), get

©Dr. Vishal Patil

Asst Professor-JU
21 7 21
1=𝐴+𝐵+ , 1 = 3𝐴 + 2𝐵 + 2 𝑛 +
4 4

Solving these, we get 𝐴 = 3/4 and 𝐵 = − 5 . Putting these into (v), we get

3 7 21
𝑏𝑛 = 4
× 3𝑛 − 5 × 2𝑛 + 2 𝑛 + 4
(𝑣𝑖)

This yield

1ൗ
3 𝑛 𝑛
7 21 2
𝑎𝑛 = ± 𝑏𝑛 = ± × 3 − 5 × 2 + 𝑛 +
4 2 4

This is the required solution.

24-03-2023 DISCRETE MATHEMATICS & GRAPH THEORY 34
 Solve the recurrence relation

𝑎𝑛 − 2𝑎𝑛−1 + 𝑎𝑛−2 = 5𝑛

For the homogeneous part of the given relation, the characteristic equation is

©Dr. Vishal Patil

𝑘 2 − 2𝑘 + 1 = 0, 2

Asst Professor-JU
𝑖. 𝑒. , 𝑘 − 1 =0

whose roots are 1, 1. Therefore,

(ℎ)
𝑎𝑛 = 𝐴 + 𝐵𝑛 × 1𝑛 (𝑖)

where A and B are arbitrary constants.

Since 1 is a root (of multiplicity 2) of the characteristic equation and the RHS of the given relation is a polynomial of
(𝑝)
degree 1, we seek 𝑎𝑛 in the form

(ℎ)
𝑎𝑛 = 𝑛2 𝐴0 + 𝐴1 𝑛 = 𝐴0 𝑛2 + 𝐴1 𝑛3 (𝑖𝑖)

24-03-2023 DISCRETE MATHEMATICS & GRAPH THEORY 35

 Putting this for 𝑎𝑛 in the given relation, we get

𝐴0 𝑛2 + 𝐴1 𝑛3 − 2 𝐴0 𝑛 − 1 2 + 𝐴1 𝑛 − 1 3 + 𝐴0 𝑛 − 2 2 + 𝐴1 𝑛 − 2 3 = 5𝑛

𝐴0 𝑛2 + 𝐴1 𝑛3 − 2 𝐴0 𝑛2 − 2𝑛 + 1 + 𝐴1 𝑛3 −3𝑛2 +3𝑛 − 1 + 𝐴0 𝑛2 − 4𝑛 + 4 + 𝐴1 𝑛3 − 6𝑛2 + 12𝑛 − 8 = 5𝑛

Equating the corresponding coefficients on the two sides, we get

©Dr. Vishal Patil

Asst Professor-JU
𝐴1 − 2𝐴1 + 𝐴1 = 0,

𝐴0 − 2𝐴0 + 6𝐴1 + 𝐴0 − 6𝐴1 = 0, Therefore, the general solution for 𝒂𝒏 is

(𝒉) (𝒑)
4𝐴0 − 6𝐴1 − 4𝐴0 + 12𝐴1 = 5, 𝒂𝒏 = 𝒂𝒏 + 𝒂𝒏

−2𝐴0 + 2𝐴1 + 4𝐴0 − 8𝐴1 = 0. 𝟓

=𝑨 + 𝑩𝒏 + 𝟔 𝒏𝟐 𝒏 + 𝟑
The last two of these give 𝐴1 = 5Τ6 and 𝐴0 = 5Τ2, Putting these into (ii),
we get

(𝑝) 5 5 5
𝑎𝑛 = 2 𝑛2 + 6 𝑛3 = 6 𝑛2 (𝑛 +

3) (𝑖𝑖𝑖)
24-03-2023 DISCRETE MATHEMATICS & GRAPH THEORY 36
 Solve the recurrence relation

𝑎𝑛+2 + 3𝑎𝑛+1 + 2𝑎𝑛 = 3𝑛 for 𝑛 ≥ 0 Given 𝑎0 = 0, 𝑎1 = 1.

For the homogeneous part of the given relation, the characteristic equation is

©Dr. Vishal Patil

𝑘 2 + 3𝑘 + 2 = 0, or 𝑘 + 2 𝑘 + 1 = 0

Asst Professor-JU
whose roots are -2, -1. Therefore,

(ℎ) 𝑛 𝑛
𝑎𝑛 = 𝐴 × −2 + 𝐵 × −1 (𝑖)

where A and B are arbitrary constants.

(𝑝)
Keeping the RHS of the given relation in mind, we seek 𝑎𝑛 in the form

(𝑝)
𝑎𝑛 = 𝐴0 × 3𝑛 (𝑖𝑖)

Putting this for 𝑎𝑛 in the given relation, we get

24-03-2023 DISCRETE MATHEMATICS & GRAPH THEORY 37

 𝐴0 × 3𝑛+2 + 3𝐴0 × 3𝑛+1 + 2𝐴0 × 3𝑛 = 3𝑛 ,

Or 𝐴0 × 32 + 3𝐴0 × 3 + 2𝐴0 = 1

(𝑝) 1
so that 𝐴0 = 1/20 Putting this into (ii), we get 𝑎𝑛 = × 3𝑛 (𝑖𝑖𝑖)
20

©Dr. Vishal Patil

(ℎ) (𝑝)
Therefore, the general solution of the given relation is 𝑎𝑛 = 𝑎𝑛 + 𝑎𝑛

Asst Professor-JU
𝑛 𝑛 1
=𝐴 × −2 + 𝐵 × −1 + 20 × 3𝑛 (𝑖𝑣)

It is given that 𝑎0 = 0, 𝑎𝑛𝑑 𝑎1 = 1. Using these in (iv), we get

1 3
0=𝐴+𝑏+ , 1 = −2𝐴 − 𝐵 +
20 20

Solving these, we get 𝐴 = − 4/5 and 𝐵 = 3/4. Putting these into (iv), we obtain

4 𝑛
3 𝑛
1
𝑎𝑛 = − × −2 + × −1 + × 3𝑛
5 4 20

This is the required solution.

24-03-2023 DISCRETE MATHEMATICS & GRAPH THEORY 38
 Solve the recurrence relation

𝑎𝑛 + 4𝑎𝑛−1 + 4𝑎𝑛−2 = 5 × −2 𝑛 , 𝑛≥2

For the homogeneous part of the given relation, the characteristic equation is

©Dr. Vishal Patil

𝑘 2 + 4𝑘 + 4 = 0, 𝑜𝑟 𝑘+2 2
= 0,

Asst Professor-JU
whose roots are -2, -2. Therefore,

(ℎ)
𝑎𝑛 = 𝐴 + 𝐵𝑛 −2 𝑛 , (𝑖)

where A and B are arbitrary constants.

We observe that the RHS of the given relation contains −2 𝑛 as a factor and −2 is a repeated root of the characteristic
(ℎ)
equation. As such, we seek 𝑎𝑛 in the form

(𝑝)
𝑎𝑛 = 𝐴0 𝑛2 −2 𝑛
(𝑖𝑖)

24-03-2023 DISCRETE MATHEMATICS & GRAPH THEORY 39

 ©Dr. Vishal Patil
Asst Professor-JU
24-03-2023 DISCRETE MATHEMATICS & GRAPH THEORY 40
 Method of Generating Functions
We now take-up the method of solving linear recurrence relations with constants coefficients through the use of
generating functions. We consider the cases of first-order and second-order relations separately.
Method of generating functions for First-order Recurrence Relations

©Dr. Vishal Patil

Asst Professor-JU
24-03-2023 DISCRETE MATHEMATICS & GRAPH THEORY 41
 ©Dr. Vishal Patil
Asst Professor-JU
24-03-2023 DISCRETE MATHEMATICS & GRAPH THEORY 42
 ©Dr. Vishal Patil
Asst Professor-JU
24-03-2023 DISCRETE MATHEMATICS & GRAPH THEORY 43
 Find the generating function for the recurrence relation

𝑎𝑛+1 − 𝑎𝑛 = 3𝑛 , 𝑛 ≥ 0, with 𝑎0 = 1. Hence solve the relation.

The given relation is of the form (1) with c = 1 and Φ(𝑛) = 3𝑛 . Therefore, a generating function for the relation is given

©Dr. Vishal Patil

by (see (6))

Asst Professor-JU
𝑎0 +𝑥𝑔 𝑥 𝑎0 +𝑥𝑔 𝑥
𝑓 𝑥 = = (𝑖) where,
1−𝑐𝑥 1−𝑥

∞ ∞

𝑔 𝑥 = ෍ Φ 𝑛 𝑥 𝑛 = ෍ 3𝑛 𝑥 𝑛
𝑛=0 𝑛=0
We immediately note that

𝑔 𝑥 = ෍ 3𝑛 𝑥 𝑛 = (1 − 3𝑥)−1
𝑛=0

24-03-2023 DISCRETE MATHEMATICS & GRAPH THEORY 44

Also, it is given that 𝑎0 = 1. Using these in (i), we get 1 − 2𝑥 1 1 1
= +
1 + 𝑥 1 − 3𝑥 −1 1 − 3𝑥 1 − 𝑥 2 1 − 𝑥 1 − 3𝑥
𝑓 𝑥 =
1−𝑥 Using this in (ii), we get
1 − 3𝑥 + 𝑥 1 − 2𝑥
= = 𝑖𝑖 1 1 1
1 − 3𝑥 1 − 𝑥 1 − 3𝑥 1 − 𝑥

©Dr. Vishal Patil

𝑓 𝑥 = +
2 1 − 𝑥 1 − 3𝑥

Asst Professor-JU
This is the required generating function.
(1−2𝑥) 𝐴 𝐵 ∞ ∞
Let = + 1−3𝑥 1
(1−3𝑥)(1−𝑥) 1−𝑥
= ෍ 𝑥 𝑛 + ෍ 3𝑛 𝑥 𝑛
2
𝑛=0 𝑛=0
∞
Then 1 − 2𝑥 = 𝐴 1 − 3𝑥 + 𝐵(1 − 𝑥) 1
= ෍ 1 + 3𝑛 𝑥 𝑛
Equating the corresponding coefficients in this, we get 2
𝑛=0

1 = 𝐴 + 𝐵, −2 = −3𝐴 − 𝐵 Accordingly, since 𝑓 𝑥 = σ∞ 𝑛

𝑛=0 𝑎𝑛 𝑥 , we find that

1
Solving these, we get 𝐴 = 𝐵 = 1/2. Thus, 𝑎𝑛 = (1 + 3𝑛 )
2
24-03-2023 DISCRETE MATHEMATICS & GRAPH THEORY 45
 Find the generating function for the recurrence relation

𝑎𝑛+1 − 𝑎𝑛 = 𝑛2 , 𝑛 ≥ 0, with 𝑎0 = 1. Hence solve it.

The given relation is of the form 𝑎𝑛+1 = 𝑐𝑎𝑛 + Φ 𝑛 , where 𝑐 = 1 and Φ 𝑛 = 𝑛2 . Therefore, a generating function for

©Dr. Vishal Patil

the relation is given by

Asst Professor-JU
𝑎0 +𝑥𝑔 𝑥 𝑎0 +𝑥𝑔 𝑥
𝑓 𝑥 = = (𝑖) where,
1−𝑐𝑥 1−𝑥
∞ ∞

𝑔 𝑥 = ෍ Φ 𝑛 𝑥 𝑛 = ෍ 𝑛2 𝑥 𝑛
𝑛=0 𝑛=0

This means that 𝑔(𝑥) is a generating function for the sequence

𝑛2 = 02 , 12 , 22 , 32 , … .

Hence, we have

𝑥 1+𝑥
𝑔 𝑥 = (ii)
(1−𝑥)3
24-03-2023 DISCRETE MATHEMATICS & GRAPH THEORY 46
Also, it is given that 𝑎0 = 1. Accordingly, (i) becomes

1 𝑥 2 (1 + 𝑥)
𝑓 𝑥 = 1+
1−𝑥 (1 − 𝑥)3

©Dr. Vishal Patil

(1 − 𝑥)3 +𝑥 2 (1 + 𝑥) 1 − 3𝑥 + 4𝑥 2

Asst Professor-JU
= = (𝑖𝑖𝑖)
(1 − 𝑥)4 (1 − 𝑥)4

This is the generating function for the given relation.

Now, we find from (iii) that

∞
3+𝑟 2
𝑓 𝑥 = 1 − 3𝑥 + 4𝑥 2 1 − 𝑥 −4 = 1 − 3𝑥 + 4𝑥 2 ෍ 𝑥 𝑖𝑣
𝑟
𝑛=0

Since 𝑓 𝑥 = σ∞ 𝑛
𝑛=0 𝑎𝑛 𝑥 , we find that

𝑎𝑛 = coefficient of 𝑥 𝑛 in the RHS of (𝑖𝑣)

24-03-2023 DISCRETE MATHEMATICS & GRAPH THEORY 47
 3+𝑛 3+𝑛−1 3+𝑛−2
= −3 +4
𝑛 𝑛−1 𝑛−2

(𝑛 + 3)(𝑛 + 2)(𝑛 + 1) 𝑛+2 𝑛+1 𝑛 (𝑛 + 1)(𝑛)(𝑛 − 1)

©Dr. Vishal Patil

= − 3. + 4.
3! 3! 3!

Asst Professor-JU
(𝑛 + 1)
= 𝑛2 + 5𝑛 + 6 − 3 𝑛2 + 2𝑛 + 4 𝑛2 − 𝑛
6

(𝑛 + 1)
= 2𝑛2 − 5𝑛 + 6
6
1
= 1 + 6 𝑛 𝑛 − 1 2𝑛 − 3 , on simplification.

This is the required solution.

24-03-2023 DISCRETE MATHEMATICS & GRAPH THEORY 48

 Using the generating function method, solve the recurrence relation

𝑎𝑛 − 3𝑎𝑛−1 = 𝑛, 𝑛 ≥ 1, Given 𝑎0 = 1.
The given relation may be rewritten as

𝑎𝑛+1 = 3𝑎𝑛 + 𝑛 + 1 , 𝑛 ≥ 0,

©Dr. Vishal Patil

Asst Professor-JU
with 𝑎0 = 1. For this relation, the generating function is given by

𝑎0 +𝑥𝑔(𝑥)
𝑓 𝑥 = (𝑖) Where
1−3𝑥

𝑔 𝑥 = ෍ 𝑛 + 1 𝑥𝑛
𝑛=0

Evidently, 𝑔(𝑥) is a generating function for the sequence 𝑛+1 = 1, 2, 3, … .

Accordingly, we have 𝑔 𝑥 = (1 − 𝑥)−2

Also, it is given that 𝑎0 = 1. Using these in (i), we get

24-03-2023 DISCRETE MATHEMATICS & GRAPH THEORY 49
 ©Dr. Vishal Patil
Asst Professor-JU
24-03-2023 DISCRETE MATHEMATICS & GRAPH THEORY 50