I understand that if I have a linear homogeneous recurrence relation of the form $q_n = c_1 q_{n-1} + c_2 q_{n-2} + \cdots + c_d q_{n-d}$, I can construct the characteristic polynomial $p(t) = t^d - c_1 t^{d-1} - \cdots - c_{d-1} t - c_d$, and if the roots are $r_1, \ldots, r_d$ (say distinct, for simplicity) I can be assured that $q_n = k_1 r_1^n + \cdots k_d r_d^n$ is a solution for any choice of coefficients $k_i$. But are these the only solutions? Is there a clean way to show this?
Asked
Active
Viewed 1,080 times
2 Answers
6
Yes, you can see it by observing that the set of all solutions is a vector space of dimension $d$; this holds because if you choose $q_1,\ldots q_d$, the rest is clearly determined. The solutions $\{r_i^n\}$ are linearly independent (which can be shown by Vandermond determinant, for example), so they generate the whole space.
Peter Franek
- 11,522
-
This is a nice reason, thanks! I'll go through it carefully in a bit. – Axesilo Jun 12 '14 at 22:48
1
This is proven in these 3 textbooks. 1. Saber Elaydi, An Introduction to Difference Equations (2005 3 ed). Pages 66, 126.
- Walter G. Kelley, Difference equations an introduction with applications by (2001 2 ed), p 50.
- Mickens, Ronald E, Difference Equations Theory, Applications and Advanced Topics (2015 3 ed), pp 84-85.
-
As it’s currently written, your answer is unclear. Please [edit] to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center. – Community Sep 11 '21 at 19:53