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)

\begin{align} \quad (f_n)_{n=0}^{\infty} = (n!)_{n=0}^{\infty} = (1, 1, 2, 6, 24, 120, ...) \end{align}

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)

\begin{align} \quad f_n = \left\{\begin{matrix} nf_{n-1} & n \geq 1\\ 1 & n = 0 \end{matrix}\right. \end{align}

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

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

(3)

\begin{align} \quad (f_n)_{n=0}^{\infty} = (2^n)_{n=0}^{\infty} = (1, 2, 4, 8, 16, ...) \end{align}

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)

\begin{align} \quad f_n = \left\{\begin{matrix} 2f_{n-1} & n \geq 1\\ 1 & n = 0 \end{matrix}\right. \end{align}

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)

\begin{align} \quad D_n = (n - 1)(D_{n-1} + D_{n-2}) = (n - 1)D_{n-1} + (n - 1)D_{n-2} \end{align}

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.