A question regarding recurrences I have often come across the fact that if we have a recurrence relation of the form $$f(n)=a_1f(n-1)+a_2f(n-2)+\dots+a_kf(n-k)$$ then $f(n)=b_1r_1^n+b_2r_2^n+\dots+b_kr_k^n$, where $r_1,r_2,\dots,r_k$ are the roots of the polynomial $x_k=a_1x^{k-1}+a_2x^{k-2}+\dots +a_k$. 
I have searched far and wide, but could never quite find a proof. Could someone please point me to one, or maybe write the proof itself?
 A: Suppose for simplification that the polyomial has $n$ distinct roots.
First, considering $F(n) = (f(n+k), \ldots , f(n))$ you can make the problem go to the space $\Bbb R^{k+1}$ and assume that the relation is 
$$F(n) = AF(n-1)$$
where $A$ has the form of a companion matrix.
The characteristic polynomial of $A$ is the polynomial giving the characteristic equation,
and as it has distinct roots $A$ is then diagonalizable, with eigenvalues $r_k$.
Let us consider a basis of eigenvectors $v_k$ associated to the root $r_k$.
Then write the decomposition of the initial condition wrt the basis:
$$
F(0)= \sum F_kv_k
$$
then:
$$
F(n)= \sum F_kr_k^n v_k
$$
and projection on the last coordinate gives you the result.
A: Use generating functions, e.g. define $F(z) = \sum_{n \ge 0} f(n) z^n$. Then you have:
$$
\sum_{n \ge 0} f(r + n) z^n
  = \frac{F(z) - f(0) - f(1) z - \cdots f(r - 1)z^{r - 1}}{z^r}
$$
Set up your recurrence like:
$$
a_k f(n + k) + a_{k - 1} f(n + k - 1) + \cdots + a_0 f(n) = 0
$$
Multiply by $z^n$, sum over $n \ge 0$, and recognize the above:
$$
a_k \frac{F(z) - f(0) - \cdots - f(k - 1) z^{k - 1}}{z^k} 
  + \cdots + F(z) = 0
$$
This is a linear equation in $F(z)$, it's form is seen to be:
$$
F(z) = \frac{Q(1/z)}{A(1/z)}
$$
where $A(z) = a_k z^k + \cdots + a_0$, and $Q(z)$ depends on your initial values. If you now divide $F(z)$ into partial fractions, expressing the terms as geometric series gives the expression you mention.
