B tech. Discrete mathematics (I. T & Comp. Science Engg.) Syllabus

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:a_n  c₁a_{n 1}  c₂ a_{n 2}  …  c_k a_{n k} , where c₁, c₂, ..., c_k are constant real numbers with c_k  0.