General formula for linear difference equations Assume the difference equation
$$x_{n+2} = ax_{n+1}+x_n$$
If we were to find a general expression of $x_n$ , we do it by considering a matrix $$A=
        \begin{pmatrix}
        a & 1  \\
        1 & 0  \\
        \end{pmatrix}
$$
giving us eigenvalues $\lambda_1,\lambda_2 $ . 
However, the general solution for such equation is 
$$x_{n} = \alpha(\lambda_1)^n+\beta(\lambda_2)^n$$
Can somebody explain how this general solution is acquired?
 A: Define 
$$
Y_{n+1} = \begin{pmatrix} x_{n+2} \\ x_{n+1}\end{pmatrix} = \begin{pmatrix}a & 1 \\ 1 & 0\end{pmatrix}\begin{pmatrix}x_{n + 1} \\ x_n \end{pmatrix} = A Y_{n} \tag{1}
$$
That is,
$$
Y_{n + 1} = A Y_{n} \tag{2}
$$
To solve Eqn. (2) imagine that $A$ is diagonalizable $A = U \Lambda U^{-1}$ with $\Lambda = {\rm diag}(\lambda_1, \lambda_2)$, so that
\begin{eqnarray}
Y_1 &=& A Y_0 \\
Y_2 &=& A Y_1 = A (A Y_0) = A^2 Y_0 = (U\Lambda U^{-1})(U\Lambda U^{-1}) Y_0 = U\Lambda^2 U^{-1}Y_0 \\
&\vdots& \\
Y_{n}&=& U \Lambda^n U^{-1} Y_0 = U\begin{pmatrix} \lambda_1^n & 0 \\ 0 & \lambda_2^n \end{pmatrix} U^{-1} Y_0 \tag{3}
\end{eqnarray}
In this last expression note that all factors are constant $U$ and $Y_0$, so you can write
$$
x_{n+1} = a_1(U,Y_0) \lambda_1^n + a_2(U,Y_0)\lambda_2^n
$$
where the numbers $a_1$ and $a_2$ just depend on $U$ and the initial conditions
A: Actually, there are many ways to prove it.
I think the most simple one consists in proving that the set of solutions is a vector space (a subspace of $\mathbb{R} ^\mathbb{N} $). That first point is quite straightforward given the linear properties of the equation $x_{n+2}=ax_{n+1}+bx_n$. This vector space is of dimension 2 because we see that a sequence is uniquely defined by its first two terms. 
Then you ought to find a basis of that vector space. Look at the corresponding characteristic polynomial $x^2-ax-b$ (that of your matrix) and find its roots (in your case the discriminant is strictly non negative so there are two). Then the sequences $(\lambda_i^n) _{n\geq 0}$ belong to the previously defined vector space. They are linearly independent and thus form a basis. Hence the result (which, in the general case, holds only for a non zero discriminant). 
A: Are you familiar with the diagonalization of a square matrix? The eigenvalues of a difference equation are just the eigenvalues of the corresponding matrix.
