Linear homogeneous recurrence relation with constant coefficients: How does one determine the solution set?

Question

According to my textbook and this Wikipedia article, a recurrence relation of the form $$ b_0 a_n + b_1 a_{n-1} + \cdots + b_k a_{n-k} = 0 $$ (EDIT: where $ b_0 \neq 0 $) has the following set of solutions (assuming $ r_1, r_2,\cdots r_p $ are the non-zero distinct roots of the characteristic polynomial and $ r'_1, r'_2, \cdots r'_q $ are non-zero roots that appear $ s_1, \cdots s_q $ times respectively):

$$ a_n = c_1 r_1^n + c_2 r_2^n + \cdots c_k r_k ^ n + k_{11} {r'_1}^n + k_{12} n {r'_1}^n + \cdots k_{1 s_1} n^{s_1} {r'_1}^n + \cdots + k_{q s_q} n^{s_q} {r'_q}^n $$

My question is, how does one prove the formula above? What I've managed to show is that if all roots are distinct, then $ u_n = c_1 r_1^n + c_2 r_2^n + \cdots c_k r_k ^ n $ is a solution to the recurrence relation.

Answer 1

Assuming $b_0\ne0$, a way to proceed is to introduce $A(x)=\sum\limits_{n=0}^{+\infty}a_nx^n$ and $B(x)=\sum\limits_{n=0}^kb_nx^n$ and to note that $A(x)B(x)$ has no power of $x$ of degree $\geqslant k$. Thus $A(x)=C(x)/B(x)$, where $C(x)$ is a polynomial of degree at most $k-1$ depending on $(b_n)_{0\leqslant n\leqslant k-1}$ and $(a_n)_{0\leqslant n\leqslant k-1}$.

The rest is as you describe it: decompose the rational function $C(x)/B(x)$ and collect the coefficients $a_n$ for $n\geqslant k$. For every root $1/r$ of $B$ with multiplicity $m$, the decomposition of $C(x)/B(x)$ includes terms $1/(1-rx)^s$ for $s\leqslant m$, and one uses the fact that $$ \frac1{(1-rx)^s}=\sum_{n=0}^{+\infty}{n+s\choose s}r^nx^n, $$ and that ${n+s\choose s}$ is a polynomial in $n$ with degree $s$ to conclude.