Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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