Coupon Accepted Successfully!


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 675.png is a recurrence relation of degree 3.

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

680.png ...(i)

Where, Cis 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


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




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
    710.png 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.

Test Your Skills Now!
Take a Quiz now
Reviewer Name