UNIT 2 : Recurrence Relations

Linear Homogeneous Recurrence relation

Solution of Linear Homogeneous Recurrence Relation
Quiz
Linear Homogeneous Recurrence Relation

A linear homogeneous recurrence relation of degree k with

constant coefficients is a recurrence relation of the form

an = c1 an−1 + c2 an−2 + · · · + ck an−k , where c1 , c2 , · · · , ck are real

numbers, and ck 6= 0.
Cont . . .

The recurrence relation in the previous definition is linear

because the right-hand side is a sum of previous terms of the
sequence each multiplied by a function of n.
The recurrence relation is homogeneous because no terms
occur that are not the multiples of aj0 s. the coefficients of the
terms of the sequence are all constants, rather than functions
that depend on n.
The degree is k, because an is expressed in terms of the
previous k terms of the sequence.
Some Examples

The recurrence relation Pn = (1.11)Pn−1 is a linear

homogeneous recurrence relation of degree 1.
The recurrence relation fn = fn−1 + fn−2 is a linear
homogeneous recurrence relation of degree 2.
The recurrence relation an = an−5 is a linear homogeneous
recurrence relation of degree 5.
Some more Examples

2
The recurrence relation an = an−1 + an−2 is not linear.
The recurrence relation Hn = 2Hn−1 + 1 is not homogeneous.
The recurrence relation Bn = nBn−1 does not have constant
coefficients.
Solving Recurrence relations

Recurrence relations may be difficult to solve, but fortunately this is not

the case for linear homogeneous recurrence relations with constant
coefficients. We can use two key ideas to find their solution.
Solving Recurrence relations

Recurrence relations may be difficult to solve, but fortunately this is not

the case for linear homogeneous recurrence relations with constant
coefficients. We can use two key ideas to find their solution.

First, these recurrence relations have solutions of the form an = r n is a

solution of the recurrence relation an = c1 an−1 + c2 an−2 + · · · + ck an−k if
and only if
r n = c1 r n−1 + c2 r n−2 + · · · + ck r n−k

When both sides of this equation are divided by r n−k (when r 6= 0) and
the right-hand side is subtracted from the left, we obtain

r k − c1 r k−1 − c2 r k−2 − · · · − ck−1 r − ck = 0

Characteristic equation and Characteristic roots

Consequently, the sequence an with an = r n where r 6= 0 is a solution if r

is a solution of the equation

r k − c1 r k−1 − c2 r k−2 − · · · − ck−1 r − ck = 0

This equation is called the characteristic equation of the given

recurrence relation and its roots (or solutions) are called the
characteristic roots of the recurrence relation.
Cont . . .

The second key observation is that a linear combination of two

solutions of a linear homogeneous recurrence relation is also a
solution.

That is, if sn and tn are both solutions of the recurrence relation

an = c1 an−1 + c2 an−2 + · · · + ck an−k , then b1 sn + b2 tn is also a
solution of the given recurrence relation, where b1 , b2 are
constants.
Cont . . .

The second key observation is that a linear combination of two

solutions of a linear homogeneous recurrence relation is also a
solution.

That is, if sn and tn are both solutions of the recurrence relation

an = c1 an−1 + c2 an−2 + · · · + ck an−k , then b1 sn + b2 tn is also a
solution of the given recurrence relation, where b1 , b2 are
constants.
Using these two key observations, we will solve linear homogeneous
recurrence relations with constant coefficients.
The Degree two Case (k = 2)

Theorem 1: Let c1 and c2 be real numbers. Suppose that

r 2 − c1 r − c2 = 0 has two distinct roots r1 and r2 . Then, the
sequence {an } is a solution of the recurrence relation
an = c1 an−1 + c2 an−2 if and only if an = a1 r1n + a2 r2n for
n = 0, 1, 2, . . . , where a1 and a2 are constants.
Example 1

Q.What is the solution of the recurrence relation: an = an−1 + 2an−2

with a0 = 2 and a1 = 7?
Example 1

Q.What is the solution of the recurrence relation: an = an−1 + 2an−2

with a0 = 2 and a1 = 7?

Solution:Here, c1 = 1 and c2 = 2. So, the characteristic equation is

given by

r 2 − c1 r − c2 = 0
⇒ r2 − r − 2 = 0
⇒ (r − 2)(r + 1) = 0
⇒ r1 = 2, r2 = −1

