# Prove $x_n = c_1\lambda_1^n + c_1\lambda_2^n + \dots + c_n\lambda_n^n$

We have the recursive relation $$x_n = a_{n-1}x_{n-1} + a_{n-2}x_{n-2} + \dots + a_1x_1 + a_0x_0$$. Prove that if the polynomial $$t^n - a_{n-1}t^{n-1} - a_{n-2}t^{n-2} - \dots - a_1t - a_0$$ has distinct roots $$\lambda_1, \lambda_2, \dots, \lambda_n$$ then $$x_n = c_1\lambda_1^n + c_1\lambda_2^n + \dots + c_n\lambda_n^n$$

Here, coefficients $$c_1, c_2, \dots, c_n$$ may be calculated from initial values $$x_0, x_1, \dots, x_n$$.

I'm thinking of finding some matrix $$A$$ then looking for eigenvalues and eigenvectors so that we can do $$A^n$$ but I'm stuck.

• This is a basic result from the theory of linear homogeneous recurrence relations. As $\lambda_i$ is a zero of that polynomial $x_n=\lambda_i^n$ is a solution of the recurrence. Because the $\lambda_i$s are distinct, those $n$ solutions are linearly independent (Vandermonde). Therefore you can write any initial segment $(x_0,x_1,\ldots,x_{n-1})$ as a linear combination. After that we are basically done. – Jyrki Lahtonen Nov 25 '18 at 8:03

One of the easiest approach: observe that the sequence space $$S =\{(x_n)_{n\geq 0}\;|\;x_{k+n} = a_{n-1}x_{n+k-1} + \cdots + a_0 x_k, \;\forall k\geq 0\}$$ is of dimension $$n$$ since the whole sequence is determined by $$n$$-data, $$x_0,\ldots x_{n-1}$$. And show that $$\lambda_j^n, n\geq 0$$ forms a linearly independent subset of $$S$$, and thus forms a basis.
Matrix approach is also valid. Let $$y_k = (x_k, \ldots,x_{k-n+1})'$$ for $$k\geq n-1$$. Then for companion matrix $$C = (c_{ij})$$ s.t. $$c_{1j} = a_{n-j}$$ and $$c_{ij} = 1$$ if $$i-1 = j$$ and $$0$$ otherwise, for $$i\geq 2$$, it holds that $$y_{k+1} = C y_k.$$ Then the set of eigenvalues of $$C$$ is exactly $$\{\lambda_j, 1\leq j \leq n\}$$ and $$C$$ is diagonalizable. That is, there is a basis consisting of its eigenvectors. You can see that $$y_{n+k-1} = \sum_j c_j \lambda_j^k v_j$$ where $$v_j$$'s are eigenvectors forming basis corresponding to $$\lambda_j$$ and $$y_{n-1}$$ is represented as $$\sum_j c_j v_j$$.