General formula for linear difference equations

Question

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?

Answer 1

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

Answer 2

Are you familiar with the diagonalization of a square matrix? The eigenvalues of a difference equation are just the eigenvalues of the corresponding matrix.

Answer 3

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