MA1002 – Computational Mathematics

Module – 6: Recurrence Relation and

Generating Function
 MA1002 – COMPUTATIONAL MATHEMATICS

Module 6: Recurrence Relation and Generating Function

Module 6
Recurrence Relation & Generating function: Recursive definition of
functions, Recursive algorithms, Recurrence relation, generating functions,
Method of solving recurrences (using generating functions).
 MA1002 - COMPUTATIONAL MATHEMATICS

Module 6: Recurrence Relation and Generating Function

Recursive Function
The meaning of the word recursive is “relating to or involving the repeated
application of a rule, definition, or procedure to successive results”.
Recursive Function is a function that repeats or uses its own previous term to
calculate subsequent terms and thus forms a sequence of terms.
Or in other words, recursive function is a function which calls itself from its
previous value to generate subsequent value.
For any recursively defined function, it has two parts. The first part is the
definition of the smallest argument, and the second part is the definition of the
𝑛𝑡ℎ term. The smallest argument is usually denoted by 𝑓(0) or 𝑓(1) and the
𝑛𝑡ℎ argument is denoted by 𝑓(𝑛).
 MA1002 - COMPUTATIONAL MATHEMATICS

Module 6: Recurrence Relation and Generating Function

Let us understand the recursively defined function with the help of an example.
Ex. Let us consider the sequence of numbers as 5, 7, 9, 11.
The explicit formula for the given sequence is 𝑓(𝑛) = 2𝑛 + 5.
The recursive formula for the given sequence is given by
𝑓(0) = 5 𝑎𝑛𝑑 𝑓(𝑛) = 𝑓(𝑛 − 1) + 2
Now, we can check the sequence terms using the recursive formula as follows:
𝑓(0) = 5
𝑓(1) = 𝑓(0) + 2 = 5 + 2 = 7
𝑓(2) = 𝑓(1) + 2 = 7 + 2 = 9
𝑓(3) = 𝑓(2) + 2 = 9 + 2 = 11
In this way, we can find the next term in the sequence with the help of the
recursive function formula.
 MA1002 - COMPUTATIONAL MATHEMATICS

Module 6: Recurrence Relation and Generating Function

If 𝑎0 , 𝑎1 , … , 𝑎𝑛−1 , 𝑎𝑛 , … is the sequence of values, then a recursive formula for
this sequence will require to compute all the previous terms and find the value of
𝑎𝑛 .
Different kind of recurrence formulas may be like
𝑎𝑛 = 𝑎𝑛−1 + 𝑎0
𝑎𝑛 = 3𝑎𝑛−1 + 2𝑎𝑛−2
𝑎𝑛+1 − 𝑎𝑛 𝑎𝑛−1 + 𝑎𝑛−2 = 0
A recursive function 𝑓(𝑛) is the same as a sequence 𝑎𝑛 , where 𝑓 𝑖 = 𝑎𝑖 ; 𝑖 =
0,1,2, …
Ex.1 𝑓 𝑛 𝑜𝑟 𝑎𝑛 = 3𝑛2 + 𝑛 + 8
3𝑛 ; 0 ≤ 𝑛 ≤ 1
Ex. 2 𝑓 𝑛 𝑜𝑟 𝑎𝑛 = ቊ 𝑛
5 ; 𝑛>1
 MA1002 - COMPUTATIONAL MATHEMATICS

Module 6: Recurrence Relation and Generating Function

Recurrence Relation (RR)
A formula which defines any term of a sequence in terms of any number of its
previous terms (or which express any term of a sequence as a function of its
previous terms), is called Recursive and the relation is called Recurrence
Relation.
The nth term of the sequence 3,8,13,18,23,… can be written as-
𝑎𝑛 = 𝑎𝑛−1 + 5 ; 𝑛 ≥ 1 𝑎𝑛𝑑 𝑎0 = 3
This relation is called Recurrence Relation and the condition 𝑎0 = 3 is called
initial condition/boundary condition for the sequence.
A function whose domain is the set of nonnegative integers and whose range is
the set of real numbers is called Discrete Numeric Function (DNF) or Numeric
Function (NF).
The NF often termed as Sequence.
 MA1002 - COMPUTATIONAL MATHEMATICS

Module 6: Recurrence Relation and Generating Function

Order of a Recurrence Relation
The difference between highest and lowest subscript in the RR is the order of
that RR.
Ex.1 For the RR 𝑎𝑛+2 − 3𝑎𝑛+1 − 𝑎𝑛 = 0, the order is
= 𝑛+2 −𝑛 =2
Ex.2 For the RR 𝑎𝑛+1 − 3𝑎𝑛2 − 2𝑎𝑛−2 = 0, the order is
= 𝑛 + 1 − (𝑛 − 2) = 3
Degree of a RR
The highest power of 𝑎 with any argument is the degree of the RR.
Ex.1 For the RR 𝑎𝑛+2 − 3𝑎𝑛+1 − 𝑎𝑛 = 0, the degree is 1.
Ex.2 For the RR 𝑎𝑛+1 − 3𝑎𝑛2 − 2𝑎𝑛−2 = 0, the degree is 2.
2
Ex.3 For the RR 𝑎𝑛+1 − 3𝑎𝑛3 − 2𝑎𝑛−2 = 0, the degree is 3.
 MA1002 - COMPUTATIONAL MATHEMATICS

