# How to prove the characteristic equation based solution of recurrence relations?

What is the proof for / where might I find the proof to:

Let $c_1, c_2,..., c_k$ be real numbers. Suppose that the characteristic equation

$$r^k-c_1 r^{k-1}-...-c_k=0$$ has $k$ distinct roots $r_1, r_2,..., r_k$. Then a sequence $\{a_n\}$ is a solution of the recurrence relation

$$a_n=c_1a_{n-1}+c_2a_{n-2}+...+c_ka_{n-k}$$

if and only if

$$a_n=\alpha_1r_1^n+\alpha_2r_2^n+...+\alpha_kr_k^n$$

for $n = 0,1,2...$, where $\alpha_1,\alpha_2,...,\alpha_k$ are constants.

$$\overrightarrow v_{n+1}= \mathbf M \cdot \overrightarrow v_n$$ We know the solution to this recurrence relation.... $$\overrightarrow v_n=\mathbf M^n \cdot \overrightarrow v_0$$ This can be evaluated using eigenvalues, hence this is why you have eigenvalues in the solutions.
• Can you add some more detail or clarify what the values in $M$ would be? – Nick Chapman Apr 20 '15 at 18:09