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