Module 6: Recurrence Relation and Generating Function

A RR is called Linear if it is in first degree.
A RR is called Homogeneous if it contains no terms that depend only on the
argument (n in this case).
A RR which is not homogeneous, is called Non – Homogeneous.
Ex.1 The RR 𝑎𝑛+2 − 3𝑎𝑛+1 − 𝑎𝑛 = 2𝑛 , is Non- Homogeneous and Linear.
Ex.2 The RR 𝑎𝑛+1 − 3𝑎𝑛 − 2𝑎𝑛−2 = 0, is Linear and Homogeneous.
2
Ex.3 The RR 𝑎𝑛+1 − 3𝑎𝑛3 − 2𝑎𝑛−2 = 0, is Nonlinear and Homogeneous.
Ex.4 The RR 𝑎𝑛 𝑎𝑛+1 − 3𝑎𝑛 − 2𝑎𝑛−2 = 0, is Nonlinear and Homogeneous
 MA1002 - COMPUTATIONAL MATHEMATICS

Module 6: Recurrence Relation and Generating Function

Modelling of a RR
Ex. A ball is dropped on a floor from a height of 40 meters. It is assumed that the
ball always rebounds and reaches half of the height from which it falls. If 𝑎𝑛
denotes the height it reaches in the nth rebound, then build the recursive
function (or recurrence relation) and find 𝑎𝑛 , If 𝑏𝑛 is the loss in height during the
nth rebound, then find 𝑏𝑛 and write it in terms of 𝑎𝑛 .
Sol.
40 1 40 40 1 40 40 40
∵ 𝑎1 = , 𝑎2 = . = 2 , 𝑎3 = . 2 = 3 , … , 𝑎𝑛 = 𝑛
2 2 2 2 2 2 2 2
40 40 40
∵ 𝑏1 = 40 − , 𝑏2 = 40 − 2 , 𝑏3 = 40 − 3 , …
2 2 2
40
∴ 𝑏𝑛 = 40 − 𝑛 = 40 − 𝑎𝑛
2
 MA1002 - COMPUTATIONAL MATHEMATICS

Module 6: Recurrence Relation and Generating Function

Ex. At a tea party of ‘𝑛’ gentlemen 𝑛 ≥ 2 , every gentleman shakes hand exactly
once with all the remaining (𝑛 − 1) gentlemen. Build a recurrence relation for
the total number of handshakes.
Sol. Let 𝑎𝑛 denote the total number of handshakes among ‘𝑛’ gentlemen. As the
handshake is not possible with one person, so, obviously 𝑎1 = 0.
Between two persons, the handshake can be done only once, so, 𝑎2 = 1.
Since, out of ‘𝑛’ gentlemen every gentleman shakes hand exactly once with the
remaining (𝑛 − 1) gentlemen, if this gentleman is left out, then there remain
(𝑛 − 1) gentlemen and so 𝑎𝑛−1 will be the total number of handshakes among
these gentlemen. Thus, we have
𝑎𝑛 = 𝑛 − 1 + 𝑎𝑛−1 ; 𝑎1 = 0, 𝑎2 = 1, 𝑛 ≥ 2
 MA1002 - COMPUTATIONAL MATHEMATICS

Module 6: Recurrence Relation and Generating Function

Generating Function (GF)
If 𝑎1 , 𝑎2 , … , 𝑎𝑛 , … is a sequence of real or complex numbers, then the power
series given by
∞

𝐺 𝑥 = ෍ 𝑎𝑛 𝑥 𝑛 = 𝑎0 + 𝑎1 𝑥 + 𝑎2 𝑥 2 + 𝑎3 𝑥 3 + ⋯ (1)
𝑛=0
is called the Generating Function (GF) for the given sequence 𝑎𝑛 ∞ 𝑛=0 , where
𝑎𝑛 =coefficient of 𝑥 𝑛 in 𝐺 𝑥 in series (1).
The word GF is used, because, in some sense 𝐺 𝑥 generates its coefficients. In
(1), 𝑥 is considered just a symbol, called an indeterminate, it is not a variable
which is replaced by numbers belonging to some domain.
 MA1002 - COMPUTATIONAL MATHEMATICS

Module 6: Recurrence Relation and Generating Function

Q1. Find the GF for the sequence 1,1,1,1,1,…
Sol. Here 𝑎0 = 𝑎1 = 𝑎2 = ⋯ . . = 1
1
∴𝐺 𝑥 =1+𝑥 + 𝑥2 + 𝑥3 +⋯= 1−𝑥 −1 = ; 𝑥 <1
1−𝑥
Q2. Find the GF for the sequence 𝑎, 𝑎, 𝑎, 𝑎, 𝑎, …
Sol. Here 𝑎0 = 𝑎1 = 𝑎2 = ⋯ . . = 𝑎
∴ 𝐺 𝑥 = 𝑎 + 𝑎𝑥 + 𝑎𝑥 2 + 𝑎𝑥 3 + ⋯
2 3 −1
𝑎
=𝑎 1+𝑥+𝑥 +𝑥 +⋯ =𝑎 1−𝑥 = ; 𝑥 <1
1−𝑥
 MA1002 - COMPUTATIONAL MATHEMATICS

