Unit 3

Compiled by: Bishal Trital

 Recurrence Relation
Let a1 ,a2, a,3, …., an be the terms of a sequence an. Then, an is said to be recurrence relation if
it is expressed by an equation in terms of it’s previous elements.

For example: an = 2an-1 + 5an-2 is a recurrence relation.

Consider a sequence: 5, 8, 11, 14,.....

Here, the first term of the sequence a1 = 5 and we can define the sequence as an = an-1 + 3 for
n≥2.

This equation is the recurrence definition because it defines the term of sequence in reference
to its previous time.

For every recurrence relation, there must be some initial condition such as a0=2, a1=6, etc.

Compiled by: Bishal Trital

 Modeling problems with recurrence relations
Eg: A person deposits Rs. 10,000 in his account such P1= 1.11P0, where P0= 10,000.
that the amount in his account is compounded by 11% P2= (1.11)2P0
annually. How much money will be in his account after
P3= (1.11)3P0
30 years? .
.
Solution:
.

Let Pn be the amount after n years and Pn-1 be the Pn= (1.11)nP0
amount after (n-1) years. This is the required solution of the above
Now, recurrence relation.
Pn= Pn-1 + 11%Pn-1
Pn= 1.11Pn-1
which is the recurrence relation for the given problem.

Now, we have to find it’s solution.

Compiled by: Bishal Trital

 Modeling problems with recurrence relations (Contd…)
For its validity, we use mathematical induction. Therefore, by mathematical induction,
Pn= (1.11)nP0 is true.
When n = 0, P0 = P0, which is true.

Assume that it is true for any arbitrary k i.e. Pk= Now,

(1.11)kP0 is true. P30= (1.11)30 X 10,000,
which will be the amount of money in his
We have to show it is true for (k+1) i.e. P k+1= account after 30 years.
(1.11)K+1P0 is also true.
From recurrence relation,
Pn= (1.11)Pn-1
Pk+1= (1.11)Pk
Pk+1= (1.11) (1.11)kP0
Pk+1= (1.11)k+1P0

Compiled by: Bishal Trital

 Tower of Hanoi Problem
Let Hn be the number of moves required to move ‘n’ discs
from source(peg1) to destination(peg3).
First of all, with the help of peg2 and peg3, (n-1) discs
from source is arranged to temporary(peg 2). This requires
Hn-1 moves.

Then the largest disc from peg1 is moved to peg3, which

requires ‘1’ move.
Finally, (n-1) discs from peg2 are moved to peg3 with the
help of peg1 and peg2, which further requires H n-1 moves.

Hence, the recurrence relation is:

Hn = Hn-1 + 1 + Hn-1

∴ Hn = 2Hn-1 + 1
Compiled by: Bishal Trital
 Tower of Hanoi Problem (Contd…)
We need to find it’s solution. For its validity, we use mathematical
induction:
H1 = 1 (initial condition)
H2 = 2H1 + 1 = 2 + 1 For n = 1, H1 = 1, which is true.
H3 = 2(2H1 + 1) + 1 = 22H1 + 2 + 1 = 4+2+1
We assume the statement is true for k
H4 = 2(22H1 + 2 + 1) + 1 = 8 +4 + 2 + 1
number of discs i.e. Hk = 2k - 1.
.
. We have to show that it is true for k+1
. number of discs i.e. Hk+1 = 2k+1 - 1.
Hn = 2n-1 + …. + 4 + 2 + 1, is in GS.
Now, Hk+1 = 2Hk + 1 = 2(2k - 1) +1 = 2k+1 - 1
∴ Hn = 1.(2n-1)/(2-1) = 2n-1, which is the
required solution for the recurrence Hence, the solution is verified using
relation. mathematical induction.
Compiled by: Bishal Trital
 Types of recurrence relation

1. Linear homogeneous recurrence relation

2. Linear non-homogeneous recurrence relation

Compiled by: Bishal Trital

 Linear Homogeneous Recurrence Relation

A recurrence relation of the form Solving linear homogeneous recurrence

relation:
an = c1an-1 + c2an-2 + …. + ckan-k
Let an = c1an-1 + c2an-2 + …. + ckan-k be
is called linear homogeneous relation of
the linear homogeneous recurrence
degree ‘k’ where c1, c2, …, ck are
relation of degree ‘k’.
constant coefficients and ck≠ 0.
Let an = rn be the solution of this
Eg: an = 2an-1 + 5an-2 is a linear
recurrence relation then it must satisfy
homogeneous recurrence relation of
the above recurrence relation.
degree 2.
∴ rn = c1an-1 + c2an-2 + …. + ckan-k
Pn = (1.11)Pn-1 is another example.
Compiled by: Bishal Trital
 Linear Homogeneous Recurrence Relation (Contd…)
