# Repeated Roots - Linear Homogeneous Recurrence Relations with Constant Coefficients

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

(1)The characteristic equation for this recurrence relation is:

(2)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)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)If we further sum all of the linear combinations then we get the general solution for our linear recurrence relation:

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