Module 6: Recurrence Relation and Generating Function

[Link] the GF for the sequence 1,2,3,4,5,…
Sol. Here 𝑎0 = 1, 𝑎1 = 2, 𝑎2 = 3, …
1
∴ 𝐺 𝑥 = 1 + 2𝑥 + 3𝑥 2 + 4𝑥 3 +⋯= 1−𝑥 −2 = 2
1−𝑥
Q4. Find the GF for the sequence 0,1,2,3,4,…
Sol. Here 𝑎0 = 0, 𝑎1 = 1, 𝑎2 = 2, … . .
∴ 𝐺 𝑥 = 0 + 𝑥 + 2𝑥 2 + 3𝑥 3 + ⋯ = 𝑥(1 + 2𝑥 + 3𝑥 2 + 4𝑥 3 + ⋯ )

−2
𝑥
=𝑥 1−𝑥 = 2
1−𝑥
 MA1002 - COMPUTATIONAL MATHEMATICS

Module 6: Recurrence Relation and Generating Function

Q5. Find the GF for the sequence 1, 𝑎, 𝑎2 , 𝑎3 , …
Sol. Here 𝑎0 = 1, 𝑎1 = 𝑎, 𝑎2 = 𝑎2 …
∴ 𝐺 𝑥 = 1 + 𝑎𝑥 + 𝑎2 𝑥 2 + 𝑎3 𝑥 3 + ⋯
−1
1
= 1 − 𝑎𝑥 = ; 𝑎𝑥 < 1
1 − 𝑎𝑥
Alternative Way
𝐺 𝑥 = 1 + 𝑎𝑥 + 𝑎2 𝑥 2 + 𝑎3 𝑥 3 + ⋯
⇒ 𝐺 𝑥 − 1 = 𝑎𝑥 + 𝑎2 𝑥 2 + 𝑎3 𝑥 3 + ⋯
𝐺 𝑥 −1
= 1 + 𝑎𝑥 + 𝑎2 𝑥 2 + 𝑎3 𝑥 3 + ⋯
𝑎𝑥
𝐺 𝑥 −1
=𝐺 𝑥
𝑎𝑥
1
⇒𝐺 𝑥 =
1 − 𝑎𝑥
 MA1002 - COMPUTATIONAL MATHEMATICS

Module 6: Recurrence Relation and Generating Function

General term of Numeric Function ‘𝒂’ Generating Function 𝐺 𝑥
𝑎𝑛 = 1 1
𝐺 𝑥 =
1−𝑥
𝑎𝑛 = 𝑛 𝑥
𝐺 𝑥 =
1−𝑥 2
𝑎𝑛 = 𝑛 + 1 1
𝐺 𝑥 =
1−𝑥 2
𝑎𝑛 = 𝑛 𝑛 + 1 2𝑥
𝐺 𝑥 =
1−𝑥 2
𝑎𝑛 = 𝑛 + 1 𝑛 + 2 2
𝐺 𝑥 =
1−𝑥 3
 MA1002 - COMPUTATIONAL MATHEMATICS

Module 6: Recurrence Relation and Generating Function

General term of Numeric Function ‘𝒂’ Generating Function 𝐺 𝑥

𝑎𝑛 = 𝑛𝑎𝑛 𝑎𝑥
𝐺 𝑥 =
1 − 𝑎𝑥 2
1 𝐺 𝑥 = 𝑒𝑥
𝑎𝑛 =
𝑛!
𝑎𝑛 = 𝐶(𝑚, 𝑛) 𝐺 𝑥 = 1+𝑥 𝑚
𝑎𝑛 = 𝑎 𝑛 1
𝐺 𝑥 =
1 − 𝑎𝑥
𝑎𝑛 = (−1)𝑛 1
𝐺 𝑥 =
1+𝑥
𝑎𝑛 = 𝑛 2 𝑥(𝑥 + 1)
𝐺 𝑥 =
1−𝑥 3
 MA1002 - COMPUTATIONAL MATHEMATICS

Module 6: Recurrence Relation and Generating Function

Th.1 Let 𝑎,𝑏 and 𝑐 be NFs and their GFs are 𝐺1 𝑥 , 𝐺2 𝑥 and 𝐺3 𝑥 respectively,
then
(i) If 𝑏𝑛 = 𝛼𝑎𝑛 for some constant 𝛼, then 𝐺2 𝑥 = 𝛼𝐺1 𝑥 .
(ii) If 𝑐𝑛 = 𝑎𝑛 + 𝑏𝑛 , then 𝐺3 𝑥 = 𝐺1 𝑥 + 𝐺2 𝑥
(iii) If 𝑐𝑛 = 𝑎𝑛 ∗ 𝑏𝑛 , then 𝐺3 𝑥 = 𝐺1 𝑥 𝐺2 𝑥
(iv) If 𝑏𝑛 = 𝛼 𝑛 𝑎𝑛 for some constant 𝛼, then 𝐺2 𝑥 = 𝐺1 𝛼𝑥
1
Th. 2 Let 𝐺(𝑥) be the GF of the NF 𝑎 = (𝑎0 , 𝑎1 , 𝑎2 , … , 𝑎𝑛 , … ) then 𝐺(𝑥) is
1−𝑥
the GF for the NF 𝑏, which is accumulated sum of 𝑎 i.e.
𝑛

