Lyapunov function for a difference equation

Remarks

Example: for $f(x) = x / (1 + x^2)$ on $\R$ with $x^* = 0$, take $V(x) = x^2$. Then $V(0) = 0$, $V(x) > 0$ for $x \ne 0$, and $\Delta V(x) = x^2 \left( (1 + x^2)^{-2} - 1 \right) < 0$ for $x \ne 0$, so $V$ is a strict Lyapunov function.

Non-example: for $f(x) = 2x$ and $V(x) = x^2$, clauses 1 and 2 hold but $\Delta V(x) = 3x^2 > 0$ for $x \ne 0$, so clause 3 fails.

The quantity $\Delta V$ is the forward difference of $V$ along solutions, the analogue of the derivative $\dot V$ along solutions of a differential equation. If a Lyapunov function exists, the equilibrium is stable; if a strict one exists, it is asymptotically stable. For a linear map $f(x) = Ax$ one often uses a quadratic form $V(x) = x^T P x$ with $P$ positive definite and $A^T P A - P$ negative definite.