I've got a question concerning some weird kind of Lipschitz constant function, but it's an introduction course in Mathematics, so Lipschitz continuity isn't part of the course (to my knowledge). Here's the question:


Let $f:\mathbb{R}\rightarrow\mathbb{R}$ be a function and $a\in\mathbb{R}$. Define the sequence $(x_n)_{n\geq 0}$ by $x_0=a$ and for $n\geq 0, x_{n+1}=f(x_n)$.

Assume now that the function $f(x)$ has the following property: There is a constant $L\in(0,1)$ such that for all $x,y\in\mathbb{R}$ that following holds: $|f(x)-f(y)|\leq L|x-y|$.

Already Shown / Proven $$|x_{k+1}-x_k|\leq L^k|x_1-x_0|$$ For all $n>m\geq 0$ the following holds: $$|x_n-x_m|\leq\sum_{k=m}^{n-1}L^k|x_1-x_0|$$

The sequence $(x_n)_{n\geq 0}$ is convergent (by Cauchy).


Show that $z$ defined by $z=\lim_{n\to\infty}x_n$ is the unique solution of the equation: $$x=f(x)$$

(So to prove: there is a solution, and there is at maximum one solution)

How far i've come

I don't really know what to do except write the following: $$z=\lim_{n\to\infty}x_n=\lim_{n\to\infty}f(x_{n-1})$$ Or: $$f(z)=f(\lim_{n\to\infty}x_n)=\lim_{n\to\infty}x_{n+1}??$$

I don't even know if this is correct. I just need a little push to get going.


2 Answers 2


This is known as the Banach fixed-point theorem. There is a solution to $f(x)=x$, namely $\lim_{n\to\infty}x_n$, since $$f(x) = f\left(\lim_{n\to\infty} x_n\right) = \lim_{n\to\infty}f(x_n)=\lim_{n\to\infty} x_{n+1} = x, $$ where continuity of $f$ justifies the interchange of limit. Now suppose $x'$ satisfies $f(x')=x'$. Then $$0 \leqslant |x'-x| = |f(x')-f(x)|\leqslant L|x'-x|. $$ Since $0<L<1$, this implies that $|x'-x|=0$, and hence $x'=x$, which means that the solution is unique.


There are a few things to do in this problem:

  1. Show that there is a $z$ with $f(z) = z$
  2. Show that this $z$ is unique
  3. Show that the function converges
  4. Show that the function must converge to such a $z$


First we show that such a $z$ exists. Take $b = f(0)$. There are three cases. Either $b = 0$, $b < 0$ or $b > 0$. If $b = 0$, we are done. Otherwise, look at the function $g(x) = f(x) - x$ (I'm assuming $b$ is positive for simplicity, the exact same argument and $g$ works for $b$ negative). Note that for $z$ such that $f(z) = z$, we have $g(z) = 0$. We know that $g(0) = b$, and we have: $$ g(b/(1-L)) = f(b/(1-L)) - b/(1-L)\\ = \big(f(b/(1-L)) - f(0)\big) + b - b/(1-L)\\ \leq |f(b/(1-L)) - f(0)| + b - b/(1-L) \\ \leq L|b/(1-L) - 0| + b - b/(1-L)\\ \leq L\frac{b}{1-L} + b - \frac{b}{1-L}\\ = \frac{bL + b(1-L) - b}{1-L} = 0 $$ which means that either $g(b/(1-L)) = 0$, and we have our $z$, or we have $g(b/(1-L)) < 0$, which means that $g$ changes from positive to negative between $0$ and $b/(1-L)$, so by the intermediate value theorem. Either way, we've proven the existence of $z$.


As for why there is a unique $z$ with $f(z)=z$, assume there are two such points $z_1,z_2$. Then $|f(z_1)-f(z_2)|=|z_1-z_2| > L|z_1 - z_2|$, which is not allowed.


You've proven that the sequence is Cauchy, so it does converge to some value.


Assume the limit is some number $y$ with $f(y)\neq y$, let's say $|f(y) - y| = \delta$. By definition of limit of a sequence, there is an $N \in \Bbb N$ such that for each $n> N$, we have $|y-x_n| < \delta/2$, say. This implies that $|y - x_{n+1}| = |y - f(x_n)| < \delta/2$. But we have $|f(y_n) - f(x_n)| < L\delta/2$. Therefore $$ |y - f(x_n)| + |f(x_n) - y| < \frac\delta2 + L\frac\delta2 < \delta = |y - f(y)| $$ which violates the triangle inequality. Such a $y$ can therefore not be the limit of the sequence. That leaves the $z$ from above as the only available limit value, and since you know the limit exists, we are done.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .