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?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
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.
answered Jun 12, 2014 at 20:48
-
$\begingroup$ This is a nice reason, thanks! I'll go through it carefully in a bit. $\endgroup$– AxesiloJun 12, 2014 at 22:48
$\begingroup$
$\endgroup$
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.
-
$\begingroup$ 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. $\endgroup$– Community BotSep 11, 2021 at 19:53