Prove that $\lim_{n\to \infty} x_n = 0$ if $\lvert f(x) - f(y) \rvert \leq \frac{1}{2} \lvert x - y \rvert$ , $f(0) = 0$ and $x_n = f(x_{n-1})$

Question

Suppose $f: \mathbb{R} \to \mathbb{R}$ satisfies $\lvert f(x) - f(y) \rvert \leq \frac{1}{2} \lvert x - y \rvert$ for all $x,y \in \mathbb{R}$, and $f(0) = 0$. Let $x_0 \in \mathbb{R} $ be arbitrary. Define $x_1 = f(x_0)$, $x_2 = f(x_1)$, etc. so that $x_n = f(x_{n-1})$ for all $n\in \mathbb{Z^+}$. Prove that $\lim_{n\to \infty} x_n = 0$.

I am aware that one of this means that the function $f$ is Lipschitz which implies that it is uniformly continuous.

This is my attempt at the proof: Suppose $\varepsilon > 0$. We have $$\lvert x_n - 0 \rvert = \lvert f(x_{n-1}) - f(0) \rvert \leq \frac{1}{2} \lvert x_{n-1} \rvert. $$

From uniform continuity, we can choose $\delta >0$ such that $\lvert x - y \rvert < \delta$ implies that $\lvert f(x) - f(y) \rvert < \varepsilon$. I want to somehow use this information to find an $N\in \mathbb{Z^+}$ such that $\vert x_n - 0 \rvert < \varepsilon$ whenever $n\geq N$ but I'm stuck on how to finish.

Answer 1

Why not iterate what you have? $$|x_n| \leq \frac{1}{2}|x_{n-1}| \leq \frac{1}{2^2} |x_{n-2}| \leq \dots \leq \frac{1}{2^n} |x_0|$$ Note $\frac{1}{2^n} \to 0$ as $n \to \infty.$

Answer 2

This is more or less the proof of the Banach Fixed Point Theorem, but I'll include the argument here. Notice that $$\lvert x_{n+1} - x_{n} \rvert = \lvert f(x_{n}) - f(x_{n-1}) \rvert \le \frac 1 2 \lvert x_{n} - x_{n-1} \rvert $$ and since this holds for all $n \in \mathbb Z^+$, we can use induction to see that $$\lvert x_{n+1} - x_{n} \rvert \le \frac{1}{2^n} \lvert f(x_1) - f(x_0) \rvert = \frac C {2^n}$$ where $C = \lvert f(x_1) - f(x_0) \rvert$ is a constant. Now fix $N \in \mathbb Z^+$, And note that for $m > n > N$, \begin{align*} \lvert x_m - x_n\rvert &= \lvert (x_m - x_{m-1}) - (x_{m-1} - x_{m-2}) - \cdots - (x_{n+1} - x_n) \rvert \\ &\le \sum^{m-1}_{k=n} \lvert x_{k+1} - x_{k} \rvert\\ &\le \sum^{m-1}_{k=n} \frac{C}{2^k} \le \sum^\infty_{k=N} \frac{C}{2^k} = \frac{C(1/2)^N}{1-(1/2)} \to 0\,\,\,\, \text{ as } N\to \infty. \end{align*} This shows that $\{x_n\}$ is a Cauchy sequence and thus converges to some $x^* \in \mathbb R$. Now taking the limit on both sides of the equation and using continuity of $f$, we see that $$x_{n+1} = f(x_n) \,\,\,\,\, \implies \,\,\,\,\, x^* = f(x^*).$$ That is $x^*$ is a fixed point of $f$.

Now suppose that for $x,y \in \mathbb R$, $$f(x) = x \,\,\,\,\,\, \text{ and } \,\,\,\,\,\, f(y) = y.$$ Then $$0 \le \lvert x - y \rvert = \lvert f(x) - f(y) \rvert \le \frac 1 2 \lvert x - y \rvert$$ which shows that $\lvert x - y \rvert = 0$ so $x=y$. Thus $f$ has only one fixed point and so $f(x^*) = x^*$ implies that $x^* = 0$. Thus $x_{n}\to 0.$