Recurrence Relations

A recurrence relation is a functional relation between the independent variable x, dependent variable f(x) and the differences of various order of f (x). A recurrence relation is also called a difference equation, and we will use these two terms interchangeably.

Example1: The equation f (x + 3h) + 3f (x + 2h) + 6f (x + h) + 9f (x) = 0 is a recurrence relation.

              It can also be written as

ar+3 + 3ar+2 + 6ar+1 + 9ar = 0
yk+3 + 3yk+2 + 6yk+1 + 9yk = 0

Example2: The Fibonacci sequence is defined by the recurrence relation a_r = a_r-2 + a_r-1, r≥2,with the initial conditions a₀=1 and a₁=1.

Order of the Recurrence Relation:

The order of the recurrence relation or difference equation is defined to be the difference between the highest and lowest subscripts of f(x) or a_r=y_k.

Example1: The equation 13a_r+20a_r-1=0 is a first order recurrence relation.

Example2: The equation 8f (x) + 4f (x + 1) + 8f (x+2) = k (x)

Degree of the Difference Equation:

The degree of a difference equation is defined to be the highest power of f (x) or a_r=y_k

Example1: The equation y³_k+3+2y²_k+2+2y_k+1=0 has the degree 3, as the highest power of y_k is 3.

Example2: The equation a⁴_r+3a³_r-1+6a²_r-2+4a_r-3 =0 has the degree 4, as the highest power of a_r is 4.

Example3: The equation y_k+3 +2y_k+2 +4y_k+1+2y_k= k(x) has the degree 1, because the highest power of y_k is 1 and its order is 3.

Example4: The equation f (x+2h) - 4f(x+h) +2f(x) = 0 has the degree1 and its order is 2.