Characteristic Equations of Linear Recurrence Relations

Recall from the Linear Recurrence Relations page that a linear recurrence relation of order $k$ for the sequence $(f_n)_{n=0}^{\infty} = (f_0, f_1, f_2, ...)$ is a linear recurrence of the form:

(1)

\begin{align} \quad f_n = a_1f_{n-1} + a_2f_{n-2} + ... + a_kf_{n-k} + b_n \end{align}

The values of $a_1, a_2, ..., a_k, b_n$ may or may not depend on $n$. If $a_1, a_2, ..., a_k$ are constants then we said the linear recurrence relation above has constant coefficients and if $b_n = 0$ then we said this linear recurrence relation is homogeneous.

We are about to look at a method for solving linear homogeneous recurrence relations with constant coefficients but we first need to define the characteristic equation of these recurrence relations.

Definition: Let $f_n = a_1f_{n-1} + a_2f_{n-2} + ... + a_kf_{n-k}$ for $n \geq k$ be a linear homogeneous recurrence relation of order $k$, i.e., $a_1, a_2, ..., a_k$ are constants and $a_k \neq 0$. Then this recurrence relation can be rewritten as $f_n - a_1f_{n-1} - a_2f_{n-2} - ... - a_kf_{n-k} = 0$ and the Character Equation for the linear homogeneous recurrence relation with constant coefficients is the polynomial $x^k - a_1x^{k-1} - a_2x^{k-2} - ... - a_k = 0$.

For example, consider the following linear homogeneous recurrence relation with constant coefficients for $n \geq 2$:

(2)

\begin{align} \quad f_n = 2f_{n-1} + 4f_{n-2} \end{align}

We can rewrite this as:

(3)

\begin{align} \quad f_n - 2f_{n-1} - 4f_{n-2} = 0 \end{align}

The corresponding characteristic equation is:

(4)

\begin{align} \quad x^2 - 2x - 4 = 0 \end{align}

For another example, consider the following linear homogeneous recurrence relation with constant coefficients for $n \geq 4$:

(5)

\begin{align} \quad f_n = 4f_{n-1} + 3f_{n-2} + 2f_{n-3} + f_{n-4} \end{align}

We can rewrite this as:

(6)

\begin{align} \quad f_n - 4f_{n-1} - 3f_{n-2} - 2f_{n-3} - f_{n-4} = 0 \end{align}

The corresponding characteristic equation is:

(7)

\begin{align} \quad x^4 - 4x^3 - 3x^2 - 2x - 1 = 0 \end{align}

We will soon see how these characteristic equations play an important role in solving linear homogeneous recurrence relations with constant coefficients.