# Bound on Distance Between Iterates of Lipschitz Function at a Point

Let $$f:\mathbb{R}^d\rightarrow \mathbb{R}^d$$ be a $$L$$-Lipschtiz continuous function and for every positive integer $$n$$ define $$x^n = f(x^{n-1}) \mbox{ and } x^0=x,$$ for some fixed $$x \in \mathbb{R}^d$$. Then for $$n, positive integers, is there a (reasonable) bound on $$\|x^n-x^m\| ,$$ as a function of $$L$$, $$n$$, and $$m$$?

• Hint: telescopic series $x^n-x^m=(x^n-x^{n+1})+(x^{n+1}-x^{n+2})+\cdots+(x^{m-1}-x^m)$ – Questioner Feb 19 at 14:44

Hint: telescopic series $$x^n-x^m=(x^n-x^{n+1})+(x^{n+1}-x^{n+2})+\cdots+(x^{m-1}-x^m)$$ gives you $$\Vert x^n-x^m\Vert\leq\sum_{i=n}^{m-1}L^i\Vert x-x^1\Vert=\frac{L^n-L^m}{1-L}\Vert x-x^1\Vert.$$
This bound is tight for $$f(x)=Lx$$, $$x^0=1$$
• Is there a reasonable lower-bound depending on $n,m$ (non-constantly)? – AIM_BLB Feb 19 at 17:42
• @AIM_BLB Not really. A constant function is $L$-Lipschitz but $\Vert x^n-x^m\Vert=0$ for $n,m\geq 1$. – Questioner Feb 19 at 17:58