Asymptotic stability of linear recurrences

Remarks

Every solution is a finite sum of terms $p(n) \lambda^n$, where $\lambda$ is a root of $\chi$ and $p$ is a polynomial of degree less than the multiplicity of $\lambda$. If all roots satisfy $\abs{\lambda} < 1$, each such term tends to $0$, because $\abs{\lambda}^n$ decays faster than any polynomial grows. If some root has $\abs{\lambda} \ge 1$, then $x_n = \lambda^n$ is a solution that does not tend to $0$. For example, $x_{n+2} = x_{n+1} - \tfrac{1}{2} x_n$ has characteristic polynomial $z^2 - z + \tfrac{1}{2}$ with roots of modulus $1/\sqrt{2}$, so all its solutions tend to $0$. In contrast, $x_{n+2} = x_n$ has roots $\pm 1$ on the unit circle, and its solution $x_n = 1$ stays bounded but does not tend to $0$. Suppose all roots satisfy $\abs{\lambda} \le 1$, some root lies on the unit circle, and the roots on the circle are simple. Then the zero solution is stable but not asymptotically stable.

Going deeper

For a student

The result is the discrete counterpart of the fact that $x' = Ax$ is asymptotically stable exactly when all eigenvalues of $A$ have negative real part. Writing the recurrence as $X_{n+1} = C X_n$ with the companion matrix $C$, the condition says that the spectral radius of $C$ is less than $1$. In practice one does not compute the roots; tests such as the Jury stability criterion decide Schur stability from the coefficients alone. The same criterion governs the local stability of a fixed point of a nonlinear map through its linearization.