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..

Linear equations

Linear equations are those equations which are linear in its variables i.e. the power of the variables are 1. There can be many kinds of linear equations depending upon the number of variables used. a single variable linear equation has one variable, a double variable linear equation has two variables, a triple variable linear equation has three variables and so on. The linear equations with two or more variables is called a multi-variable linear equation. A single variable linear equation looks like this: ax = b where x is the variable. A double variable linear equation looks like this: ax + by = c and a triple variable linear equation looks like this: ax + by + cz = d. The number of variables can extend to any number of variables.

The solution of a linear requires as much equations as there are variables in it. A single variable linear equation requires one equation. a double variable linear equation requires two variables and a three variable linear equation requires three equations. The number of variables is equal to the number of equations. When we find the solution of a set of linear equations then the solutions can be unique or dependent or no solution. The solution of a linear equation can be found with the help of substitution, elimination or with the help of determinants. The solution using determinants is very cumbersome so to simplify the steps we use Gauss algorithms which use matrix to solve such equations. Let us look at the solutions of some linear equations.

Single variable linear equation
A single variable linear equation ax = b has solution x = b/a. When we plot it on a graph then we get a straight line parallel to y-axis. As the value of y is not present in the equation therefore the solution is independent of y.

Double variable linear equation

A double variable linear equation can be solved either by substitution method or elimination method. The solution on a graph is the point of intersection of the lines represented by the two equations.

The equations are 2x − y = 3 and 4x + y = −6

Let us solve the above two equations by substitution method and elimination method.

Substitution method

In substitution method we express one variable in terms of the other and substitute it to get value of one variable. Then substitute it in any equation to get value of other variable.

Step 1:Express any one equation in terms of one variable.
2x−y = 3 ⇒ y = 2x − 3
Step 2:Substitute it in next equation.
4x + y = −6
⇒ 4x + 2x − 3 = −6
⇒ 6x = −3
⇒ x = −(1/2) = −.5
Step 3:Substitute value in the first equation.
y = 2x − 3 = 2(−.5) − 3 = −4
So solution is x = −.5 and y = −4

Elimination method

The elimination method is based on the fact that if one variable is removed from the equation then the reduced equation contains only one variable. After we can find the solution. Substitute one solution in one equation to get the other solution.

Step 1: Eliminate one variable by making coefficient of that variable equal in two equations.

2x − y = 3
4x + y = −6
Add the two equations
6x = −3
x = −(1/2) = −.5
Substitute in anyone
2(−.5) − y = 3
y = − 4

the linear equations of multi variables is found by Gauss elimination method. We will discuss about such methods in some other posts.