How do I resolve a recurrence relation when the characteristic equation has fewer roots than terms? I know how to solve "simple" recurrence relations. For instance, say you have:
$$c_0 = 20$$
$$c_1 = 30$$
$$c_n = 3 c_{n-1} - 2 c_{n-2}$$
We can write the characteristic equation as:
$$3x^{n-1} - 2x^{n-2} = x^n$$
Solving this with $n=2$, we get $x = 1$ or $x = 2$. This lets us write the relation $c_n = \alpha_1 1^n + \alpha_2 2^n$, and we can solve for $\alpha_1$ and $\alpha_2$ with the initial states $c_0$ and $c_1$.
However, this depends on the fact that $3x^{n-1} - 2x^{n-2} = x^n$ has two roots.
Now, I'm stuck on another problem where the characteristic equation has fewer roots than terms.
Say I have this recurrence relation instead:
$$a_0 = 0$$
$$a_1 = 2$$
$$a_2 = −1$$
$$a_n = 9a_{n-1} - 15a_{n-2} - 25a_{n-3}$$
The characteristic equation would be:
$$9x^{n-1} - 15x^{n-2} - 25x^{n-3} = x^n$$
However, solving with $n=3$, we only get two roots: $x=-1$ or $x=5$. There are not enough roots to write a relation in the form of $a_n = \alpha_1 r_1^n + \alpha_2r_2^n + \alpha_3r_3^n$. How do I proceed?

Use generating function directly: define $A(z) = \sum_{n \ge 0} a_n z^n$, write the recurrence with no subtractions in indices:
$$
a_{n + 3} = 9 a_{n + 2} - 15 a_{n + 1} - 25 a_n
$$
Multiply by $z^n$ and sum over $n \ge 0$, recognize:
$$
\sum_{n \ge 0} a_{n + k} z^n 
  = \frac{A(z) - a_0 - a_1 z - \ldots - a_{k - 1} z^{k + 1}}{z^k}
$$
to get:
$$
\frac{A(z) - 2 z + z^2}{z^3}
  = 9 \frac{A(z) - 2 z}{z^2}
      - 15 \frac{A(z)}{z}
      - 25 A(z)
$$
Written as partial fractions:
$$
A(z) = \frac{53}{60 (1 - 5 z)} - \frac{3}{10 (1 - 5 z)^2} - \frac{7}{12 (1 + z)}
$$
The generalized binomial theorem lets you read off coefficients:
\begin{align}
a_n &= \frac{53}{60} \cdot 5^n 
        - \frac{3}{10} \binom{-2}{n} (-5)^n
        - \frac{7}{12} \cdot (-1)^n \\
    &= \frac{53}{60} \cdot 5^n
        - \frac{3}{10} \binom{n + 2 - 1}{2 - 1} \cdot 5^n
        - \frac{7}{12} \cdot (-1)^n \\
    &= \frac{(35 - 18 n) \cdot 5^n - 35 \cdot (-1)^n}{60}
\end{align}
Repeat roots give terms including $\binom{-m}{n} = \binom{n + m - 1}{m - 1}$, which is just a polynomial of degree $m - 1$ in $n$.
