Uniqueness of solutions to linear recurrence relations

Question

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?

Answer 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.

• Axesilo: This is a nice reason, thanks! I'll go through it carefully in a bit.

Answer 2

This is proven in these 3 textbooks. 1. Saber Elaydi, An Introduction to Difference Equations (2005 3 ed). Pages 66, 126.

enter image description here

enter image description here

2. Walter G. Kelley, Difference equations an introduction with applications by (2001 2 ed), p 50.

enter image description here

3. Mickens, Ronald E, Difference Equations Theory, Applications and Advanced Topics (2015 3 ed), pp 84-85.

enter image description here

• Community: 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.