Solving LHRRs with CCs and Repeated Roots of the Characteristic Equation

Recall from the Repeated Roots - Linear Homogeneous Recurrence Relations with Constant Coefficients page that if we have a linear homogeneous recurrence relation with constant coefficients of order $k$ of the form:

(1)

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

And the corresponding characteristic equation is:

(2)

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

And if the roots to the characteristic equation are $q_1, q_2, ..., q_k$ which are not necessarily distinct, say only $t < k$ are distinct, i.e, $q_1, q_2, ..., q_t$, each with multiplicity $m_1, m_2, ..., m_t$ respectively, then for each $j \in \{1, 2, ..., t \}$ we will have the following satisfies the linear homogeneous recurrence relation:

(3)

\begin{align} \quad f_n = c_{j,1}q_j^n + c_{j,2}nq_j^n + ... + c_{j,m_j}n^{m_j-1}q_j^n = \sum_{i=1}^{m_j} c_{j,i}n^{i-1}q_j^n \end{align}

The general solution to this linear recurrence relation is given as the sum of all of these solutions ranging from $j = 1$ to $j = t$, that is, the general solution is given as:

(4)

\begin{align} \quad f_n = \sum_{j=1}^{t} \left ( \sum_{i=1}^{m_j} c_{j,i}n^{i-1}q_j^n \right ) \end{align}

We noted that by plugging in $n = 0, 1, 2, ..., k-1$ into this equation, then we could obtain a system of $k = m_1 + m_2 + ... + m_t$ equations in $k$ unknowns:

(5)

\begin{align} \quad \left\{\begin{matrix} f_0 = \sum_{j=1}^{t} \left (\sum_{i=1}^{m_j} c_{j, i} 0^{i-1} q_j^0 \right )\\ f_1 = \sum_{j=1}^{t} \left (\sum_{i=1}^{m_j} c_{j, i} 1^{i-1} q_j^1 \right )\\ f_2 = \sum_{j=1}^{t} \left (\sum_{i=1}^{m_j} c_{j, i}2^{i-1}q_j^2 \right )\\ \vdots \\ \quad f_{k-1} = \sum_{j=1}^{t} \left (\sum_{i=1}^{m_j} c_{j, i}(k-1)^{i-1}q_j^{k-1} \right ) \end{matrix}\right. \end{align}

The solution to the system yields the constants $c_{j, i}$ for $j \in \{1, 2, ..., t \}$ and $i \in \{1, 2, ..., m_j \}$ which can be replaced in the general solution to yield a unique solution satisfying the initial conditions $f_0, f_1, ..., f_{k-1}$.

We will now look at an example of solving a recurrence relation of this type. For example, suppose that we want to solve the following linear homogeneous recurrence relation with constant coefficients with initial conditions $f_0 = 0$ and $f_1 = 1$:

(6)

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

The characteristic equation for this recurrence relation is:

(7)

\begin{align} \quad x^2 - 6x + 9 = 0 \\ \quad (x - 3)^2 = 0 \end{align}

The only distinct root of the characteristic equation is $q_1 = 3$ and it has multiplicity $2$. Therefore we have the following general solution to our linear homogeneous recurrence relation with constant coefficients for $c_{1,1}, c_{1,2}$ as constants:

(8)

\begin{align} \quad f_n = c_{1,1}3^n + c_{1,2}n3^n \end{align}

Plugging in $n = 0$ and $n = 1$ gives us the following system of equations:

(9)

\begin{align} \quad \left\{\begin{matrix} c_{1,1} = 0 \\ 3c_{1,1} + 3c_{1,2} = 1 \\ \end{matrix}\right. \end{align}

We see that $c_{1,1} = 0$ and $c_{1,2} = \frac{1}{3}$ and so the solution to our linear homogeneous recurrence relation is:

(10)

\begin{align} \quad f_n = 0 \cdot 3^n + \frac{1}{3} \cdot n3^n \\ \quad f_n = n3^{n-1} \end{align}