I was recently able to convince myself that if $F_n = bF_{n-1} + aF_{n-2}$, then the generating function is $G(x) = \sum_{n=0}^{\infty} F_nx^n$ is also the same as $G(x) = \frac{F_0 + x \cdot (F_1 - bF_0)}{1 - bx - ax^2}$.
Let $r$ and $R$ be the roots of $1 - bx - ax^2$. Then through partial fraction decomposition I found that
$$G(x) = \frac{F_0 + r \cdot (F_1 - bF_0)}{(r-R)(x-r)} + \frac{F_0 + R \cdot (F_1 - bF_0)}{(R-r)(x-R)}$$
which simplifies to the following for constants $\alpha$ and $\beta$:
$$G(x) = \alpha \cdot \frac{1}{1-(1/r)x} + \beta \cdot \frac{1}{1-(1/R)x}$$
which brings us back to
$$F(n) = \alpha \cdot (1/r)^n + \beta \cdot (1/R)^n$$
and if we use the root inverses instead:
$$F(n) = \alpha \cdot (r)^n + \beta \cdot (R)^n$$
these are the roots of the characteristic polynomial $x^2-bx-a=0$ (the original $1-bx-ax^2$ with coefficients reversed), and this is the form we normally associated with closed-form linear recurrences.
My question:
Sometimes if there is a $>1$ multiplicity in the roots, the closed form actually looks more like $\alpha \cdot r^n + \beta \cdot n \cdot r^n$ instead, but how do I show that this sort of thing arises? Why didn't it show up in my derivation?
I will use a numerical example to show things clearly. Let us assume that our sequence $\{a_n\}_{n\geq 0}$ has a characteristic polynomial with a simple root at $3$ and a double root at $2$, $p(x)=(x-3)(x-2)^2= x^3-7x^2+16x-12$, associated with the recurrence $$ a_{n+3}=7a_{n+2}-16 a_{n+1}+12 a_n. $$ By your previous question we know that the generating function of such a sequence fulfills $$ f(x) = \sum_{n\geq 0} a_n x^n = \frac{g(x)}{q(x)} $$ where $g(x)$ depends on the initial conditions, but $q(x)$ does not, being the "reciprocal polynomial" of $p(x)$, namely $(1-3x)(1-2x)^2$. If we apply a partial fraction decomposition to $f(x)$ we get $$ f(x) = \frac{A}{1-3x}+\frac{B}{1-2x}+\frac{C}{(1-2x)^2} $$ with $A,B,C$ being constants, and we may expand each term as its Taylor series at $x=0$. We have $$ \frac{1}{1-kx}=\sum_{n\geq 0} k^n x^n,\qquad \frac{1}{(1-kx)^2}=\sum_{n\geq 0}(n+1) k^n x^n $$ by differentiation, hence $$ a_n = A 3^n + B 2^n + C(n+1) 3^n $$ and that explains the appearance of terms like $n^k \lambda^n$ in the closed form for $a_n$, if the characteristic polynomial has a multiple root.