# Linear Recurrence Relations

Definition: A Linear Recurrence Relation of order $k$ for the sequence $(f_n)_{n=0}^{\infty} = (f_0, f_1, f_2, ...)$ is a recurrence relation of the form $f_n = a_1f_{n-1} + a_2f_{n-2} + ... + a_kf_{n-k} + b_n$ for $n \geq k$ where $a_1, a_2, ..., a_{n-k}, b_n$ are quantities that may or may not depend on $n$. |

For example, consider the sequence generated by the factorial function:

(1)Notice that $f_n = n! = n \cdot (n - 1) \cdot ... \cdot 2 \cdot 1$ and $f_{n-1} = (n -1)! = (n-1) \cdot ... \cdot 2 \cdot 1$ and so one such recurrence relation of order $1$ for the sequence $(f_n)_{n=0}^{\infty} = (n!)_{n=0}^{\infty}$ is:

(2)Here we have that $a_1 = n$ and $b_n = 0$.

For another example, consider the following sequence of powers of $2$:

(3)Notice that $f_n = 2^n = 2 \cdot 2^{n-1}$ and $f_{n-1} = 2^{n-1}$ and so once such recurrence relation of order $1$ for the sequence $(f_n)_{n=0}^{\infty} = (2^n)_{n=0}^{\infty}$ is:

(4)Here we have that $a_1 = 2$ and $b_n = 0$.

Now recall from the Derangements page that that if we consider a finite $n$-element set of ascending positive integers $\{ 1, 2, ..., n \}$ then a derangement of this set is an $n$-permutation $(x_1, x_2, ..., x_n)$ such that $x_i \neq i$ for all $i \in \{1, 2, ..., n \}$. We noted on the A Recurrence Relation for the Derangement Numbers page that the number of derangements of a finite $n$-element set $D_n$ satisfied the following recurrence relation:

(5)This is a linear recurrence relation of order $2$ and $a_1 = a_2 = n-1$ where $b_n = 0$.

Since we are now a little more familiar with linear recurrence relations, we will make some more definitions regarding the various types we'll come across.

Definition: A linear recurrence relation of order $k$, $f_n = a_1f_{n-1} + a_2f_{n-2} + ... + a_k f_{n-k} + b_n$ is said to have Constant Coefficients if $a_1, a_2, ..., a_k$ are constants. Furthermore, if $b_n = 0$ then this linear recurrence relation is said to be Homogeneous. |

Note that the only recurrence relation above that has constant coefficients is the recurrence relation we've established for the sequence $(2^n)_{n=0}^{\infty}$ while all of the recurrence relations above were homogeneous.