Distinct Roots - Lin. Hom. Rec. Rel. with Constant Coefficients

Distinct Roots - Linear Homogeneous Recurrence Relations with Constant Coefficients

Consider the following linear homogeneous recurrence relation with constant coefficients of order $k$ for $n \geq k$:

(1)

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

Which of course, can be rewritten as:

(2)

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

We know that the coefficients $a_1, a_2, ..., a_k$ are constants. Suppose that $f_n = q^n$ where $q \neq 0$ is a solution to the linear homogeneous recurrence relation with constant coefficients above. We've already seen on the Characteristic Equations of Linear Recurrence Relations page that the $q$ must be a root of the characteristic equation:

(3)

\begin{align} \quad x^k - a_1x^{k-1} - a_2x^{k-2} - ... - a_k = 0 \end{align}

Suppose that $q_1, q_2, ..., q_k$ are distinct roots to the characteristic equation above. Then $f_n = q_1^n$, $f_n = q_2^n$, …, $f_n = q_k^n$ are unique solutions to our linear homogeneous recurrence relation with constant coefficients. Furthermore, for constants $c_1, c_2, ..., c_k$, the following linear combination of $q_1, q_2, ..., q_k$ will also be a general solution to the linearity of the recurrence relation.

(4)

\begin{align} \quad f_n = c_1q_1^n + c_2q_2^n + ... + c_kq_k^n \quad (*) \end{align}

We want to now determine whether the coefficients $c_1, c_2, ..., c_k$ from $(*)$ above can be uniquely chosen to satisfy the initial conditions $f_0, f_1, ..., f_{n-1}$. Plugging $n = 0$ into $*$ and we must have:

(5)

\begin{align} \quad c_1q_1^0 + c_2q_2^0 + ... + c_kq_k^0 = f_0 \\ \quad c_1 + c_2 + ... + c_k = f_0 \end{align}

Plugging $n = 1$ into $*$ and we must have:

(6)

\begin{align} \quad c_1q_1^1 + c_2q_2^1 + ... + c_kq_k^1 = f_1 \\ \quad c_1q_1 + c_2q_2 + ... + c_kq_2 = f_1 \end{align}

If we continue on in this manner, then for plugging $n = k - 1$ into $*$ we must have:

(7)

\begin{align} \quad c_1q_1^{k-1} + c_2q_2^{k-1} + ... + c_kq_k^{k-1} = f_{k-1} \end{align}

Therefore the coefficients $c_1, c_2, ..., c_k$ that satisfy the initial conditions $f_0, f_1, ..., f_{k-1}$ and the linear homogeneous recurrence relation with constant coefficients are precisely the solution(s) to the following system of $k$ equations in $k$ underknowns:

(8)

\begin{align} \left\{\begin{matrix} c_1 + c_2 + ... + c_k = f_0\\ c_1q_1 + c_2q_2 + ... + c_kq_k = f_1\\ \vdots\\ c_1q_1^{k-1} + c_2q_2^{k-1} + ... + c_kq_k^{k-1} = f_{k-1} \end{matrix}\right. \end{align}

We've already noted that this system of equations has a unique solution provided that the determinant of the corresponding Vandermonde Matrix $V = \begin{bmatrix} 1 & 1 & \cdots & 1\\ q_1 & q_2 & \cdots & q_k\\ \vdots &\vdots & \ddots & \vdots \\ q_1^{k-1} & q_2^{k-1} & \cdots & q_k^{k-1} \end{bmatrix}$ is nonzero. It can be shown that provided that $q_1, q_2, ..., q_k$ are distinct (which we've already assumed) then $\det V \neq 0$ and a solution for $c_1, c_2, ..., c_k$ can be obtained by solving:

(9)

\begin{align} \quad \begin{bmatrix} 1 & 1 & \cdots & 1\\ q_1 & q_2 & \cdots & q_k\\ \vdots &\vdots & \ddots & \vdots \\ q_1^{k-1} & q_2^{k-1} & \cdots & q_k^{k-1} \end{bmatrix} \begin{bmatrix} c_1 \\ c_2 \\ \vdots \\ c_k \end{bmatrix} = \begin{bmatrix} f_0 \\ f_1 \\ \vdots \\ f_{k-1} \end{bmatrix} \end{align}

Therefore, a unique solution for the constants $c_1, c_2, ..., c_k$ exists and a unique solution can be obtained that satisfies the linear homogeneous recurrence relation with constant coefficients AND satisfies the initial conditions of $f_0, f_1, ..., f_{k-1}$.