𝑏𝑛 = ෍ 𝑎𝑖 = 𝑎0 + 𝑎1 + 𝑎2 + 𝑎3 + ⋯ + 𝑎𝑛 ; n ≥ 0
𝑖=0
 MA1002 - COMPUTATIONAL MATHEMATICS

Module 6: Recurrence Relation and Generating Function

∞

∵ 𝐺 𝑥 = ෍ 𝑎𝑛 𝑥𝑛 = 𝑎0 + 𝑎1 𝑥 + 𝑎2 𝑥 2 + 𝑎3 𝑥 3 + ⋯ + 𝑎𝑛 𝑥 𝑛 + ⋯ (1)
𝑛=0
1
Also = 1 + 𝑥 + 𝑥2 + 𝑥3 + ⋯ + 𝑥𝑛 + ⋯ (2)
1−𝑥
(1)*(2), we have
𝐺(𝑥)
= 1 + 𝑥 + 𝑥2 + 𝑥3 + ⋯ + 𝑥𝑛 + ⋯
1−𝑥
∗ (𝑎0 + 𝑎1 𝑥 + 𝑎2 𝑥 2 + 𝑎3 𝑥 3 + ⋯ + 𝑎𝑛 𝑥 𝑛 + ⋯ )
= 𝑎0 + (𝑎0 + 𝑎1 )𝑥 + (𝑎0 + 𝑎1 + 𝑎2 )𝑥 2 + (𝑎0 + 𝑎1 + 𝑎2 +𝑎3 )𝑥 3 + ⋯
+ (𝑎0 + 𝑎1 + 𝑎2 + ⋯ + 𝑎𝑛 )𝑥 𝑛 + ⋯
= 𝑏0 + 𝑏1 𝑥 + 𝑏2 𝑥 2 + 𝑏3 𝑥 3 + ⋯ + 𝑏𝑛 𝑥 𝑛 + ⋯
Where 𝑏𝑛 = 𝑎0 + 𝑎1 + 𝑎2 + ⋯ + 𝑎𝑛
 MA1002 - COMPUTATIONAL MATHEMATICS

Module 6: Recurrence Relation and Generating Function

Q1. Find GF for the series 1,-1,1,-1,1,-1,….
Sol. Here 𝑎0 = 1, 𝑎1 = −1, 𝑎2 = 1, …
1
∴𝐺 𝑥 =1−𝑥+ 𝑥2 − 𝑥3 +⋯= 1+𝑥 −1 =
1+𝑥
Q2. Find GF for the series 1,1,1,1,1,1,1
Sol. Here 𝑎0 = 1, 𝑎1 = 1, 𝑎2 = 1, … , 𝑎6 = 1
∴ 𝐺 𝑥 = 1 + 𝑥 + 𝑥2 + 𝑥3 + ⋯ + 𝑥6 …(1)
∴ 𝑥𝐺 𝑥 = 𝑥 + 𝑥 2 + 𝑥 3 + ⋯ + 𝑥 7 …(2)
(1)-(2), we get 1 − 𝑥 𝐺 𝑥 = 1 − 𝑥 7
1 − 𝑥7
∴𝐺 𝑥 =
1−𝑥
 MA1002 - COMPUTATIONAL MATHEMATICS

Module 6: Recurrence Relation and Generating Function

Q3. Find GF for the series 2,3,5,9,17,33,…
Sol. Here 𝑎0 = 2, 𝑎1 = 3, 𝑎2 = 5, …
∴ 𝐺 𝑥 = 2 + 3𝑥 + 5𝑥 2 + 9𝑥 3 + 17𝑥 4 + 33𝑥 5 + ⋯
= 1 + 𝑥 + 𝑥 2 + 𝑥 3 + ⋯ + 1 + 2𝑥 + 22 𝑥 2 + 23 𝑥 3 + ⋯
1 1 2 − 3𝑥
= + =
1 − 𝑥 1 − 2𝑥 1 − 3𝑥 + 2𝑥 2
Q4. Find GF for the series 2,5,13,35,…
Sol. Here 𝑎0 = 2, 𝑎1 = 5, 𝑎2 = 13, …
∴ 𝐺 𝑥 = 2 + 5𝑥 + 13𝑥 2 + 35𝑥 3 + ⋯
= 1 + 3𝑥 + 32 𝑥 2 + 33 𝑥 3 + ⋯ + 1 + 2𝑥 + 22 𝑥 2 + 23 𝑥 3 + ⋯
1 1 2 − 5𝑥
= + =
1 − 3𝑥 1 − 2𝑥 1 − 5𝑥 + 6𝑥 2
 MA1002 - COMPUTATIONAL MATHEMATICS

Module 6: Recurrence Relation and Generating Function

