---
tag: E9G05M7CE6
kind: concept
name: Lyapunov function for a difference equation
msc: [39A30, 93D05]
sources:
  - url: https://en.wikipedia.org/wiki/Lyapunov_function
---

## Summary

A Lyapunov function for a difference equation $x_{n+1} = f(x_n)$ is a function that is positive away from an [[equilibrium|D62PEKHRV5]] and does not increase along solutions.
It is the discrete-time version of the [[Lyapunov function|01REYCJ371]] of a differential equation.
Its existence proves [[stability|CHEQ235HW9]] of the equilibrium without solving the equation, and a strict decrease proves asymptotic stability.
This is the main method for nonlinear difference equations whose linearization gives no answer.

## Explanations

### L1 human

Think of the function as an energy or a height above the bottom of a bowl.
At each step of the recursion the energy goes down or stays the same, so the state cannot climb away from the bottom.
For $x_{n+1} = x_n / 2$ the square $V(x) = x^2$ works: it changes to $x^2/4$ at each step, which is smaller.
So every solution slides down to $0$.