What are the eigenvectors of a recurrence relation?

Question

I'm struggling to understand what the eigenvectors of a recurrence relation actually are. Can someone define them in an easy way to understand? Thanks in advance

Edit: forgot to mention, I'm interested in linear recurrence relations of first and second order, both homogeneous and not homogeneous,but particularly the homogeneous ones

Answer 1

A homogeneous linear recurrence relation of arbitrary order turns out to have solutions which are of the form $a_n=\sum_i p_i(n)\lambda_i^n$,

where the $\lambda_i$ are roots of an associated polynomial (which becomes the characteristic polynomial of the associated matrix, so the $\lambda_i$ are eigenvalues of the matrix)

and the $p_i(n)$ are polynomials of order one less than the multiplicity of the associated eigenvalues. So for multiplicity $1$, the $p_i$ are constant. The coefficients of the $p_i$ depend on the initial values.

The eigenvectors of the matrix correspond with the eigenvalues and are associated with solutions of the form $a_n=A\lambda_i^n$

so, for example, $$M\binom {a_n}{a_{n-1}}=\lambda \binom {a_n}{a_{n-1}}=\binom {a_{n+1}}{a_{n}}$$ means that $a_{n+1}=\lambda a_n=\lambda^2 a_{n-1}$

In the general case we add terms associated with different eigenvalues using the linearity properties.