Lecture 11

UNIT 2 : Recurrence Relations
Linear Non-Homogeneous Recurrence relation
Important Terminologies
Relation between Shift Operator and Difference Opertaor
Use of shift Operator
Solution of Linear Non-Homogeneous Recurrence Relation using

inverse operator method
Quiz
Linear Non-Homogeneous Recurrence Relation
A linear Non-homogeneous recurrence relation with constant

coefficients is a recurrence relation of the form
an = c1 an−1 + c2 an−2 + · · · + ck an−k + g (n) where c1 , c2 , · · · , ck are real
numbers and g (n) is a function not identically zero depending only on n.

The recurrence relation an = c1 an−1 + c2 an−2 + · · · + ck an−k is the

associated homogeneous recurrence relation. It plays an
important role in the solution of the nonhomogeneous recurrence
relation.

The recurrence relation an = c1 an−1 + c2 an−2 + · · · + ck an−k is the

associated homogeneous recurrence relation. It plays an
important role in the solution of the nonhomogeneous recurrence
relation.
For example, an = 3an−1 + 2n is a linear non-homogeneous
recurrence relation with constant coefficients.
Examples of associated homogeneous recurrence relation
The recurrence relation an = an−1 + 2n is a linear non-homogeneous

recurrence relation with constant coefficients. Its associated
homogeneous recurrence relation is an = an−1 .
Examples of associated homogeneous recurrence relation
The recurrence relation an = an−1 + 2n is a linear non-homogeneous

recurrence relation with constant coefficients. Its associated
homogeneous recurrence relation is an = an−1 .
The recurrence relation an = an−1 + an−2 + n2 + n + 1 is a linear

non-homogeneous recurrence relation with constant coefficients. Its
associated homogeneous recurrence relation is an = an−1 + an−2 .
Theorem 5
(p)
Theorem :If {an } is a particular solution of the nonhomogeneous linear
recurrence relation with constant coefficients
an = c1 an−1 + c2 an−2 + · · · + ck an−k + F (n),
(p) (h) (h)

then every solution is of the form {an + an }, where {an } is a solution
of the associated homogeneous recurrence relation
an = c1 an−1 + c2 an−2 + · · · + ck an−k .

Important Terminology
Shift Operator : The shift operator ”E ” is defined as the operator that

increases the argument of a function by one tabular interval. Thus,
Ean = an+1
.
Important Terminology
Shift Operator : The shift operator ”E ” is defined as the operator that

increases the argument of a function by one tabular interval. Thus,
Ean = an+1
Difference Operator : The difference operator 4 is defined by
4an = an+1 − an
.
Relation between Shift Operator and Difference Operator
We have
4an = an+1 − an
⇒ 4an = Ean − an
⇒ 4an = (E − 1)an
⇒ 4 = E − 1.
Use of sift operator
The recurrence relation an = an−1 + an−2 can also be written as
an+2 = an+1 + an .
Here, we used the shift operator E two times.
The recurrence relation an = 5an−1 − 6an−2 + 7n can also be

written as
an+2 = 5an+1 − 6an + 7n+2 .
Here also, we used the shift operator two times.

The recurrence relation an = c1 an−1 + c2 an−2 + · · · + ck an−k + g (n) can
also be written as, using shift operator as follows :
an+k − c1 an+k−1 − c2 an+k−2 − · · · − ck an = g (n + k)

⇒ (E k − c1 E k−1 − c2 E k−2 − · · · − ck−1 E − ck )an = f (n)
⇒ F (E )an = f (n).
The recurrence relation an = c1 an−1 + c2 an−2 + · · · + ck an−k + g (n) can
also be written as, using shift operator as follows :
an+k − c1 an+k−1 − c2 an+k−2 − · · · − ck an = g (n + k)

⇒ (E k − c1 E k−1 − c2 E k−2 − · · · − ck−1 E − ck )an = f (n)
⇒ F (E )an = f (n).
Here, F (m) is the characteristic equation for the associated homogeneous

recurrence relation. And, after this, we can easily find the solution of the
homogeneous recurrence relation, as we discussed earlier. And, particular
solution is given by
1
P.S. = f (n)
F (E )
Method of inverse operator to solve non-homogeneous recurrence relation
1 n 1 n
Case 1:If f (n) = an , then P.S. = a = a , F (a) 6= 0.
F (E ) F (a)
1 n 1 n
F (E ) F (a)
Example 1: Solve an = 5an−1 − 6an−2 + 7n
1 n 1 n
F (E ) F (a)
Example 1: Solve an = 5an−1 − 6an−2 + 7n
Solution:The given recurrence relation can be written as, using shift

operator,
an+2 = 5an+1 − 6an + 7n+2