∴ the sequence {an } is a solution to the recurrence relation if and only if

an = α1 2n + α2 (−1)n where α1 and α2 are constants.
Example 1 cont . . .

From the given initial conditions, we have

a0 = 2 = α1 + α2 and a1 = 7 = α1 .2 + α2 .(−1)

Solving these two equations, we get

α1 = 3 and α2 = −1

Hence, the solution to the recurrence relation and initial conditions is the
sequence {an } with
an = 3.2n − (−1)n .
The Degree two Case (k = 2)

Theorem 2: Let c1 and c2 be real numbers with c2 6= 0. Suppose

that r 2 − c1 r − c2 = 0 has only one root r0 . Then, the sequence
{an } is a solution of the recurrence relation an = c1 an−1 + c2 an−2
if and only if an = a1 r0n + a2 nr0n for n = 0, 1, 2, . . . , where a1 and
a2 are constants.
Example 2

Q.What is the solution of the recurrence relation: an = 6an−1 − 9an−2

with a0 = 1 and a1 = 6?
Example 2

Q.What is the solution of the recurrence relation: an = 6an−1 − 9an−2

with a0 = 1 and a1 = 6?

Solution:Here, c1 = 6 and c2 = −9. So, the characteristic equation is

given by

r 2 − c1 r − c2 = 0
⇒ r 2 − 6r + 9 = 0
⇒ (r − 3)2 = 0
⇒ r = 3, 3

∴ the sequence {an } is a solution to the recurrence relation if and only if

an = α1 3n + α2 n3n where α1 and α2 are constants.
Example 2 cont . . .

From the given initial conditions, we have

a0 = 1 = α1 and a1 = 6 = α1 .3 + α2 .3

Solving these two equations, we get

α1 = 1 and α2 = 1

Hence, the solution to the recurrence relation and initial conditions is the
sequence {an } with
an = 3n + n3n .
Quiz 1

The solution of recurrence relation an = 2an−1 , for n ≥ 1, a0 = 3 is

A. 6n
B. 2.3n
C. 3.2n
D. 2n
Quiz 1

The solution of recurrence relation an = 2an−1 , for n ≥ 1, a0 = 3 is

A. 6n
B. 2.3n
C. 3.2n
D. 2n
Answer : C
Quiz 2

What are the characteristic roots of the recurrence relation

an = an−1 + 6an−2 ?

A. 3, -2
B. 3, 2
C. -3, 2
D. -3, -2
Quiz 2

What are the characteristic roots of the recurrence relation

an = an−1 + 6an−2 ?

A. 3, -2
B. 3, 2
C. -3, 2
D. -3, -2
Answer : A
The General Case

Theorem 3: Let c1 , c2 , . . . , ck be real numbers. Suppose that the

characteristic equation

r k − c1 r k−1 − · · · − ck = 0

has k distinct roots r1 , r2 , · · · , rk . Then a sequence {an } is a

solution of the recurrence relation

an = c1 an−1 + c2 an−2 + · · · + ck an−k

if and only if
an = a1 r1n + a2 r2n + · · · + ak rkn

for n = 0, 1, 2, . . . , where a1 , a2 , · · · , ak are constants.

Example 3

Q.What is the solution of the recurrence relation:

an = 6an−1 − 11an−2 + 6an−3 with a0 = 2, a1 = 5 and a2 = 15?
Example 3

Q.What is the solution of the recurrence relation:

an = 6an−1 − 11an−2 + 6an−3 with a0 = 2, a1 = 5 and a2 = 15?

Solution:The characteristic equation and characteristic roots are given

by

r 3 − c1 r 2 − c2 r − c3 = 0
⇒ r 3 − 6r 2 + 11r − 6 = 0
⇒ (r − 1)(r − 2)(r − 3) = 0
⇒ r1 = 1, r2 = 2, r3 = 3

∴ the sequence {an } is a solution to the recurrence relation if and only if

an = α1 1n + α2 2n + α3 3n where α1 , α2 and α3 are constants.
Example 3 cont . . .

From the given initial conditions, we have

a0 = 2 = α1 + α2 + α3 ,
a1 = 5 = α1 + α2 .2 + α3 .3,
a2 = 15 = α1 + α2 .4 + α3 .9.

