Solving LHRRs with CCs and Distinct Roots of the Characteristic Eqs.

Solving Linear Homogeneous Recurrence Relations with Constant Coefficients and Distinct Roots of the Characteristic Equation

Recall from the Distinct Roots - Linear Homogeneous Recurrence Relations with Constant Coefficients page that we saw if we had a linear homogeneous recurrence relation with constant coefficients of order $k$ such as:

(1)

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

And if the corresponding characteristic equation $x^k - a_1x^{k-1} - a_2x^{k-2} - ... - a_k = 0$ has $k$ distinct roots $q_1, q_2, ..., q_k$, then the general solution to this recurrence relation was given for constants $c_1, c_2, ..., c_k$ as:

(2)

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

If we are given the initial conditions $f_0, f_1, ..., f_{k-1}$, then we can solve for these constants $c_1, c_2, ..., c_k$ by solving the following system of equations that includes the corresponding Vandermonde matrix (which is invertible since $q_1, q_2, ..., q_k$ are distinct):

(3)

\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}

We will now look at example of solving a linear homogeneous recurrence relation with constant coefficients and such that the corresponding characteristic equation has distinct roots. Suppose that we want to solve the linear homogeneous recurrence relation with constant coefficients below with initial conditions $f_0 = 3$ and $f_1 = 5$:

(4)

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

We can rewrite this recurrence relation as:

(5)

\begin{align} \quad f_n - 7f_{n-1} + 12f_{n-2} = 0 \end{align}

The corresponding characteristic equation is:

(6)

\begin{align} \quad x^2 - 7x + 12 = (x - 3)(x - 4) = 0 \end{align}

The roots of this characteristic equation are $q_1 = 3$ and $q_2 = 4$. The general solutions is given for $c_1$ and $c_2$ as constants by:

(7)

\begin{align} \quad f_n = c_1q_1^n + c_2q_2^n = c_13^n + c_24^n \end{align}

To find the specific solution to this recurrence relation, we must use the initial conditions $f_0 = 3$ and $f_1 = 5$ and solve the following system of equations:

(8)

\begin{align} \quad \begin{bmatrix} 1 & 1\\ 3 & 4 \end{bmatrix} \begin{bmatrix} c_1\\ c_2 \end{bmatrix} = \begin{bmatrix} 3\\ 5 \end{bmatrix} \end{align}

We note that the Vandermonde matrix $V = \begin{bmatrix} 1 & 1\\ 3 & 4 \end{bmatrix}$ is invertible and $V^{-1} = \begin{bmatrix} 4 & -1\\ -3 & 1 \end{bmatrix}$ and so:

(9)

\begin{align} \quad \begin{bmatrix} c_1\\ c_2 \end{bmatrix} = \begin{bmatrix} 4 & -1\\ -3 & 1 \end{bmatrix} \begin{bmatrix} 3\\ 5 \end{bmatrix} = \begin{bmatrix} 4 & -1\\ -3 & 1 \end{bmatrix} \begin{bmatrix} 7\\ -4 \end{bmatrix} \end{align}

Therefore the solution to our linear homogeneous recurrence relation with constant coefficients where $f_0 = 3$, $f_1 = 5$ is given by:

(10)

\begin{align} \quad f_n = 7 \cdot 3^n - 4 \cdot 4^n = 7 \cdot 3^n - 4^{n+1} \end{align}