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 Hn = 2Hn–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 an = rn, 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 rn–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: an = c1an–1 c2an–2. The characteristic equation of this relation is r2 – c1r – c2 = 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.