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.

Answer 2

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

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

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