Linear Inhomogenous Recurrence Relations

Solve each of the following recurrence relations.

1. an = -an-1 + 2an-2 + 3; a0 = 2; a1 = 4

2. an = -4an-1 - 4an-2 + 5; a0 = 3; a1 = 12

3. an = 2an-1 + 3an-2 + 4n; a0 = a1 = 1

4. an = 6an-1 + 5; a0 = 1

5. an = 9an-2 + 4n; a1 = a2 = 0
 
 
 
 
 
 
 
 
 
 
 
 

SOLUTIONS:
1. an = -an-1 + 2an-2 + 3; a0 = 2; a1 = 4
Homogenous Portion:  an = -an-1 + 2an-2 + 3; f(n) = 3 (0 degree polynomial)
Characteristic Polynomial: a2 + a - 2 = 0; Roots at -2, 1. Note that because we have a root of 1, we'll want to 'bump up' the solution to include a higher degree polynomial. The term in the solution including the root of 1 [kj(1)n] becomes, in effect, a constant term.

Prototype: an = k1(-2)n + k2n2 + k3n + k4.

a0 = k1(-2)n + k2(0)2 + k3(0) + k4 = k1 + k4 = 2
a1 = k1(-2)1 + k2(1)2 + k3(1) + k4 = -2k1 + k2 + k3 + k4 = 4
a2 = k1(-2)2 + k2(2)2 + k3(2) + k4 = 4k1 + 4k2 + 2k3 + k4 = 3
a3 = k1(-2)3 + k2(3)2 + k3(3) + k4 = -8k1 + 9k2 + 3k3 + k4 = 8
(Values for a2 and a3 found by applying recurrence relation.)

k1 = -1, k2 = 0, k3 = -1, k4 = 3.
 an = -1(-2)n + 0n2 + (-1)n + 3  = -1(-2)n - n + 3.

2. an = -4an-1 - 4an-2 + 5; a0 = 3; a1 = 12
Homogenous portion: -4an-1 - 4an-2 ; f(n) = 5  (0 degree polynomial)
Characteristic polynomial: a2 + 4a + 4 = 0; Double root at -2.

Prototype: an = k1(-2)n + k2n(-2)n + k3

a0 = k1(-2)0 + k2(0)(-2)0 + k3 = k1 + k3 = 3
a1 = k1(-2)1 + k2(1)(-2)1 + k3 = -2k1 -2k2 + k3 = 12
a2 = k1(-2)2 + k2(2)(-2)2 + k3 = 4k1 +8k2 + k3 = -55

k1 = 16/7
k2 = -111/14
k3 = 5/7

an = (16/7)(-2)n - (111/14)(n)(-2)n + (5/7)

3. an = 2an-1 + 3an-2 + 4n; a0 = a1 = 1
Characteristic polynomial: a2 - 2a - 3 = 0; Roots at 3, -1. f(n) = 4n  (1st degree polynomial)
Prototype: an = k1(3)n + k2(-1)n + k3n + k4.
a0 = k1(3)0 + k2(-1)0 + k3(0) + k4 = k1 + k2 + k4 = 1
a1 = k1(3)1 + k2(-1)1 + k3(1) + k4 = 3k1 - k2 + k3 + k4 = 1
a2 = k1(3)2 + k2(-1)2 + k3(2) + k4 = 9k1 + k2 + 2k3 + k4 = 13
a3 = k1(3)3 + k2(-1)3 + k3(3) + k4 = 27k1 - k2 + 3k3 + k4 = 41
(Values for a2 and a3 found by applying recurrence relation.)

k1 = 7/4
k2 = 5/4
k3 = -1
k4 = -2

an = (7/4)(3)n +(5/4)(-1)n  - n -2
 

4. an = 6an-1 + 5; a0 = 1
Characteristic polynomial: a - 6 = 0; root at 6. f(n) = 5 (0 degree polynomial)
Prototype: an = k1(6)n + k2.

a0 = k1 (6)0 + k2 = k1 + k2 = 1
a1 = k1(6)1 + k2 = 6k1 + k2 = 11

k1 = 2; k2 = -1

an = 2(6)n - 1

5. an = 9an-2 + 4n; a1 = a2 = 0
Note that the recurrence goes back two steps; this is a linear inhomogeneous recurrence relation of order 2.
Homogenous Portion: an = 9an-2 ;  f(n) = 4n (1st degree polynomial).
Characteristic Polynomial: a2 - 9 = 0. Roots at -3, 3.

Protoype: an = k1(3)n + k2(-3)n + k3n + k4.
System of equations: Note that as this problem is defined, we begin at n = 1 rather than n = 0.
a1 = k1(3)1 + k2(-3)1 + k3(1) + k4 = 3k1 - 3k2 + k3 + k4 = 0
a2 = k1(3)2 + k2(-3)2 + k3(2) + k4 = 9k1 + 9k2 + 2k3 + k4 = 0
a3 = k1(3)3 + k2(-3)3 + k3(3) + k4 = 27k1 - 27k2 + 3k3 + k4 = 12
a4 = k1(3)4 + k2(-3)4 + k3(4) + k4 = 81k1 + 81k2 + 4k3 + k4 = 16

k1 = 8/9
k2 = -17/36
k3 = 11
k4 = -39/4

an = (8/9)(3)n - (17/36)(-3)n + 11n -(39/4)
 

CS 191 SI Home

Email Brian