Dividing both sides by rn-k and then Theorem:
subtracting RHS from LHS, we get:
Let an = c1an-1 + c2an-2 be the linear
rk - c1k-1 - c2rk-2 - …. - ck = 0, homogeneous recurrence relation and r2 - c1r
- c2 = 0 be its characteristics equation. Then
which is called the characteristic equation
a sequence an is said to be the solution of
(degree ‘k’) of the given recurrence relation
this recurrence relation if an is of the form:
and its roots are called characteristic roots.
an = ∝1r1n + ∝2r2n
Example: an = 2an-1 + 6an-2
where ∝1 and ∝2 are the distinct roots of
r2 - 2r - 6 = 0 is the characteristic equation.
characteristic equation and ∝1 , ∝2 are
The roots of the characteristic equation can constants.
be same or different.
Compiled by: Bishal Trital
 Linear Homogeneous Recurrence Relation (Contd…)
Eg: What is the solution of the recurrence When n = 0,
relation: a0 = ∝130 + ∝2(-2)0
an = an-1 + 6an-2, with a0 = 5, a1 = 7. 5 = ∝1 + ∝2 …………..(2)

Solution: When n = 1,
a1 = ∝131 + ∝2(-2)1
The given recurrence relation is: an = an-1 + 6an-2
7 = 3∝1 - 2∝2 …………..(3)
It’s characteristic equation is : r - r - 6 = 0
2
Solving equations (2) and (3), we get:
Now, it’s roots are: r1 = 3 and r2 = -2. ∝1 = 17/5, ∝2 = 8/5

Since, the roots are distinct, the solution is of Substituting the values of ∝1 and ∝2 in equation (1)
the form: an = ∝1r1n + ∝2r2n and (2), we get:
an = (17/5).(3n) + (8/5).(-2)n, which is the required
an = ∝13n + ∝2(-2)n………..(1)
solution (explicit formula).
Compiled by: Bishal Trital
 Linear Homogeneous Recurrence Relation (Contd…)
Eg: Generate the explicit formula for Fibonacci When n = 0,
series. a0 = ∝1 + ∝2

Solution: 0 = ∝1 + ∝2 …..(2)

The recurrence relation for fibonacci series is: an = When n = 1,

a1 = ∝1((1 + √5)/2 )1 + ∝2((1 - √5)/2 )1
an-1 + an-2 [Using initial condition a0=0 and a1=1]
1 = -∝2((1 + √5)/2 ) + ∝2((1 - √5)/2 )
The characteristic equation is: r2 - r - 1 = 0
1 = ∝2((-1 - √5 + 1 - √5) / 2)
It’s roots are:
1 = ∝2 (-√5 )
r1 = (1 + √5)/2 and r2 = (1 - √5)/2 ∴ ∝2 = -1/√5 and ∝1 = 1/√5
Since, the roots are distinct, the solution is of the Substituting the values of ∝1 and ∝2 in (1), we get:
form : an = ∝1r1n + ∝2r2n
an = (1/√5)((1 + √5)/2 )n + (-1/√5)((1 - √5)/2 )n, which is
an = ∝1((1 + √5)/2 )n + ∝2((1 - √5)/2 )n….(1) the required solution.
Compiled by: Bishal Trital
 Linear Homogeneous Recurrence Relation (Contd…)
★ If the roots of the characteristic equation r2 - c1r - c2 = When n = 0,
0 are equal roots, then the solution is of the form: an = a0 = ∝120 + 0
∝1rn + n∝2rn
3 = ∝120 + 0
★ Eg: what is the solution of the recurrence relation an =
4an-1 - 4an-2, with a0 = 3 and a1 = 5? ∴ ∝1 = 3

Solution: When n = 1,
a1 = ∝121 + ∝221
The recurrence relation is: an = 4an-1 - 4an-2

The characteristic equation is: r2 - 4r + 4 = 0

5 = 2∝1 + 2∝2

It’s roots are: 5 = 2.3 + 2∝2

r=2,2 ∝2 = -1/2
∴

The solution is of the form : an = ∝1rn + n∝2rn Substituting the values of ∝1 and ∝2 in (1), we get:

an = ∝12n + n∝22n….(1) an = 3.2n - (1/2).n.2n, which is the required solution.

Compiled by: Bishal Trital
 Linear Non-Homogeneous Recurrence Relation
