A recurrence relation for a sequence $\{a_n\}$ is an equation that expresses $a_n$ in terms of one or more previous terms of the sequence. A recurrence relation is called linear if $a_n$ appears as a linear combination of previous terms, and homogeneous if there is no term independent of the sequence.

The order of a recurrence relation is the difference between the highest and lowest subscripts appearing in the relation.

A linear homogeneous recurrence relation of degree $k$ with constant coefficients has the form: $a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k}$

where $c_1, c_2, \ldots, c_k$ are constants with $c_k \neq 0$.

The associated characteristic equation is: $r^k = c_1 r^{k-1} + c_2 r^{k-2} + \cdots + c_k$ or equivalently: $r^k - c_1 r^{k-1} - c_2 r^{k-2} - \cdots - c_k = 0$

A linear non-homogeneous recurrence relation has the form: $a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k} + f(n)$

where $f(n)$ is a function of $n$ (the non-homogeneous term). The general solution is: $a_n = a_n^{(h)} + a_n^{(p)}$

where $a_n^{(h)}$ is the general solution to the associated homogeneous relation and $a_n^{(p)}$ is a particular solution to the non-homogeneous relation.