# 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)And the corresponding characteristic equation is:

(2)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)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)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)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)The characteristic equation for this recurrence relation is:

(7)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)Plugging in $n = 0$ and $n = 1$ gives us the following system of equations:

(9)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)