A recurrence relation of the form: The solution of the associated
an = c1an-1 + c2an-2 + … + ckan-k + f(n)
homogeneous part is called the General
Solution and the solution of the non-
is called non-homogeneous recurrence homogeneous part is called the
relation. Particular Solution.
Here, an = c1an-1 + c2an-2 + … + ckan-k is
Hence, the solution of the given linear
called the associated homogeneous part
non-homogeneous recurrence relation
and f(n) is called the non-homogeneous
is the sum of general solution and
part.
particular solution.
Eg: an = an-1 + 5an-2 + 7n is a linear non-
homogeneous recurrence relation.
Compiled by: Bishal Trital
 Linear Non-Homogeneous Recurrence Relation (Contd…)
★ What is the solution of the recurrence The non-homogeneous part is: an = 7n
relation an=6an-1-9an-2+ 7n with a0 = 3 and a1
= 7? Assume it’s solution is: an = c17n
Solution: Now, it must satisfy the given
The given recurrence relation is: recurrence relation.
an = 6an-1 - 9an-2 + 7n
c17n = 6c17n-1 - 9c17n-2 + 7n
The associated homogeneous part is:
an = 6an-1 - 9an-2 c1 = 6c17-1 - 9c17-2 + 1
It’s characteristics equation is:
(1 - 6/7 + 9/49).c1 = 1
r2 - 6r + 9 = 0 ∴ r = 3,3

Then, it’s solution is: GS = ∝13n + n∝23n ∴ c1 = 49/16 and PS = (49/16).7n

Compiled by: Bishal Trital
 Linear Non-Homogeneous Recurrence Relation (Contd…)

Now, Applying initial conditions: a1 = 7

an = GS + PS 7 = ∝1.3 + ∝2.3 + (49/16).7
∴ an = ∝13n + n∝23n + (49/16).7n 7 = (-1/16).3 + ∝2.3 + (343/16)
Applying initial conditions : a0 = 3 ∴ ∝2 = -19/4

3 = ∝1 + 0 + (49/16) ∴ an = (-1/16).3n + (-19/4).n.3n + (49/16).7n,

which is the required solution.
∴ ∝1 = -1/16

Compiled by: Bishal Trital

 Linear Non-Homogeneous Recurrence Relation (Contd…)
To find the particular solution, we find an Let a non-homogeneous recurrence relation be
appropriate trial solution. Fn=AFn–1+BFn−2+f(n) with characteristic roots
Let f(n) = cxn; let x2 = Ax+B be the characteristic x1=2 and x2=5. Trial solutions for different
equation of the associated homogeneous possible values of f(n) are as follows:
f(n) Trial solutions
recurrence relation and let x1 and x2 be its roots.
4 A
If x ≠ x1 and x ≠ x2, then an = Axn
5.2n An2n
If x = x1 and x ≠ x2, then an = n.Axn
8.5n An5n
If x = x1 and x = x2, then an = n2.Axn
4n A4n

2n2+3n+1 An2+Bn+C

Compiled by: Bishal Trital

 Linear Non-Homogeneous Recurrence Relation (Contd…)
Problem Since f(n) = 7.5n, i.e. of the form c.xn, a reasonable trial
solution of at will be Anxn. ∴ an= Anxn = An5n
Solve the recurrence relation an= 3an−1+10an−2+7.5n where
a0=4 and a1=3. After putting the solution in the recurrence relation, we get:

Solution An5n = 3A(n–1)5n−1 + 10A(n–2)5n−2 + 7.5n

This is a linear non-homogeneous relation, where the Dividing both sides by 5n−2, we get
associated homogeneous equation is an=3an−1+10an−2 and
An52 = 3A(n−1)5 + 10A(n−2)50 + 7.52
f(n)=7.5n
Or, 25An = 15An − 15A + 10An − 20A + 175
The characteristic equation of its associated homogeneous
relation is: Or, 35A = 175

x2−3x−10=0, whose roots are x1 = 5 and x2 = -2. Or, A=5

Hence, homogeneous solution is: an = ∝1.5n + ∝2.(−2)n, So, an = An5n = 5n5n = n5n+1
where ∝1 and ∝2 are constants.
Compiled by: Bishal Trital
 Linear Non-Homogeneous Recurrence Relation (Contd…)
The solution of the recurrence relation can be written as −

an = an(h) + an(p)

an = ∝1.5n + ∝2.(−2)n + n5n+1

Putting values of a0=4 and a1=3, in the above equation, we get ∝1=−2 and ∝2=6

Hence, the solution is −

an= 6.(−2)n − 2.5n + n5n+1

Compiled by: Bishal Trital

 Linear Non-Homogeneous Recurrence Relation (Contd…)
