Recurrence relation (Part 2) : Linear Equations

In the post Recurrence Relation (Part 1) we studied three examples of recurrence relations. In this post we will solve them. The recurrence relation (T_n = T_n-1 + T_n-2) of Fibonacci problem is linear and has order 2 and degree 1. It is also homogeneous. The recurrence relation (T_n = 2T_n-1 + 1) of Tower of Hanoi problem is also linear. It has order 1 and degree 1 but it is non homogeneous. Recurrence relations can exist in many forms as linear or non-linear.

A linear recurrence relation looks like this

T_n = f₁(n)T_n-1 + f₂(n)T_n-2 + f₃(n)T_n-3 + ...+ f_r(n)T_n-r+...+f_n-1(n)T₁ + f(n)
The order of the recurrence relation is r if f_i(n) = 0 for i > r.
It is called homogeneous if f(n) = 0 and non-homogeneous if f(n) ≠ 0.
We will consider linear homogeneous and non-homogeneous recurrence relation with constant coefficients. A linear recurrence relation with constant coefficients is given by

T_n = C₁T_n-1 + C₂T_n-2 + C₃T_n-3 + ...+ C_rT_n-r+...+C_n-1T₁ + f(n) where C_i is a constant, 0 < i < n.
The order of the recurrence relation is r if C_i = 0 for i > r.
It is called homogeneous if f(n) = 0 and non-homogeneous if f(n) ≠ 0.

---

We will solve the linear homogeneous recurrence relation with constant coefficients first. The example of this type of equation which we are going to solve is Fibonacci Problem.
T_n = T_n−1 + T_n−2
Substitute the Terms with the r^{(the subscript)}
We get,
rⁿ = rⁿ⁻¹ + rⁿ⁻²
Divide throughout by the lowest power term which is r^n-2.
We get,
r² = r + 1
r² − r − 1 = 0
The above equation is called the characteristic polynomial of the recurrence relation and its roots are called characteristic roots.
The solution of the polynomial is r₁ = (1 + √5)/2 and r₂ = (1 − √5)/2

The solution of the recurrence relation can be written like this
T_n = A(r₁)ⁿ + B(r₂)ⁿ = A[(1 + √5)/2]ⁿ + B[(1 − √5)/2]ⁿ

T₁ = 1 = A[(1 + √5)/2] + B[(1 − √5)/2] = (A + B)/2 + (√5)/2(A − B)
T₂ = 1 = A[(1 + √5)/2]² + B[(1 − √5)/2]²
= A [1 + 5 + 2√5]/4 + B [1 + 5 − 2√5]/4
= A [6 + 2√5]/4 + B[6 − 2√5]/4

We get two relations
(A + B) + (√5)(A − B) = 2 ----(i)
and
3(A + B) + (√5)(A − B) = 2 ----(ii)

Solving the equations simultaneously, we get
3(i) - (ii)
2√5(A − B) = 4
A − B = 2/√5 and substituting in (i)  we get
A + B = 0

Again solving simultaneously,
2A = 2/√5
A = 1/√5
B = -1/√5
Hence the solution of the recurrence is
T_n = [1/√5][(1 + √5)/2]ⁿ - [1/√5][(1 − √5)/2]ⁿ

---

Next we will solve the recurrence relation T_n = 2T_n−1 + 1 which belongs to the tower of Hanoi problem.

Linear non homogeneous recurrences require us to solve for their homogeneous part then substitute a relation which satisfies the non homogeneous recurrence. There are many methods which are different from it and can be used to solve many recurrences. These methods are

1. Method of iteration
2. Method of substitution
3. Method of telescoping sums
4. Method of inspection

Here, we will use method of iteration to solve the recurrence.
In this method we substitute the earlier term in the recurrence and look at the pattern and solve the series.
T_n = 2T_n−1 + 1
T_n = 2(2T_n−2 + 1) + 1
T_n = 2(2(2T_n−3 + 1) + 1) + 1
As T₁ = 1, so we get
T_n = 2^n-1 + 1 + 2 + 2² +....+ 2^n-2
T_n = 2^n-1 + (2^n-1 − 1) = 2ⁿ − 1

---

Now we will solve the recurrence T_n = T_n-1 + k. This problem is multiplication problem. This recurrence will be solved by inspection. In inspection we write down enough terms such that we can guess the solution.
T₁ = k. Hence,
T_n  = T_n−2 + k + k
T_n  = T_n−3 + k + k + k
T_n  = T_n−4 + k + k + k + k
We can guess the solution to be T_n = nk as the number of k's increases as we use the lower terms of the recurrence and it increases by a definite number..