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

Repeated Roots - Linear Homogeneous Recurrence Relations with Constant Coefficients

Consider the following linear homogeneous recurrence relation with constant coefficients of order $k$:

(1)

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

The characteristic equation for this recurrence relation is:

(2)

\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 the roots of this characteristic equation. We've already seen that if these roots are distinct then the general solution to our recurrence relation is $f_n = c_1q_1^n + c_2q_2^n + ... + c_kq_k^n$ for constants $c_1, c_2, ..., c_k$ which can be determined uniquely to satisfy the initial conditions $f_0, f_1, ..., f_{k-1}$. Now suppose that $q_1, q_2, ..., q_k$ are not all distinct roots. Then there are $t < k$ roots of the characteristic equation that are distinct, call them $q_1, q_2, ..., q_t$, and let $m_1, m_2, ..., m_t$ denote their respective multiplicities.

We already note that $f_n = q_1^n$ is a solution to the recurrence relation above. Suppose that $m_1 = 2$, that is the root $q_1$ has multiplicity $2$ (i.e, $(x - q_1)^2$ appears in the simplified factorization of the characterization equation). Then $f_n = nq_1^n$ will also be a solution to the linear recurrence relation above. In fact, if $m_1 > 1$ then $f_n = q_1^n$, $f_n = nq_1^n$, …, $f_n = n^{m_1 - 1}q^n$ will all be solutions. By the linearly of our recurrence relation we also have that for suitable constants $c_{1,1}, c_{1,2}, ..., c_{1, m_1}$ that any linear combination of these solutions is also a solution:

(3)

\begin{align} \quad f_n = c_{1, 1}q_1^n + c_{1,2}nq_1^n + ... + c_{1, m_1}n^{m_1 - 1}q_1^n \\ \quad f_n = \sum_{i=1}^{m_1} c_{1, i}n^{i-1}q_1^n \end{align}

For each distinct root $q_j$ with corresponding multiplicity $m_j$ for $j \in \{1, 2, ..., t \}$ we will have that $f_n = q_j^n$, $f_n = nq_j^n$, …, $f_n = n^{m_j - 1}q^n$ will be solutions to our linear recurrence relation and so for suitable constants $c_{j,1}, c_{j,2} , ..., c_{j, m_j}$ we have that any linear combination of these solutions is also a solution:

(4)

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

If we further sum all of the linear combinations then we get the general solution for our linear recurrence relation:

(5)

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

By plugging $n = 0, 1, ..., k-1$ in the solution above we obtain the following system of $k$ equations in $k = m_1 + m_2 + ... + m_t$ unknowns:

(6)

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

And we can then obtain a specific solution $f_n$ by solving the system above for the constants $c_{j, i}$ for $j \in \{1, 2, ..., t \}$ and $i \in \{1, 2, ..., m_j \}$ satisfying the initial conditions $f_0, f_1, ..., f_{k-1}$.