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

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.

## 1 Answer

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.