2𝑛 𝑖𝑓 𝑛 𝑖𝑠 𝑒𝑣𝑒𝑛
Q5. Find GF of a NF 𝑎, where 𝑎𝑛 = ቐ−2𝑛 𝑖𝑓 𝑛 𝑖𝑠 𝑜𝑑𝑑
1 ; 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
1
Sol. Here 𝐺 𝑥 = 1 − 2𝑥 + 22 𝑥 2 − 23 𝑥 3 + 24 𝑥 4 − 25 𝑥 5 +⋯=
1+2𝑥
Q6. Find the GF for the NF 𝑎, such that 𝑎𝑛 = 2𝑛 + 3𝑛
Sol.
∞ ∞ ∞ ∞

∵ 𝐺 𝑥 = ෍ 𝑎𝑛 𝑥 𝑛 = ෍ 2𝑛 + 3𝑛 𝑥 𝑛 = ෍ 2𝑛 𝑥 𝑛 + ෍ 3𝑛 𝑥 𝑛
𝑛=0 𝑛=0 𝑛=0 𝑛=0

1 1 2 − 5𝑥
= + =
1 − 2𝑥 1 − 3𝑥 1 − 5𝑥 + 6𝑥 2
 MA1002 - COMPUTATIONAL MATHEMATICS

Module 6: Recurrence Relation and Generating Function

Q7. Find the GF of the sequence 𝑦1 , 𝑦2 , 𝑦3 , … , 𝑦𝑛 , … defined as
𝑦𝑛 + 2𝑦𝑛−1 − 15𝑦𝑛−2 = 0 ; 𝑛 ≥ 2
With boundary conditions 𝑦0 = 0, 𝑦1 = 1.
Sol. As for the given sequence GF is
∞

𝐺 𝑥 = 𝑦0 + 𝑦1 𝑥 + 𝑦2 𝑥 2 + ⋯ = ෍ 𝑦𝑛 𝑥 𝑛 … (1)
𝑛=0
Also 𝑦𝑛 + 2𝑦𝑛−1 − 15𝑦𝑛−2 = 0 …(2)
Multiply with 𝑥 𝑛 and taking summation from 𝑛 = 2 to 𝑛 = ∞, we have
∞ ∞ ∞

෍ 𝑦𝑛 𝑥 𝑛 + 2 ෍ 𝑦𝑛−1 𝑥 𝑛 − 15 ෍ 𝑦𝑛−2 𝑥 𝑛 = 0
𝑛=2 𝑛=2 𝑛=2
 MA1002 - COMPUTATIONAL MATHEMATICS

Module 6: Recurrence Relation and Generating Function

∞ ∞ ∞

⇒ ෍ 𝑦𝑛 𝑥 𝑛 − 𝑦0 − 𝑦1 𝑥 + 2𝑥 ෍ 𝑦𝑛−1 𝑥 𝑛−1 − 2𝑥𝑦0 − 15 𝑥 2 ෍ 𝑦𝑛−2 𝑥 𝑛−2 = 0

𝑛=0 𝑛=1 𝑛=2

⇒ 𝐺 𝑥 − 𝑦0 − 𝑦1 𝑥 + 2𝑥 𝐺 𝑥 − 𝑦0 − 15𝑥 2 𝐺(𝑥) = 0

⇒ 𝐺 𝑥 1 + 2𝑥 − 15𝑥 2 − 𝑥 = 0

𝑥 𝑥
⇒𝐺 𝑥 = 2
=
1 + 2𝑥 − 15𝑥 (1 + 5𝑥)(1 − 3𝑥)
 MA1002 - COMPUTATIONAL MATHEMATICS

Module 6: Recurrence Relation and Generating Function

Solution of RR using Generating Function
Let us consider the RR
𝑐0 𝑎𝑛 + 𝑐1 𝑎𝑛−1 + 𝑐2 𝑎𝑛−2 + ⋯ + 𝑐𝑘 𝑎𝑛−𝑘 = 𝑓 𝑛 … (1)
Where 𝑐0 , 𝑐1 , 𝑐2 , … , 𝑐𝑘 are constants and the relation is valid for 𝑛 ≥ 𝑘.
Multiply (1) with 𝑥 𝑛 on both sides and taking summation from 𝑛 = 𝑘 to 𝑛 = ∞,
we get
∞ ∞

෍ 𝑥 𝑛 𝑐0 𝑎𝑛 + 𝑐1 𝑎𝑛−1 + 𝑐2 𝑎𝑛−2 + ⋯ + 𝑐𝑘 𝑎𝑛−𝑘 = ෍ 𝑥 𝑛 𝑓 𝑛 … (2)

𝑛=𝑘 ∞ 𝑛=𝑘

∵ 𝐺 𝑥 = ෍ 𝑎𝑛 𝑥 𝑛 = 𝑎0 + 𝑎1 𝑥 + 𝑎2 𝑥 2 + ⋯ + 𝑎𝑘−1 𝑥 𝑘−1 + 𝑎𝑘 𝑥 𝑘 + ⋯
𝑛=0
 MA1002 - COMPUTATIONAL MATHEMATICS

Module 6: Recurrence Relation and Generating Function

∞ ∞

∴ ෍ 𝑎𝑛 𝑥 𝑛 = ෍ 𝑎𝑛 𝑥 𝑛 − 𝑎0 − 𝑎1 𝑥 − 𝑎2 𝑥 2 − ⋯ − 𝑎𝑘−1 𝑥 𝑘−1
𝑛=𝑘 𝑛=0

∞ ∞

∴ 𝑐0 ෍ 𝑎𝑛 𝑥 𝑛 = 𝑐0 ෍ 𝑎𝑛 𝑥 𝑛 − 𝑎0 − 𝑎1 𝑥 − 𝑎2 𝑥 2 − ⋯ − 𝑎𝑘−1 𝑥 𝑘−1
𝑛=𝑘 𝑛=0

∞ ∞

∵ ෍ 𝑎𝑛−1 𝑥 𝑛−1 = ෍ 𝑎𝑛 𝑥 𝑛 − 𝑎0 − 𝑎1 𝑥 − 𝑎2 𝑥 2 − ⋯ − 𝑎𝑘−2 𝑥 𝑘−2

𝑛=𝑘 𝑛=0

∞ ∞

∴ 𝑐1 ෍ 𝑎𝑛−1 𝑥 𝑛 = 𝑐1 𝑥 ෍ 𝑎𝑛 𝑥 𝑛 − 𝑎0 − 𝑎1 𝑥 − 𝑎2 𝑥 2 − ⋯ − 𝑎𝑘−2 𝑥 𝑘−2

𝑛=𝑘 𝑛=0
 MA1002 - COMPUTATIONAL MATHEMATICS

Module 6: Recurrence Relation and Generating Function

∞ ∞

𝑐2 ෍ 𝑎𝑛−1 𝑥 𝑛 = 𝑐2 𝑥 2 ෍ 𝑎𝑛 𝑥 𝑛 − 𝑎0 − 𝑎1 𝑥 − 𝑎2 𝑥 2 − ⋯ − 𝑎𝑘−3 𝑥 𝑘−3

𝑛=𝑘 𝑛=0
:
∞ ∞

𝑐𝑘 ෍ 𝑎𝑛−𝑘 𝑥 𝑛 = 𝑐𝑘 𝑥 𝑘 ෍ 𝑎𝑛−𝑘 𝑥 𝑛−𝑘

𝑛=𝑘 𝑛=𝑘
Putting these values in (2) and write 𝐺 𝑥 = σ∞ 𝑎
𝑛=0 𝑛 𝑥 𝑛 , we have

𝑐0 𝐺(𝑥) − 𝑎0 − 𝑎1 𝑥 − 𝑎2 𝑥 2 − ⋯ − 𝑎𝑘−1 𝑥 𝑘−1

+ 𝑐1 𝑥 𝐺(𝑥) − 𝑎0 − 𝑎1 𝑥 − 𝑎2 𝑥 2 − ⋯ − 𝑎𝑘−2 𝑥 𝑘−2
+ 𝑐2 𝑥 2 𝐺(𝑥) − 𝑎0 − 𝑎1 𝑥 − 𝑎2 𝑥 2 − ⋯ − 𝑎𝑘−3 𝑥 𝑘−3 + ⋯ + 𝑐𝑘 𝑥 𝑘 𝐺 𝑥
∞

= ෍ 𝑥𝑛𝑓 𝑛
𝑛=𝑘
 MA1002 - COMPUTATIONAL MATHEMATICS

Module 6: Recurrence Relation and Generating Function

∞
𝐺 𝑥 𝑐0 + 𝑐1 𝑥 + 𝑐2 𝑥 2 + ⋯ + 𝑐𝑘−1 𝑥 𝑘−1 + 𝑐𝑘 𝑥 𝑘
= ෍ 𝑥 𝑛 𝑓 𝑛 + 𝑐0 𝑎0 + 𝑎1 𝑥 + 𝑎2 𝑥 2 + ⋯ + 𝑎𝑘−1 𝑥 𝑘−1
𝑛=𝑘
+ 𝑐1 𝑥 𝑎0 + 𝑎1 𝑥 + 𝑎2 𝑥 2 + ⋯ + 𝑎𝑘−2 𝑥 𝑘−2 + 𝑐2 𝑥 2 𝑎0 + 𝑎1 𝑥 + 𝑎2 𝑥 2 + ⋯ + 𝑎𝑘−3 𝑥 𝑘−3
+ 𝑐𝑘−1 𝑥 𝑘−1 𝑎0
𝐺 𝑥
∞
1 𝑛𝑓 𝑛
= ቎ ෍ 𝑥
𝑐0 + 𝑐1 𝑥 + 𝑐2 𝑥 2 + ⋯ + 𝑐𝑘−1 𝑥 𝑘−1 + 𝑐𝑘 𝑥 𝑘
𝑛=𝑘
+ 𝑐0 𝑎0 + 𝑎1 𝑥 + 𝑎2 𝑥 2 + ⋯ + 𝑎𝑘−1 𝑥 𝑘−1 + 𝑐1 𝑥 𝑎0 + 𝑎1 𝑥 + 𝑎2 𝑥 2 + ⋯ + 𝑎𝑘−2 𝑥 𝑘−2

