# 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)Which of course, can be rewritten as:

(2)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)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)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)Plugging $n = 1$ into $*$ and we must have:

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

(7)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)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)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}$.