There is one complication that we haven't covered yet. What happens if we have a characteristic polynomial that has multiples of the same root? It doesn't really make sense to have a solution with two terms $r^n + r^n$. The big question is how to separate these two terms. In short, the answer is to separate terms by a factor of $n^i$. In other words, for $k$ repeated roots, we have terms of the form $n^0 r^n = r^n, nr^n, n^2 r^n, \dots, n^{k-1} r^n$. This is more formally stated in the following theorem.
Theorem 25.1. Suppose that the characteristic equation for a linear homogenous recurrence has distinct real roots $r_1, \dots, r_t$ with multiplicities $m_1, \dots, m_t$ respectively such that $m_i \geq 1$ and $m_1 + \cdots + m_t = k$. Then the solutions to the recurrence take the form $$a_n = \sum_{i = 1}^t \sum_{j = 0}^{m_i - 1} n^j b_{i,j} r_i^n$$ for real constants $b_{i,j}$ with $1 \leq i \leq t$ and $1 \leq j \leq m_i$.
Example 25.2. Consider the recurrence $a_n = 6a_{n-1} - 9a_{n-2}$ with $a_0 = 2, a_1 = 3$. This recurrence has a characteristic equation $x^2 - 6x + 9 = 0$, and therefore has a root 3 of multiplicity 2. This means that our solution will be of the form $a3^n + bn3^n$. As usual, we solve for $a$ and $b$ using the initial conditions, \begin{align*} a3^0 + b \cdot 0 \cdot 3^0 &= a = 2 \\ a3^1 + b \cdot 1 \cdot 3^1 &= 3a + 3b = 3 \end{align*} This gives us $a = 2$ and $b = -1$ and so the solution to the recurrence is $$a_n = 2 \cdot 3^n - n 3^n = (2-n)3^n.$$
There is one more curveball that we can throw that is not too hard to deal with. This is when we are confronted with a nonhomogenous recurrence. We've already seen an example of such a recurrence, the Tower of Hanoi recurrence $H_n = 2H_{n-1} + 1$.
Definition 25.3. A linear nonhomogenous recurrence relation with constant coefficients is a recurrence relation of the form $$a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots c_k a_{n-k} + F(n),$$ where $c_1, \dots, c_k$ are real numbers and $F(n)$ is a nonzero function that depends only on $n$. The recurrence $$a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots c_k a_{n-k}$$ is called the associated homogenous recurrence relation.
The very convenient thing about recurrences of this form is that part of the solution is formed by the associated homogenous recurrence, and so, we can make use of our work from before. The only complication is how to deal with the nonhomogenous term.
Theorem 25.4. Let $a_n = c_1 a_{n-1} + \cdots c_k a_{n-k} + F(n)$ be a recurrence relation, where $c_1, \dots, c_k$ are real numbers and $F(n)$ is a nonzero function. If $\{g_n\}$ is a particular solution to the recurrence $a_n$ and $\{h_n\}$ is a solution to the associated homogenous linear recurrence, then all solutions of $a_n$ are of the form $\{g_n + h_n\}$.
Proof. Consider two solutions to $a_n = c_1 a_{n-1} + \cdots + c_k a_{n-k} + F(n)$, say $f$ and $g$. That is, we have \begin{align*} f_n &= c_1 f_{n-1} + c_2 f_{n-2} + \cdots c_k f_{n-k} + F(n), \\ g_n &= c_1 g_{n-1} + c_2 g_{n-2} + \cdots c_k g_{n-k} + F(n). \end{align*} Then it is clear that $f-g = h$ is a solution to the associated homogenous linear recurrence of $a_n$ and we have $f = g + h$. $\tag*{$\Box$}$
Example 25.5. Consider the recurrence $a_n = 3a_{n-1} + 2n$ with $a_0 = 2$. We know how to solve the associated homogenous recurrence, $a_n = 3a_{n-1}$, easily; we have $h_n = a3^n$ for some constant $a \in \mathbb R$.
Now, we need to find a possible solution. For now, we will guess such a solution, observing that $F(n) = 2n$, and guessing that a linear function $g_n = bn+c$ may work. Substituting this into the recurrence gives us $$bn+c = 3(b(n-1) + c) + 2n.$$ We can then rearrange this to $(2b+2)n + 2c-3b = 0$ and solve for $b$ and $c$ by \begin{align*} 2b+2 &= 0 \\ 2c-3b &= 0 \end{align*} This gives us $b = -1$ and $c = -\frac 3 2$, and we have $g_n = -n - \frac 3 2$. Then by Theorem 25.4, all solutions of our recurrence are of the form $$a_n = g_n + h_n = -n -\frac 3 2 + a 3^n.$$ To complete this solution, we just need to consider our initial condition $a_0 = 2$. This gives us \begin{align*} a_0 &= a3^0 - 0 -\frac 3 2 \\ 2 &= a - \frac 3 2 \\ a &= \frac 7 2 \end{align*} Thus, our solution is $a_n = \frac 7 2 \cdot 3^n - n - \frac 3 2$.
Of course, we would like some certainty in our lives and guessing is a bit too shaky for most of us to feel comfortable with. Surely, there's a better way? It turns out that if $F(n)$ is of a particular form, then there is.
Theorem 25.6. Let $a_n = c_1 a_{n-1} + \cdots c_k a_{n-k} + F(n)$ be a recurrence relation, where $c_1, \dots, c_k$ are real numbers and $F(n)$ is a nonzero function. Suppose $F(n)$ is of the form $$F(n) = (b_t n^t + \cdots + b_1 n + b_0)s^n,$$ where $b_0, \dots, b_t$ are real numbers and $s$ is a constant.
The distinction between the two cases at the end have to do with whether we can just tack on a term with $s^n$ to our solution. If the characteristic equation doesn't have a root $s$, then we can just add it. If $s$ is a root, then we have to multiply it by a term $n^m$ to ensure that it's separate, in the same way that we would have had to with multiples of the same root.
But what if $F(n)$ isn't of this form? Well, then we're out of luck, which is just as well, because we've reached the end of this course.