+ 𝑐2 𝑥 2 𝑎0 + 𝑎1 𝑥 + 𝑎2 𝑥 2 + ⋯ + 𝑎𝑘−3 𝑥 𝑘−3 + 𝑐𝑘−1 𝑥 𝑘−1 𝑎0 ቏ … (3)

We get 𝑎𝑛 from (3), which is the solution of given RR.

 MA1002 - COMPUTATIONAL MATHEMATICS

Module 6: Recurrence Relation and Generating Function

Ex. 1 Solve the RR 𝑎𝑛 − 7𝑎𝑛−1 + 10𝑎𝑛−2 = 0 ; 𝑛 ≥ 2, given that 𝑎0 = 10, 𝑎1 = 41
Sol. ∵ 𝑎𝑛 − 7𝑎𝑛−1 + 10𝑎𝑛−2 = 0 …(1)
Multiplying with 𝑥 𝑛 and taking summation from 𝑛 = 2 𝑡𝑜 ∞, we get
∞ ∞ ∞

෍ 𝑎𝑛 𝑥 𝑛 − 7 ෍ 𝑎𝑛−1 𝑥 𝑛 + 10 ෍ 𝑎𝑛−2 𝑥 𝑛 = 0
𝑛=2 𝑛=2 𝑛=2

∴ 𝐺 𝑥 − 𝑎0 − 𝑎1 𝑥 − 7𝑥 𝐺 𝑥 − 𝑎0 + 10𝑥 2 𝐺(𝑥) = 0
∴ 𝐺 𝑥 − 10 − 41𝑥 − 7𝑥 𝐺 𝑥 − 10 + 10𝑥 2 𝐺(𝑥) = 0
∴ 𝐺 𝑥 1 − 7𝑥 + 10𝑥 2 + 10 7𝑥 − 1 − 41𝑥 = 0
10 − 29𝑥 3 7
∴𝐺 𝑥 = 2
= +
1 − 7𝑥 + 10𝑥 1 − 2𝑥 1 − 5𝑥
MA1002 - COMPUTATIONAL MATHEMATICS

Module 6: Recurrence Relation and Generating Function

∞ ∞ ∞

෍ 𝑎𝑛 𝑥 𝑛 = 3 ෍ 2𝑛 𝑥 𝑛 + 7 ෍ 5𝑛 𝑥 𝑛
𝑛=0 𝑛=0 𝑛=0

∴ 𝑎𝑛 = 3. 2𝑛 + 7. 5𝑛
 MA1002 - COMPUTATIONAL MATHEMATICS

Module 6: Recurrence Relation and Generating Function

Ex. 2 Solve the RR 𝑎𝑛+2 − 2𝑎𝑛+1 + 𝑎𝑛 = 2𝑛 ; given that 𝑎0 = 2, 𝑎1 = 1
Sol. ∵ 𝑎𝑛+2 − 2𝑎𝑛+1 + 𝑎𝑛 = 2𝑛 …(1)
Multiplying with 𝑥 𝑛 and taking summation from 𝑛 = 0 𝑡𝑜 ∞, we get
∞ ∞ ∞ ∞

෍ 𝑎𝑛+2 𝑥 𝑛 − 2 ෍ 𝑎𝑛+1 𝑥 𝑛 + 10 ෍ 𝑎𝑛 𝑥 𝑛 = ෍ 2𝑛 𝑥 𝑛
𝑛=0 𝑛=0 𝑛=0 𝑛=0

𝐺 𝑥 − 𝑎0 − 𝑎1 𝑥 𝐺 𝑥 − 𝑎0 1
∴ 2
−2 + 𝐺(𝑥) =
𝑥 𝑥 1 −2 2𝑥
2
𝑥
∴ 𝐺 𝑥 − 2 − 𝑥 − 2𝑥 𝐺 𝑥 − 2 + 𝑥 𝐺(𝑥) =
2
1 − 2𝑥
2
𝑥
∴ 𝐺 𝑥 1 − 2𝑥 + 𝑥 + 3𝑥 − 2 =
1 − 2𝑥
MA1002 - COMPUTATIONAL MATHEMATICS

Module 6: Recurrence Relation and Generating Function

2 − 3𝑥 𝑥2
∴𝐺 𝑥 = 2
+
1−𝑥 1 − 𝑥 2 1 − 2𝑥
3 1 1 1
= − 2
+ − 2
1−𝑥 1−𝑥 1 − 2𝑥 1−𝑥
3 1 2
= + −
1−𝑥 1 − 2𝑥 1−𝑥 2
∞ ∞ ∞ ∞

∴ ෍ 𝑎𝑛 𝑥 𝑛 = 3 ෍ 1𝑛 𝑥 𝑛 + ෍ 2𝑛 𝑥 𝑛 − 2 ෍ 𝑛 + 1 𝑥 𝑛
𝑛=0 𝑛=0 𝑛=0 𝑛=0
∴ 𝑎𝑛 = 3. 1𝑛 + 2𝑛 − 2 𝑛 + 1 = 3 + 2𝑛 − 2𝑛 −2
∴ 𝑎𝑛 = 1 − 2𝑛 + 2𝑛
 MA1002 - COMPUTATIONAL MATHEMATICS

