Bound on Distance Between Iterates of Lipschitz Function at a Point

Question

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<m$, positive integers, is there a (reasonable) bound on $$ \|x^n-x^m\| , $$ as a function of $L$, $n$, and $m$?

Answer 1

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$