The method for linear recurrences needs two different roots to make two different solutions. When the characteristic equation is a perfect square, there is only one root, and we need a second solution from somewhere else.
Key idea
If $r^{2} = c_{1}r + c_{2}$ has a double root $r$ (so $c_{1} = 2r$ and $c_{2} = -r^{2}$), then every solution of $a_{n} = c_{1}a_{n-1} + c_{2}a_{n-2}$ has the form $$a_{n} = (A + Bn)\,r^{n}.$$
Why it works
Check that $n r^{n}$ is a solution. With $c_{1} = 2r$ and $c_{2} = -r^{2}$: $$c_{1}(n - 1)r^{n-1} + c_{2}(n - 2)r^{n-2} = 2(n - 1)r^{n} - (n - 2)r^{n} = n r^{n}.$$ So both $r^{n}$ and $n r^{n}$ solve the recurrence, and so does $A r^{n} + B n r^{n}$. Two free constants match two starting values: $n = 0$ gives $A = a_{0}$, and $n = 1$ gives $(A + B)r = a_{1}$.
Worked examples
Worked example: A double root of $3$
Solve $a_{n} = 6a_{n-1} - 9a_{n-2}$ with $a_{0} = 1$, $a_{1} = 6$.
- $r^{2} - 6r + 9 = (r - 3)^{2} = 0$: double root $3$.
- $a_{n} = (A + Bn)3^{n}$. From $n = 0$: $A = 1$. From $n = 1$: $(1 + B) \cdot 3 = 6$, so $B = 1$.
- $a_{n} = (1 + n)3^{n}$. Check $a_{2}$: $3 \cdot 9 = 27$ from the formula, $6 \cdot 6 - 9 \cdot 1 = 27$ from the recurrence.
Answer: $a_{n} = (n + 1)3^{n}$
Worked example: A coefficient that goes negative
Solve $a_{n} = 4a_{n-1} - 4a_{n-2}$ with $a_{0} = 2$, $a_{1} = 2$.
- $r^{2} - 4r + 4 = (r - 2)^{2} = 0$: double root $2$.
- $A = a_{0} = 2$. Then $(2 + B) \cdot 2 = 2$, so $B = -1$.
- $a_{n} = (2 - n)2^{n}$: $2, 2, 0, -8, -32, \ldots$ Check $a_{3}$: $4 \cdot 0 - 4 \cdot 2 = -8$.
Answer: $a_{n} = (2 - n)2^{n}$
Worked example: Using the closed form
For $a_{n} = -6a_{n-1} - 9a_{n-2}$ with $a_{0} = 1$, $a_{1} = -6$, find $a_{4}$ from a closed form.
- $r^{2} = -6r - 9$, so $r^{2} + 6r + 9 = (r + 3)^{2} = 0$: double root $-3$.
- $A = a_{0} = 1$, and $(1 + B)(-3) = -6$ gives $B = 1$. So $a_{n} = (1 + n)(-3)^{n}$.
- $a_{4} = 5 \cdot 81 = 405$. Check by stepping: $a_{2} = 36 - 9 = 27$, $a_{3} = -162 + 54 = -108$, $a_{4} = 648 - 243 = 405$.
Answer: $405$
Where does the extra $n$ come from? If the two roots were $r$ and a nearby $s$, the combination $\frac{s^{n} - r^{n}}{s - r}$ would be a solution. As $s$ approaches $r$, this tends to the derivative of $x^{n}$ at $r$, which is $n r^{n-1}$, a constant times $n r^{n}$. The repeated root case is the limit of the distinct root case.
Common mistake
Writing $A \cdot r^{n} + B \cdot r^{n}$. That is just $(A + B)r^{n}$, one solution with one constant, and it forces $a_{1} = r\,a_{0}$. In the first example it would need $a_{1} = 3$, but $a_{1} = 6$. Check: your general solution must have two different pieces, neither a multiple of the other; for a double root the second piece carries the extra factor $n$.