# Method For Solving Linear Homogeneous Recurrence Relations With Constant Coefficients:

**Method for solving linear homogeneous recurrence relations with constant coefficients:** In the previous subsection, we have seen a backtracking method

for solving recurrence relation. However, not all the equations can be solved easily using this method . In this subsection, we shall discuss the method of solving a type of recurrence relation called linear homogeneous recurrence relation. Before that we shall define this class of recurrence relation.

**Definition :** **A linear homogeneous recurrence relation** of degree k with constant coefficients is a recurrence relation of the form:

, where c1, c2, ..., ck are constant real numbers with ck ≠ 0.

**Example :** Fibonacci sequence is also an example of a linear homogeneous recurrence relation of degree 2.

**Example : **The recurrence relation is not linear (due to square term), whereas the relation H_{n} = 2H_{n–1} 1 is not homogeneous (due to constant 1).

The basic approach for solving a linear homogeneous recurrence relation to look for the solution of the form a_{n} = r^{n}, where r is constant. Note that, rn is a solution to the linear homogeneous recurrence relation of degree k, if and only if; When both the sides of the equation are divided by r^{n–k} and right side is subtracted from the left side, we obtain an equation, known as characteristic equation of the recurrence relation as follows:

The solutions of the equation are called as characteristic roots of the recurrence relation.

In this subsection, we shall focus on solving linear homogeneous recurrence relation of degree 2 that is: a_{n} = c_{1}a_{n–1} c_{2}a_{n–2}. The characteristic equation of this relation is r^{2} – c_{1}r – c_{2} = 0. This is a quadratic equation and has two roots. Two cases arise.

(i) Roots are distinct, say s1 and s2. Then, it can be shown that is a solution to the recurrence relation, with

(ii) Roots are equal, say s. Then it can be shown that is a solution to the recurrence relation.

We shall use above results to solve some problems.