Module 6: Recurrence Relation and Generating Function

Ex. 3 Solve the RR 𝑎𝑛 − 5𝑎𝑛−1 + 6𝑎𝑛−2 = 2𝑛 + 𝑛 ; 𝑛 ≥ 2, given that 𝑎0 = 𝑎1 = 1.
Sol. ∵ 𝑎𝑛 − 5𝑎𝑛−1 + 6𝑎𝑛−2 = 2𝑛 + 𝑛 …(1)
Multiplying with 𝑥 𝑛 and taking summation from 𝑛 = 2 𝑡𝑜 ∞, we get
∞ ∞ ∞ ∞

෍ 𝑎𝑛 𝑥 𝑛 − 5 ෍ 𝑎𝑛−1 𝑥 𝑛 + 6 ෍ 𝑎𝑛−2 𝑥 𝑛 = ෍ (2𝑛 + 𝑛)𝑥 𝑛

𝑛=2 𝑛=2 𝑛=2 𝑛=2

∞ ∞

∴ 𝐺 𝑥 − 𝑎0 − 𝑎1 𝑥 − 5𝑥 𝐺 𝑥 − 𝑎0 + 6𝑥 2 𝐺 𝑥 = ෍ 2𝑛 𝑥 𝑛 + ෍ 𝑛𝑥 𝑛
𝑛=2 𝑛=2
…(2)
∞ ∞
1
∵෍ 2𝑛 𝑥 𝑛 = 22 𝑥 2 ෍ 2𝑛−2 𝑥 𝑛−2 = 4𝑥 2
1 − 2𝑥
𝑛=2 𝑛=2
 MA1002 - COMPUTATIONAL MATHEMATICS

Module 6: Recurrence Relation and Generating Function

∞

∵ ෍ 𝑛𝑥 𝑛 = 2𝑥 2 + 3𝑥 3 + 4𝑥 4 + ⋯ = 𝑥 + 2𝑥 2 + 3𝑥 3 + 4𝑥 4 + ⋯ − 𝑥
𝑛=2
𝑥
= 𝑥 1 + 2𝑥 + 3𝑥 2 + 4𝑥 3 +⋯ −𝑥 = 2
−𝑥
1−𝑥
From (2), we have
4𝑥 2 𝑥
2
𝐺 𝑥 − 1 − 𝑥 − 5𝑥 𝐺 𝑥 − 1 + 6𝑥 𝐺 𝑥 = + −𝑥
1 − 2𝑥 1−𝑥 2
4𝑥 2 𝑥
2
∴ 𝐺 𝑥 1 − 5𝑥 + 6𝑥 + 5𝑥 − 1 = +
1 − 2𝑥 1−𝑥 2
1 − 5𝑥 4𝑥 2 𝑥
∴𝐺 𝑥 = + 2
+
1 − 2𝑥 1 − 3𝑥 1 − 2𝑥 1 − 3𝑥 1 − 𝑥 2 1 − 2𝑥 1 − 3𝑥
 MA1002 - COMPUTATIONAL MATHEMATICS

Module 6: Recurrence Relation and Generating Function

3 2 2 2 4 5ൗ
= − − − + + 4
1 − 2𝑥 1 − 3𝑥 1 − 2𝑥 1 − 2𝑥 2 1 − 3𝑥 1−𝑥
1ൗ 4 9ൗ
+ 2 − + 4
1−𝑥 2 1 − 2𝑥 1 − 3𝑥
3 17ൗ 2 5ൗ 1ൗ
=− + 4 − + 4 + 2
1 − 2𝑥 1 − 3𝑥 1 − 2𝑥 2 1−𝑥 1−𝑥 2
∞ ∞ ∞ ∞
𝑛 𝑛 𝑛
17
∴ ෍ 𝑎𝑛 𝑥 = −3 ෍ 2 𝑥 + ෍ 3𝑛 𝑥 𝑛 − 2 ෍ 𝑛 + 1 2𝑛 𝑥 𝑛
4
𝑛=0 𝑛=0 𝑛=0 𝑛=0
∞ ∞
5 1
+ ෍ 𝑥 + ෍ (𝑛 + 1)𝑥 𝑛
𝑛
4 2
𝑛=0 𝑛=0
MA1002 - COMPUTATIONAL MATHEMATICS

Module 6: Recurrence Relation and Generating Function

17 𝑛
𝑛 𝑛
5 1
∴ 𝑎𝑛 = −3 ∗ 2 + ∗ 3 − 2 𝑛 + 1 2 + + (𝑛 + 1)
4 4 2
17 𝑛 𝑛
1
∴ 𝑎𝑛 = ∗ 3 − 2 2𝑛 + 5 + 2𝑛 + 7
4 4
MA1002 – COMPUTATIONAL MATHEMATICS

Module 6: Recurrence Relation and Generating Function

Summary
In this topic, you learnt:

Concept of recursive definition of a function.

Concept of recurrence relation.
Different types of recurrence relations.
Concept of generating function.
Application of generating function to solve
recurrence relations.
THANK YOU