# 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)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)We can rewrite this as:

(3)The corresponding characteristic equation is:

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

(5)We can rewrite this as:

(6)The corresponding characteristic equation is:

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