What are recurrence relations?

A recurrence relation for the $a_{n}$ sequence in terms of one or more of its previous terms ($a_{0}$,$a_{1}$,$a_{2}$…$a_{n-1}$) such that n>$n_{i}$, where $n_{i}$ is a non-negative integer.

Example: Fibonacci series

{$F_{n}$} = 1, 1, 2, 3, 5,…

$F_{0}$ = 1, $F_{1}$ = 1, $F_{2}$ = 2, $F_{3}$ = 3, …

$F_{n}$ = $F_{n-1}$ + $F_{n-2}$, n >= 2

Degree of recurrence relation

The degree of recurrence relation is ‘K’ if the highest term of the numeric function is expressed in terms of its previous K terms.

Degree = highest coefficient - lowest coefficient

Linear recurrence relation with constant coefficients

The standard form of a linear recurrence relation with a constant coefficient is,

$c_{0}$$a_{n}$ + $c_{1}$$a_{n-1}$ + $c_{2}$$a_{n-2}$ +…+ $c_{k}$$a_{n-k}$

Each term of the sequence {$a_{n}$} is linear, the coefficients are $c_{0}$, $c_{1}$, $c_{2}$,…,$c_{k}$

$a_{n}$ = $a_{0}$$a_{n-1}$ + $a_{1}$$a_{n-2}$+…+$a_{n-1}$$a_{0}$

Homogeneous recurrence relation

The above equation is said to be homogenous if f( r ) = 0, i.e,

$c_{0}$$a_{n}$ + $c_{1}$$a_{n-1}$ +…+$c_{k}$$a_{n-k}$ = 0

Non-homogeneous recurrence relation

Equation is non-homogeneous if f( r ) != 0

$c_{0}$$a_{n}$ + $c_{1}$$a_{n-1}$ +…+ $c_{k}$$a_{n-k}$ != 0

General solution of the Fibonacci relation

If $F_{n}$ satisfies the fibonacci relation $a_{n}$ = $F_{n-1}$ + $F_{n-2}$ for n>=2, then there are constants $c_{1}$ and $c_{2}$ such that,

$F_{n}$ = $c_{1}$( $\frac{1 + 2.2360}{2}$ )^n + $c_{1}$( $\frac{1 - 2.2360}{2}$ )^n

Let the constant be completely determined by the initial conditions.

Solving recurrence relations by the method of characteristic roots

Let the homogeneous linear recurrence relation with constant coefficient be,

$a_{n}$ = $c_{1}$$a_{n-1}$ + $c_{2}$$a_{n-2}$ +…+ $c_{k}$$a_{n-k}$

Assume that there exists a solution of form $a_{n}$ = $r^{n}$ and substitute in the above relation.

$r^{k}$ - $c_{1}$$r^{k-1}$ - $c_{2}$$r^{k-2}$ -…-$c_{k}$ = 0 – characteristic equation.

$r_{1}$, $r_{2}$, $r_{3}$,…,$r_{k}$ are called characteristic roots.

• Roots are real and unequal: If the roots $r_{1}$, $r_{2}$,…,$r_{k}$ are real and unequal then the homogeneous solution is,

$a_{n}$ = $c_{1}$$r_{1}$^n + $c_{2}$$r_{2}$^n +…+ $c_{k}$$r_{k}$^n

$c_{1}$, $c_{2}$ are constants that are determined by the given initial conditions.

• Roots are real and equal: If two roots $r_{1}$, $r_{2}$ are equal ( $r_{1}$ = $r_{2}$ ), then the homogeneous solution is,

$a_{n}$ = ( $c_{1}$ + n$c_{2}$ )$r_{n}$