Linear Recurrence Relations with Constant Coefficients

A Recurrence Relations is called linear if its degree is one.

The general form of linear recurrence relation with constant coefficient is

          C₀ y_n+r+C₁ y_n+r-1+C₂ y_n+r-2+⋯+C_r y_n=R (n)

Where C₀,C₁,C₂......C_n are constant and R (n) is same function of independent variable n.

A solution of a recurrence relation in any function which satisfies the given equation.

Linear Homogeneous Recurrence Relations with Constant Coefficients:

The equation is said to be linear homogeneous difference equation if and only if R (n) = 0 and it will be of order n.

The equation is said to be linear non-homogeneous difference equation if R (n) ≠ 0.

Example1: The equation a_r+3+6a_r+2+12a_r+1+8a_r=0 is a linear non-homogeneous equation of order 3.

Example2: The equation a_r+2-4a_r+1+4a_r= 3r + 2^r is a linear non-homogeneous equation of order 2.

A linear homogeneous difference equation with constant coefficients is given by

          C₀ y_n+C₁ y_n-1+C₂ y_n-2+⋯......+C_r y_n-r=0 ....... equation (i)

Where C₀,C₁,C₂.....C_n are constants.

The solution of the equation (i) is of the form , where ∝₁ is the characteristics root and A is constant.

Substitute the values of A ∝^K for y_n in equation (1), we have

          C₀ A∝^K+C₁ A∝^K-1+C₂ A∝^K-2+⋯....+C_r A∝^K-r=0.......equation (ii)

After simplifying equation (ii), we have

          C₀ ∝^r+C₁ ∝^r-1+C₂ ∝^r-2+⋯C_r=0..........equation (iii)

The equation (iii) is called the characteristics equation of the difference equation.

If ∝₁ is one of the roots of the characteristics equation, then is a homogeneous solution to the difference equation.

To find the solution of the linear homogeneous difference equations, we have the four cases that are discussed as follows:

Case1: If the characteristic equation has n distinct real roots∝₁, ∝₂, ∝₃,.......∝_n.

Thus, are all solutions of equation (i).

Also, we have are all solutions of equation (i). The sums of solutions are also solutions.

Hence, the homogeneous solutions of the difference equation are

Case2: If the characteristics equation has repeated real roots.

If ∝₁=∝₂, then (A₁+A₂ K) is also a solution.

If ∝₁=∝₂=∝₃ then (A₁+A₂ K+A₃ K²) is also a solution.

Similarly, if root ∝₁ is repeated n times, then.

          (A₁+A₂ K+A₃ K²+......+A_n K_n-1) 

The solution to the homogeneous equation.

Case3: If the characteristics equation has one imaginary root.

If α+iβ is the root of the characteristics equation, then α-iβ is also the root, where α and β are real.

Thus, (α+iβ)^K and (α-iβ)^K are solutions of the equations. This implies

          (α+iβ)^K A₁+α-iβ)^K A₂

Is also a solution to the characteristics equation, where A₁ and A₂ are constants which are to be determined.

Case4: If the characteristics equation has repeated imaginary roots.

When the characteristics equation has repeated imaginary roots,

          (C₁+C₂ k) (α+iβ)^K +(C₃+C₄ K)(α-iβ)^K

Is the solution to the homogeneous equation.

Example1: Solve the difference equation a_{r-3ar-1+2ar-2=0.}

Solution: The characteristics equation is given by

          s²-3s+2=0 or (s-1)(s-2)=0
          ⇒ s = 1, 2

Therefore, the homogeneous solution of the equation is given by

          a_r=C¹_r+C².2^r.

Example2: Solve the difference equation 9y_K+2-6y_K+1+y_K=0.

Solution: The characteristics equation is

          9s²-6s+1=0 or (3s-1)²=0
          ⇒ s = and

Therefore, the homogeneous solution of the equation is given by
y_K=(C₁+C₂ k).

Example3: Solve the difference equation y_K-y_K-1-y_K-2=0.

Solution: The characteristics equation is s²-s-1=0
s=

Therefore, the homogeneous solution of the equation is

Example4: Solve the difference equation y_K+4+4y_K+3+8y_K+2+8y_K+1+4y_K=0.

Solution: The characteristics equation is s⁴+4s³+8s²+8s+4=0
          (s²+2s+2) (s²+2s+2)=0
          s = -1±i,-1±i

Therefore, the homogeneous solution of the equation is given by

          y_K=(C₁+C₂ K)(-1+i)^K+(C₃ +C₄ K)(-1-i)^K