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$?

  • 2
    $\begingroup$ Hint: telescopic series $x^n-x^m=(x^n-x^{n+1})+(x^{n+1}-x^{n+2})+\cdots+(x^{m-1}-x^m)$ $\endgroup$ – 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$

  • $\begingroup$ Is there a reasonable lower-bound depending on $n,m$ (non-constantly)? $\endgroup$ – AIM_BLB Feb 19 at 17:42
  • $\begingroup$ @AIM_BLB Not really. A constant function is $L$-Lipschitz but $\Vert x^n-x^m\Vert=0$ for $n,m\geq 1$. $\endgroup$ – Questioner Feb 19 at 17:58
  • $\begingroup$ Fair but suppose non-constant (or else like you said its trivial) $\endgroup$ – AIM_BLB Feb 19 at 17:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.