What is the general form of the particular solution The particular solution is of the form p3n3 + p2n2 +
guaranteed to exist of the linear non homogeneous p1n + p0.
recurrence relation an = 8an−2 − 16an−4 + F(n) if:
b) F(n) = (−2)n?
a) F(n) = n3?
we know that −2 is a root with multiplicity 2, so the
We first need to find the associated homogeneous particular solution is of the form n2p0(−2)n.
recurrence relation: an = 8an−2 − 16an−4
c) F(n) = n2n?
Characteristic equation: r4 − 8r2 + 16 = 0
We know that 2 is a root with multiplicity 2, so the
Factor to find roots: (r + 2)(r − 2)(r + 2)(r − 2) = 0 particular solution is of the form n2(p1n + p0)2n.

Our roots are r1 = 2 with multiplicity 2 and r2 = −2 d) F(n) = n24n?

with multiplicity 2.
We know that 4 is not a root, so the particular
solution is of the form (p2n2 +p1n + p0)4n.
Compiled by: Bishal Trital
 Linear Non-Homogeneous Recurrence Relation (Contd…)
e) F(n) = (n2 − 2)(−2)n?

We know that −2 is a root with multiplicity 2, so the

particular solution is of the form n2(p2n2 + p1n + p0)(−2)n.

f) F(n) = n42n?

We know that 2 is a root with multiplicity 2, so the

particular solution is of the form n2(p4n4 + p3n3 + p2n2 +
p1n + p0)2n.

g) F(n) = 2?

or, F(n) = 2.1n

We know that for sn, s = 1 and 1 is not a root, so the

particular solution is of the form p0.

Compiled by: Bishal Trital

 Linear Non-Homogeneous Recurrence Relation (Contd…)
Consider an - 7an-1 + 10an-2= 6 + 8n, a0= 1 and a1= 2 Now, it’s particular solution is:

Solution: an = Cn + D

Associated homogeneous part is: a n - 7an-1 + 10an- Cn + D - 7[C(n-1)+D] + 10[C(n-2)+D] = 6 + 8n

=0
2
Cn + D - 7Cn + 7C - 7D + 10Cn - 20C + 10D = 6 + 8n
It’s characteristics equation is: 4Cn - 13C + 4D = 6 + 8n
r2 - 7r + 10 = 0 ∴ r = 5,2 Two polynomials are equal only if their coefficients
Now, the general solution is: are equal i.e.

an = ∝12n + ∝25n…….(1) 4C = 8 => C = 2

It’s non homogeneous part is: an = 6 + 8n And -13C + 4D = 6 => D = 8

∴ an = 2n + 8 …..(2)
Compiled by: Bishal Trital
 Linear Non-Homogeneous Recurrence Relation (Contd…)
∴ an = GS + PS

∴ an = ∝12n + ∝25n + 2n + 8 …..(3)

Apply initial conditions: a0 = 1 and a1 = 2.

a0 = ∝ 1 + ∝ 2 + 8

∴ ∝1 + ∝2 = -7 …..(4)

a1 = 2∝1 + 5∝2 + 10

∴ 2∝1 + 5∝2 = -8 …..(5)

Solving 4 and 5, we get: ∝1 = -9 and ∝2 = 2.

From 3, an= -9.2n + 2.5n + 2n + 8 is the required soln.

Compiled by: Bishal Trital
 Example
Q. an = -2nan-1 + 3n(n-1)an-2, a0 = 1, a1 = 2 General solution is:
Solution: bn = c11n + c2(-3)n …….(1)
[an / n!] = [-2nan-1 / n!] + [3n(n-1)an-2 / n!]
When n = 0, b0 = c1 + c2
[an / n!] = [-2an-1 / (n-1)!] + [3an-2 / (n-2)!]
a0/0! = c1 + c2
Put bn = an/n!
∴ c1 + c2 = 1 ….(2) [∵ a a0 = 1]
Then,
When n = 1, b1 = c1 - 3c2
bn = -2bn-1 + 3bn-2

The characteristics equation is: a1/1! = c1 - 3c2

r2 + 2r - 3 = 0 ∴ r = 1, -3 ∴ c1 - 3c2 = 2 ….(3) [∵ a a1 = 2]
Compiled by: Bishal Trital
 Example (Contd…)

Solving 2 and 3, we get:

c1 = 5/4 and c2 = -¼

∴ bn = (5/4). 1n - (1/4).(-3)n

∴ bn = 5/4. - (1/4).(-3)n

Thus,

an = n!bn

∴ an = (n!/4).[5 - (-3)n], which is the

