5
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ This is a nice reason, thanks! I'll go through it carefully in a bit. $\endgroup$ – Axesilo Jun 12 '14 at 22:48

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.