Solving these simultaneous equations, we get

α1 = 1, α2 = −1, α3 = 2

Hence, the solution to the recurrence relation and initial conditions is the
sequence {an } with
an = 1 − 2n + 2.3n .
The General Case cont . . .

Theorem 4: Let c1 , c2 , . . . , ck be real numbers. Suppose that the

characteristic equation

r k − c1 r k−1 − · · · − ck = 0

has t distinct roots r1 , r2 , . . . , rt with multiplicities m1 , m2 , . . . , mt ,

respectively, so that mi ≥ 1 for i = 1, 2, . . . , t and
m1 + m2 + · · · + mt = k.
The General Case cont . . .

Then, a sequence {an } is a solution of the recurrence relation

an = c1 an−1 + c2 an−2 + · · · + ck an−k if and only if

an = (a1,0 + a1,1 n + · · · + a1,m1 −1 nm1 −1 )r1n + (a2,0 + a2,1 n + · · ·

+ a2,m2 −1 nm2 −1 )r2n + · · · + (at,0 + at,1 n + · · · + at,mt −1 nmt −1 )rtn

for n = 0, 1, 2, . . . , where ai,j are constants for 1 ≤ t and 0 ≤ j ≤ mi − 1.

Example 4

Q.What is the solution of the recurrence relation:

an = −3an−1 − 3an−2 − an−3 with a0 = 1, a1 = −2 and a2 = −1?
Example 4

Q.What is the solution of the recurrence relation:

an = −3an−1 − 3an−2 − an−3 with a0 = 1, a1 = −2 and a2 = −1?

Solution:The characteristic equation and characteristic roots are given

by

r 3 − c1 r 2 − c2 r − c3 = 0
⇒ r 3 + 3r 2 + 3r + 1 = 0
⇒ (r + 1)3 = 0
⇒ r = −1, −1, −1

∴ the sequence {an } is a solution to the recurrence relation if and only if

an = α1 (−1)n + α2 n(−1)n + α3 n2 (−1)n where α1 , α2 and α3 are
constants.
Example 3 cont . . .
From the given initial conditions, we have

a0 = 1 = α1 ,
a1 = −2 = −α1 − α2 .2 − α3 .3,
a2 = −1 = α1 + 2α2 + 4α3 .

Solving these simultaneous equations, we get

α1 = 1, α2 = 3, α3 = −2

Hence, the solution to the recurrence relation and initial conditions is the
sequence {an } with

an = (1 + 3n − 2n2 )(−1)n .
Quiz 3

The sequence {an } is a solution of the recurrence relation

an = −4an−1 − 6an−2 − 4an−3 − an−4 , where

A. an = (α1 + nα2 + n2 α3 + n3 α4 )1n

B. an = (α1 + nα2 + n2 α3 + n3 α4 )2n
C. an = (α1 + nα2 + n2 α3 + n3 α4 )(−2)n
D. an = (α1 + nα2 + n2 α3 + n3 α4 )(−1)n
Quiz 3

The sequence {an } is a solution of the recurrence relation

an = −4an−1 − 6an−2 − 4an−3 − an−4 , where

A. an = (α1 + nα2 + n2 α3 + n3 α4 )1n

B. an = (α1 + nα2 + n2 α3 + n3 α4 )2n
C. an = (α1 + nα2 + n2 α3 + n3 α4 )(−2)n
D. an = (α1 + nα2 + n2 α3 + n3 α4 )(−1)n
Answer : D
Quiz 4

Let a recurrence relation of degree 3 has characteristic roots 1, 2

and 2. Then, sequence {an } is a solution of the recurrence
relation, where

A. an = (α1 + nα2 )1n + α3 2n

B. an = (α1 + nα2 )2n + α3 1n
C. an = (α1 + α2 )1n + α3 2n
D. an = (α1 + α2 )2n + α3 1n
Quiz 4

Let a recurrence relation of degree 3 has characteristic roots 1, 2

and 2. Then, sequence {an } is a solution of the recurrence
relation, where

A. an = (α1 + nα2 )1n + α3 2n

B. an = (α1 + nα2 )2n + α3 1n
C. an = (α1 + α2 )1n + α3 2n
D. an = (α1 + α2 )2n + α3 1n
Answer : B