Department of Mathematics

DISCRETE STRUCTURES
I/IV-B.Tech-(I st Sem), Academic Year: 2023-2024

(CO-3)

Session-20
(SOLUTION OF RECURRENCE RELATIONS by Using GENERATING FUNCTIONS)
Instructional Objective:
1. Generating functions can be used to solve many types of counting problems, such as the
number of ways to select or distribute objects of different kinds, subject to a variety of
constraints.
Learning Outcomes: 1) Able to determine the n th term of sequence.
2) Able to determine the solution of recurrence relation by using generating function

Introduction:
Generating functions are used to represent sequences efficiently by coding the terms of a
sequence as coefficients of powers of a variable x in a formal power series. Generating functions
can be used to solve many types of counting problems, such as the number of ways to select or
distribute objects of different kinds, subject to a variety of constraints, and the number of ways to
make change for a dollar using coins of different denominations. Generating functions can be
used to solve recurrence relations by translating a recurrence relation for the terms of a sequence
into an equation involving a generating function. This equation can then be solved to find a
closed form for the generating function. From this closed form, the coefficients of the power
series for the generating function can be found, solving the original recurrence relation.
Generating functions can also be used to prove combinatorial identities by taking advantage of
relatively simple relationships between functions that can be translated into identities involving
the terms of sequences.
Explanation: Here we explain the solution of recurrence relation by using generating
function by taking an example as follows:

Example: solve the recurrence relation

a n=3 an−1 for n=1, 2, 3 4----with initial condition a 0 =2 , by using generation function.
∞
G( x )= ∑ a n xn
Sol: Let G(x) be the generating function for sequence {an}, that is n=0

is
a n=3 an−1 for n=1 ,2 , 3−−−
Given recurrence relation ------------------(1)

a n x n=3 an−1 x n
Multiplying (1) both sides with xn, we got
 ∞ ∞
∑ a n x n=3 ∑ an−1 x n−1
n=1 n=1
For n=1,2,3----, by taking summation -------------(2)
By using def of generating function G(x), (2) Can be written as
G( x )−a0 =3 xG( x ) i . e . G( x )-2=3xG( x )
∞
2
=2 ∑ 3 x
n n
⇒G (x )=
1−3 x n=0
n
⇒ an =2 .3 is solution for recurrence relation (1)

Summary:

In this session, it was discussed the solution of homogeneous and non-homogeneous recurrence
relations by using generating functions.

Self-assessment questions:
1
1. Find the coefficient of x10 in the power series of each of these function 1−2 x
a) 1024 b) -1024 c) 1034 d)-1034
Ans: a
1
2
2. Find the coefficient of x10 in the power series of each of these functions ( 1+ x )
a) -11 b)11 c)12 d)-12
Ans: b
1
, the value of a 3
3. For the generating function 1−5 x
a)25 b)625 c)125 d)5
Ans: c
x3
, the value of a 4
4. For the generating function 1+3 x
a) a)2 b)3 c)-2 d)-3

Ans: d
1
3
5. Find the coefficient of x10 in the power series of each of these function ( 1−x )
a)-66 b) 66 c)55 d)-55
Ans: b

Class Room Delivery Problems:

1) Solve the recurrence relation
a n=2 an−1 +3a n-2 for n=2, 3, 4----with initial condition a 0 =3 and a 1 =1 by using
generation function
2) Suppose that a valid code word is an n-digit number in decimal notation containing an even
number of 0s. Let an denote the number of valid code words of length n. Then, the
corresponding recurrence relation is
a n=8 an−1 +10n-1 for n=1,2, 3, 4----with initial condition a 0 =1 . Use generating
functions to find an explicit formula for an
3) Use generating functions to solve the recurrence relation
a n=7 an−1 , with a0 =5 , for n=1, 2, 3----
Tutorial Questions:

1) Use generating functions to solve the recurrence relation

a n=3 an−1 +2 , with a 0 =1 , for n=1, 2, 3----
2) Use generating functions to solve the recurrence relation
a n=3 an−1 +4 n−1 , with a 0 =1 , for n=1, 2, 3----
3) Use generating functions to solve the recurrence relation
a n=5 an−1 -6 a n-2 for n=2, 3, 4----with initial condition a 0 =6 and a 1=30
4) Use generating functions to solve the recurrence relation
a n=3 an−1 +n , with a 0=1 , for n=1, 2, 3----

Home Assignment questions:

1) Use generating functions to solve the recurrence relation

a n=an−1 +2 a n-2 +2n for n=2, 3, 4----with initial condition a 0 =4 and a 1 =12

2) Use generating functions to solve the recurrence relation

a n=2 an−1 + 3 a n-2 +4 n + 6 for n=2, 3, 4----with initial condition a 0=20 and a 1=60

Use generating functions to solve the recurrence relation

3)
a n=an−1 +3 n-1 for n=1 , 2, 3, 4----with initial condition a 0 =1

4) Use generating functions to solve the recurrence relation

a n=3 an−1 -1 for n=1 ,, 2, 3, 4----with initial condition a 0 =2

5) Use generating functions to solve the recurrence relation

a n=an−1 -2a n-3 for n=3, 4----with initial condition a 0 =1,a1 =0,a 2 =1

Links:
https://www.youtube.com/watch?v=Xf-mnh65CaU
https://www.google.com/search?q=solu+of+recurrence+relation+by+
+using+generating+function+discrete+mathematics&client=firefox-b-
d&sxsrf=AB5stBikDYEeQLFiJbagqGu05wEvNXAG-g
%3A1689518831064&ei=7wK0ZMrMA-
nvseMPqqi1wA4&ved=0ahUKEwiKgJGOvJOAAxXpd2wGHSpUDegQ4dUDCBA&uact=
5&oq=solu+of+recurrence+relation+by+
+using+generating+function+discrete+mathematics&gs_lp=Egxnd3Mtd2l6LXNlcnAiTnNv
bHUgb2YgcmVjdXJyZW5jZSByZWxhdGlvbiBieSAgdXNpbmcgZ2VuZXJhdGluZyBmd
W5jdGlvbiBkaXNjcmV0ZSBtYXRoZW1hdGljczIHECMYsAIYJ0i6JlC0B1iHInABeAGQ
AQCYAZoCoAGQCKoBAzItNLgBA8gBAPgBAcICChAAGEcY1gQYsAPiAwQYACBBi
AYBkAYI&sclient=gws-wiz-serp#fpstate=ive&vld=cid:ceeb74ef,vid:LNOZlxyrkPA

https://www.youtube.com/watch?v=p99AC4FtloM