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


if and only if


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


This can be shown with matrices. Note that your relation can be expressed in matrix/vector form as a system of equations.

$$\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.

  • $\begingroup$ Can you add some more detail or clarify what the values in $M$ would be? $\endgroup$ – Nick Chapman Apr 20 '15 at 18:09
  • $\begingroup$ @NickChapman They would be the coefficients multiplying the v vector, the variables in the relation. $\endgroup$ – Zach466920 Apr 20 '15 at 18:23

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.