Solving linear homogeneous recurrence relations

Solving linear homogeneous recurrence relations with examples

1. SOLVING RECURRENCE
RELATIONS
Dr. Maamoun Ahmed © 2018

2. Introduction
•A sequence defined in terms of recursion requires:
1)Recurrence Relation, and
2)Initial Conditions

•Example: the sequence 1,1,2,3, 5, 8, 13, 21, …etc
(Fibonacci sequence), can be defined in terms of
recursion as:
1)Recurrence Relation: f
n=f
n-1+f
n-2
2)Initial Conditions: f
0=0, f
1=1

3. Types of Recurrence Relations
Recurrence Relations can be divided into:
1)Linear (
2)Non-Linear

Examples:
-f
n = 4f
n-1 + f
n-2 [Linear]
-f
n = 3f
n-1 + 2f
n-2 + n [Linear]
-f
n = 3(f
n-1)
2
+ 2f
n-2 + n

[Non-Linear]
-f
n = 2f
n-1·f
n-2 + n

[Non-Linear]
-f
n = n·f
n-2 + n

[Non-Linear]

4. Types of Linear Recurrence Relations
Linear Recurrence Relations, on the other hand, can be
divided into:
1)Homogeneous: no additional terms that do not refer to
numbers in the sequence
2)Non-Homogeneous: additional terms that do not refer to
the number of the sequence can be added

Examples:
-f
n = 4f
n-1 + f
n-2 [homogeneous]
-f
n = 3f
n-1 + 2f
n-2 + n
2
[Non homogeneous]
-f
n = 2f
n-1 + 5f
n-2 + n [Non homogeneous]

5. Solving linear homogeneous recurrence
relations
•Generally, linear homogenous recurrence relations
(LHRR) of degree k has the following form:
a
n = c
1a
n-1 + c
2a
n-2 + … + c
ka
n-k , where
c
1, c
2, …, c
k are real numbers, and c
k ≠ 0

Regarding the initial conditions, the recurrence relations
should have k initial conditions such that:
a
0=c
0, a
2=c
2, …..a
k=c
k
Example: for the recurrence relation a
n=2a
n-1+4a
n-2
k=2, therefore, we should have 2 initial conditions to be
able to solve the recurrence relations, a
0=1, a
1=2

6. Solving linear homogeneous recurrence
relations
•Recurrence relation: a
n = c
1a
n-1 + c
2a
n-2 + … + c
ka
n-k
•We try to find a solution of the form x
n

•Change each subscript of a (a
n) to superscript of x (x
n
)
x
n
= c
1x
n
+ c
2x
2
+ … + c
kx
n-k

•Move all items to the left-hand side:
x
n
- c
1x
n
- c
2x
2
- … - c
kx
n-k
=0
•Divide all by x
n-k
:
x
k
- c
1x
k-1
- c
2xk
k-2
- … - c
k

=0
•Now we achieved the characteristic equation.

7. Solving linear homogeneous recurrence
relations
Theorem 1:
•Consider the characteristic equation:
x
k
- c
1x
k-1
- c
2xk
k-2
- … - c
k

=0
For the recurrence relation:
a
n = c
1a
n-1 + c
2a
n-2 + … + c
ka
n-k
Assume that x
1, x
2, …, x
m are different solutions that satisfy the
recurrence.
Let α
1, α
2, α
3, ….., α
m are constants
•Then:
a
n = α
1 x
1
1
+ α
2 x
2
2
+ … + α
mx
m
m

Satisfies the recurrence
•Finally, we find solutions of the recurrence relation and values
of the constants α
1 to α
m relaying on the initial conditions.

8. Solving linear homogeneous recurrence
relations
Example 1: Find the solution of the recurrence relation:
a
n = a
n-1+6a
n-2 Given: a
0=1 and a
1=2
First find the characteristic equation:
a
n - a
n-1-6a
n-2=0
x
2
-x-6=0 (characteristic equation)
(x+2)(x-3) = 0
Thus, x=-2,3 are solutions.
Therefore, a
n= α
1 (-2)
n
+ α
2(3)
n
satisfies the recurrence.
Find α
1 and α
2 by using the initial conditions.
a
0= α
1 + α
2 = 1 >> α
1 =1- α
2 …(1)
and, a
1= α
1 (-2)
1
+ α
2 (3)
1
=2 (substitute (1) here) >>
1- α
2(-2) + α
2 (3) = 2 >>
6 α
2 =2
α
2 =1/3 and hence α
1=2/3

Therefore,
a
n= 2/3(-2)
n
+ 1/3(3)
n
is the solution to the recurrence relation above.

9. Solving linear homogeneous recurrence
relations
Example 2: Find the solution of the recurrence relation:
a
n = -a
n-1+4a
n-2 +4a
n-3 Given: a
0=8 and a
1=6 a
1=26
First find the characteristic equation:
a
n - a
n-1-6a
n-2=0
x
3
+x
2
-4x-4=0 (characteristic equation)
(x+1)(x+2)(x-2) = 0
Thus, x=-1,-2, 2 are solutions.
Therefore, a
n= α
1 (-1)
n
+ α
2(-2)
n
+α
3(2)
n
satisfies the recurrence.
Find α
1,α
2 and α
3 by using the initial conditions.
a
0= α
1 + α
2 + α
3
= 8 …(1)
a
1= -α
1 -2α
2 + 2α
3
= 6 …(2)
a
2= α
1 + 4α
2 + 4α
3
= 26 …(3)
Solving:
α
1 =2, α
2=1, and α
3=5
Therefore,
a
n= 2 (-1)
n
+ (-2)
n
+ 5(2)
n
is the solution to the recurrence relation above.

10. Solving linear homogeneous recurrence
relations
Theorem 2:
•Consider the characteristic equation:
x
k
- c
1x
k-1
- c
2xk
k-2
- … - c
k

=0
For the recurrence relation:
a
n = c
1a
n-1 + c
2a
n-2 + … + c
ka
n-k
Assume that x
1, x
2, …, x
m are similar solutions that satisfy the
recurrence.
Let α
1, α
2, α
3, ….., α
m are constants
•Then:
a
n = α
1 x
1
1
+ α
2 (n)x
2
2
+ … + α
m(n)
m
x
m
m

Satisfies the recurrence
•Finally, we find solutions of the recurrence relation and values
of the constants α
1 to α
m relaying on the initial conditions.

11. Solving linear homogeneous recurrence
relations
Example: Find the solution of the recurrence relation:
a
n = 6a
n-1-9a
n-2 Given: a
0=1 and a
1=6
First find the characteristic equation:
a
n - 6a
n-1+9a
n-2=0
x
2
-6x+9=0 (characteristic equation)
(x-3)(x-3) = 0
Thus, x=3,3 are solutions (similar)
Therefore, a
n= α
1 (3)
n
+ α
2 (n)(3)
n
satisfies the recurrence.
Find α
1 and α
2 by using the initial conditions.
a
0= α
1 = 1 >> α
1 =1 …(1)
and, a
1= α
1 (3)
1
+ α
2 (1)(3)
1
=6 (substitute (1) here) >>
3+ 3α
2 = 6 >>
α
2 =1
Therefore,
a
n= (3)
n
+ n(3)
n
is the solution to the recurrence relation above.