⇒ an+2 − 5an+1 + 6an = 7n+2
⇒ (E 2 − 5E + 6)an = 7n+2 .
Here, the characteristic equation is
m2 − 5m + 6 = 0
⇒ (m − 3)(m − 2) = 0
⇒ m = 3, 2.
cont . . .
So, the general solution of the associated homogeneous recurrence
relation is given by
an(h) = b1 3n + b2 2n
where, b1 , b2 are constants.
cont . . .
an(h) = b1 3n + b2 2n
where, b1 , b2 are constants.
And, particular solution is given by
1
P.S. = an(p) = 7n+2
E2
− 5E + 6
1
= 49. 2 7n
E − 5E + 6
49
= 2 7n
7 −5×7+6
49 n
= 7
20
Thus, required solution is
49 n
an = an(p) + an(h) = b1 3n + b2 2n + 7 .
20
Case 2:Failure Case : If F (a) = 0, then
1 n(n − 1)(n − 2) n−3
P.S. = 3
an = a
(E − a) 3!
1 n(n − 1)(n − 2) n−3
P.S. = 3
an = a
(E − a) 3!
Example 2: Solve an = 12an−1 − 48an−2 + 64an−3 = 5.4n−3 .
1 n(n − 1)(n − 2) n−3
P.S. = 3
an = a
(E − a) 3!
Example 2: Solve an = 12an−1 − 48an−2 + 64an−3 = 5.4n−3 .
Solution:The given recurrence relation can be written as, using shift

operator,
an+3 = 12an+2 − 48an+1 + 64an + 5.4n

⇒ an+3 − 12an+2 + 48an+1 − 64an = 5.4n
⇒ (E 3 − 12E 2 + 48E − 64)an = 5.4n .
Here, the characteristic equation is
m3 − 12m2 + 48m − 64 = 0
⇒ (m − 4)3 = 0
⇒ m = 4, 4, 4.
cont . . .
an(h) = b1 4n + b2 n4n + b3 n2 4n
where, b1 , b2 , b3 are constants.

cont . . .
an(h) = b1 4n + b2 n4n + b3 n2 4n
where, b1 , b2 , b3 are constants.

And, particular solution is given by
1
P.S. = an(p) = 5.4n
(E − 4)4
n(n − 1)(n − 2) n−3
= 5. 4
3!
5
= n(n − 1)(n − 2)4n−3
6
Thus, required solution is
5
an = an(p) + an(h) = b1 4n + b2 n4n + b3 n2 4n + . n(n − 1)(n − 2)4n−3 .
6
Quiz 1
The general solution of the recurrence relation

an = 2an−1 − an−2 + 2n is
A. b1 + b2 (2)n + 2n
B. b1 + b2 n + 2n
C. b1 + b2 n + 4.2n
D. b1 + b2 (2)n + n2n
Quiz 1
The general solution of the recurrence relation

an = 2an−1 − an−2 + 2n is
A. b1 + b2 (2)n + 2n
B. b1 + b2 n + 2n
C. b1 + b2 n + 4.2n
D. b1 + b2 (2)n + n2n
Answer : C
Quiz 2
The particular solution of the recurrence relation

an = 6an−1 − 12an−2 + 8an−3 + 2n−3 is
n(n − 1)(n − 2) n−3

A. 2
3
n(n − 1)(n − 2) n
B. 2
6
n(n − 1)(n − 2) n−3
C. 2
6
n(n − 1)(n − 2) n
D. 2
3
Quiz 2
The particular solution of the recurrence relation

an = 6an−1 − 12an−2 + 8an−3 + 2n−3 is
n(n − 1)(n − 2) n−3

A. 2
3
n(n − 1)(n − 2) n
B. 2
6
n(n − 1)(n − 2) n−3
C. 2
6
n(n − 1)(n − 2) n
D. 2
3
Answer : C

Lecture 11

Uploaded by

Copyright:

Available Formats

Lecture 11

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Lecture 11

Uploaded by

Copyright:

Available Formats

UNIT 2 : Recurrence Relations

Linear Non-Homogeneous Recurrence relation

Relation between Shift Operator and Difference Opertaor

Use of shift Operator

Solution of Linear Non-Homogeneous Recurrence Relation using

A linear Non-homogeneous recurrence relation with constant

A linear Non-homogeneous recurrence relation with constant

The recurrence relation an = c1 an−1 + c2 an−2 + · · · + ck an−k is the

A linear Non-homogeneous recurrence relation with constant

The recurrence relation an = c1 an−1 + c2 an−2 + · · · + ck an−k is the

The recurrence relation an = an−1 + 2n is a linear non-homogeneous

The recurrence relation an = an−1 + 2n is a linear non-homogeneous

The recurrence relation an = an−1 + an−2 + n2 + n + 1 is a linear

an = c1 an−1 + c2 an−2 + · · · + ck an−k + F (n),

(p) (h) (h)

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

Shift Operator : The shift operator ”E ” is defined as the operator that

Shift Operator : The shift operator ”E ” is defined as the operator that

Difference Operator : The difference operator 4 is defined by

The recurrence relation an = an−1 + an−2 can also be written as

Here, we used the shift operator E two times.

The recurrence relation an = 5an−1 − 6an−2 + 7n can also be

Here also, we used the shift operator two times.

an+k − c1 an+k−1 − c2 an+k−2 − · · · − ck an = g (n + k)

an+k − c1 an+k−1 − c2 an+k−2 − · · · − ck an = g (n + k)

Here, F (m) is the characteristic equation for the associated homogeneous

Solution:The given recurrence relation can be written as, using shift

an+2 = 5an+1 − 6an + 7n+2

Here, the characteristic equation is

Solution:The given recurrence relation can be written as, using shift

an+3 = 12an+2 − 48an+1 + 64an + 5.4n

Here, the characteristic equation is

where, b1 , b2 , b3 are constants.

where, b1 , b2 , b3 are constants.

The general solution of the recurrence relation

The general solution of the recurrence relation

The particular solution of the recurrence relation

n(n − 1)(n − 2) n−3

The particular solution of the recurrence relation

n(n − 1)(n − 2) n−3

You might also like