# Recurrence Relations

A recurrence relation for the sequence {ar} is an equations that expresses ar in terms of one or more of the previous terms of the sequence.

A sequence is called a solution of a recurrence if its terms satisfy the recurrence relation.

e.g., The recurrence relation ar = arâ€“1 + 3 with initial condition
a1 = 2 defines the sequence {2, 5, 8, 11...}.

Order of recurrence relation :
The order of a recurrence relation (or difference equation) is the difference between the largest and smallest subscript appearing in the relation.

e.g., ar = arâ€“1 + arâ€“2 is a recurrence relation of order 2.

Degree of the recurrence relation :
The degree of a recurrence relation is the highest power of ar occuring in that relations.

Example  is a recurrence relation of degree 3.

L
inear recurrence relation with constant coefficients : A recurrence relation of the form.

...(i)

Where, Ciâ€™s are constants is called a linear recurrence relation with constant coefficients of kth order, provided C0 and Ck both are non-zero. f(r) is the function of the independent variable â€˜râ€™ only.

e.g., 3ar + 6arâ€“1 = 2r is the first order linear recurrence relation with constant coefficients.

A recurrence relation is said to be linear if it's degree is one.

# Homogeneous Solution of the Recurrence Relation

A homogeneous solution of a linear difference equation with constant coefficients is of the form AÎ±r1, where Î±1 is called a characteristic root and A is a constant determined by the bounded conditions. Consider a recurrence relation in the form

...(i)

Since, right hand side of Eq. (i) is set to zero, we substitute A
Î±r for ar. Eq. (i) become

...(ii)

Eq. (ii) is called characteristic equation. The solutions of this equaiton are called the characteristic roots of the recurrence relation.

A characteristic equation of kth degree has
k characteristics roots. Two cases of the roots may arise.

1. If roots are distinct and real. Then

2. If the roots are multiple roots. Let Î±1 be a root of multiplying m, then
is a homogeneous solution.

Note : Although, there is no question asked in past GATE exams from this chapter still, reading of this chapter would be helpful in future GATE exams.