required solution.
Compiled by: Bishal Trital
 Example (Contd…)
★ Assume that the deer population of Let dn denotes the deer population after
Rustic country is 1000 at time n=0 n years and dn-1 denotes the deer
and increases from time n-1 to time population after n-1 years.
n by 10% of the size at time n-1.
Given that d0 =1000 and
Write a recurrence relation and an
condition that define the deer dn = dn-1 + 10% of dn-1
population at time n and then solve
the recurrence relation. ∴ dn = 1.1 dn-1,

which is the recurrence relation. Now

we have to find it’s solution:

Compiled by: Bishal Trital

 Example (Contd…)
Now, Let us assume that it is true for n = k.
d0 = 1000 i.e. dk = (1.1)kd0 is true.
d1 = (1.1)d0 We need to show that it is true for n = k+1
d2 = (1.1)d1 = (1.1)2d0 i.e. dk+1 = (1.1)k+1d0.

d3 = (1.1)3d0 Now,

Similarly, dn = (1.1)nd0, which is the required dk+1 = (1.1)dk = (1.1)(1.1)kd0

recurrence relation.
∴ dk+1 = (1.1)k+1 d0
For its validity, we use mathematical induction.
So, it is proved by mathematical induction.
When n=0, d0 = d0 which is true.
Compiled by: Bishal Trital
 Example (Contd…)
★ Assume that the deer population of Let dn denotes the deer population after n
Rustic country is 500 at time n=0 years and dn-1 denotes the deer population
and 550 at time n=1 and that the after n-1 years. Then, by question:
increase from time n-1 to time n is (dn - dn-1) = 2(dn-1 - dn-2)
twice the population increase from dn -3 dn-1 + 2dn-2 = 0
time n-2 to time n-1. Write a
recurrence relation and an initial It’s characteristics equation is:
condition that define the deer r2 - 3r + 2 = 0 ∴ r = 1,2
population at time n and then solve
The general solution is:
the recurrence relation.
dn = c1.1n + c2.2n …..(1)
Compiled by: Bishal Trital
 Example (Contd…)

Given that the initial conditions are: Solving 2 and 3, we get:

d0 = 500 and d1 = 550 C1 = 450

When n=0, from 1, we get: C2 = 50

d0 = c1 + c2 From 1, the required solution is:

∴ c1 + c2 = 500 …..(2) dn = 450 + 50. 2n

When n=1, from 1, we get:

d0 = c1 + 2c2

∴ c1 + 2c2 = 550 …..(3)

Compiled by: Bishal Trital
 Example (Contd…)
Find a recurrence relation and initial Find a recurrence relation and initial conditions that
conditions that generates a sequence that generates a sequence that begins with given terms:
begins with given terms: 1, 3, 7, 13, 21, ….. 1, 1, 2, 4, 16, 128, 4096.
Solution: Solution:

a1 = 1 a1 = 1

a2 = 3 = 1 + 2 = a1 + 2(2-1) a2 = 1

a3 = 7 = a2 + 2(3-1) a3 = 2 x a2 x a1

Similarly, a4 = 2 x a3 x a2

a =2xa xa
an = an-1 + 2(n-1), n ≥ 1, which is the required 5 4 3

recurrence relation. Hence, the recurrence relation is: an = 2 x an-1 x an-2

for n ≥ 1.
Compiled by: Bishal Trital
 Example (Contd…)
Suppose a number of virus in a colony triples V = 3V
1 0
every hour. Find recurrence relation for the
number of virus after n hours have elapsed. If
100 virus were there in a colony in the
V2 = 3V1 = 32V0
beginning, how many virus will be there after
12 hours? V3 = 3V2 = 33V0

Solution: Similarly,
Let Vn be the virus after n hours and Vn-1 be
Vn = 3nV0, which is the solution of the
the virus after n-1 hours.
recurrence relation.
Now, Vn = 3Vn-1, which is the recurrence
relation.
We have to find its solution.

Compiled by: Bishal Trital

 Example (Contd…)
For its validity, we use mathematical induction So, by mathematical induction process:
When n=0, V0 = V0, which is true. Vn = 3nV0 is true.
Let us assume it is true for n=k i.e. Vk = 3kV0.
When n = 12,
We need to show that it is true for n = k+1
V12 = 312V0 = 312 x 100
i.e. Vk+1 = 3k+1V0
Now, ∴ V12 = 53144100 virus.

Vk+1 = 3Vk = 3.3kV0

∴ Vk+1 = 3k+1V0
Thus, Vk+1 is also true.

Compiled by: Bishal Trital