# 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

a_{r+3}+ 3a_{r+2}+ 6a_{r+1}+ 9a_{r}= 0 y_{k+3}+ 3y_{k+2}+ 6y_{k+1}+ 9y_{k}= 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_{0}=1 and a_{1}=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^{3}_{k+3}+2y^{2}_{k+2}+2y_{k+1}=0 has the degree 3, as the highest power of y_{k} is 3.

**Example2:** The equation a^{4}_{r}+3a^{3}_{r-1}+6a^{2}_{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.