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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.