# Recurrence Relations

A recurrence relation for the sequence {a_{r}} is an equations that expresses a_{r} 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 a_{r} = a_{râ€“1} + 3 with initial condition

a_{1} = 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., a_{r} = a_{râ€“1} + a_{râ€“2} is a recurrence relation of order 2.

Degree of the recurrence relation :** **The degree of a recurrence relation is the highest power of a_{r} 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, C_{i}*â€™*s are constants is called a linear recurrence relation with constant coefficients of *k*th order, provided C_{0} and C_{k} both are non-zero. f(r) is the function of the independent variable â€˜râ€™ only.

e.g., 3a_{r} + 6a_{râ€“1} = 2^{r} 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Î±^{r}_{1}, 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 a_{r}. 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.

- If roots are distinct and real. Then

- If the roots are multiple roots. Let Î±
_{1}be a root of multiplying m, thenis 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.