Prove existence of unique fixed point

Let $f(x)$ be a strictly decreasing function on $\mathbb{R}$ with $|f(x)-f(y)|<|x-y|$ whenever $x\neq y$. Set $x_{n+1}=f(x_n)$. Show that the sequence $\{x_n\}$ converges to the root of $x=f(x)$.

Note that the condition is weaker than what is required in the contracting mapping principle.

Firstly, here's a picture of what's going on:

Formally, we start by observing that because $f$ is strictly decreasing and continuous, $f(x) = x$ must have a unique solution. Call this fixed point $r$; then defining \begin{align*} A &= \{x \in \mathbb{R} : x < r \} \\ B &= \{r\} \\ C &= \{x \in \mathbb{R} : x > r \}. \end{align*} we have \begin{align*} f(x) &> x \text{ for all } x \in A \\ f(r) &= r \\ f(x) &< x \text{ for all } x \in C. \end{align*}

We can say more:

• $\boldsymbol{f}$ maps $\boldsymbol{A}$ into $\boldsymbol{C}$ and vice versa: For $a \in A$, $f(a) > a$, so by decreasing $f(f(a)) < f(a)$. So $f(a) \in C$. Similarly for $C$.

• $\boldsymbol{f(f(x)) > x}$ on $\boldsymbol{A}$ and $\boldsymbol{f(f(x)) < x}$ on $\boldsymbol{C}$: For $a \in A$, $|f(f(a)) - f(a)| < |f(a) - a|$. So $f(f(a))$ is closer to $f(a)$ than $a$ is, and since $a, f(f(a)) \in A$ and $f(a) \in C$, "closer to $f(a)$" implies larger.

So now fix any $x_1 \in \mathbb{R}$. We may assume that $x_1 \in A$. By the above facts, it follows that $x_1, x_3, x_5, \ldots$ is an increasing sequence in $A$, and $x_2, x_4, x_6, \ldots$ is a decreasing sequence in $C$. It follows that both of them converge, say to $x$ and to $y$ respectively, where $x \le r \le y$. But by continuity, $f(x_{2k})$ must converge to the same thing as $f(x_{2k+1})$, so $x = y = r$, and therefore $x_n \to r$.

Uniqueness. If $x$ and $y$ are distinct fixed points then $0<|x-y|=|f(x)-f(y)|<|x-y|$. Contradiction.

Existence. $|f(x)-f(y)|<|x-y|$ implies that $f$ is continuous. If $f$ has not fixed point then i) $f(x)>x$ for all $x$ or ii) $f(x)<x$ for all $x$. If i) holds then for $x_0\in \mathbb{R}$, $x_1=f(x_0)>x_0$ and since $f$ is decreasing $x_2=f(x_1)<f(x_0)=x_1$. Hence if $h(x)=f(x)-x$ we have that $h(x_0)>0$ and $h(x_1)<0$ and by the IVT, we have a root of $h(x)=0$, i.e. a fixed point for $f$. The case ii) is similar.

Convergence of iterates. Let $z$ be the fixed point. And let $x_0\in\mathbb{R}$, then $$|x_n-z|=|f(x_{n-1})-z|<|x_{n-1}-z|<\dots<|x_{0}-z|$$ which means that $f$ send the compact $K=[z-|z-x_0|,z+|z-x_0|]$ in itself. Moreover $d_n=|x_n-z|$ is strictly decreasing, and admits a limit $r\geq 0$. Let $x_{n_k}$ be a subsequence which converges to some $y\in K$. If $y\not=z$ then $$r=|y-z|=\lim_{k\to\infty} d_{n_k}=\lim_{k\to\infty} d_{n_{k}+1}=\lim_{k\to\infty}|f(x_{n_k})-z| =|f(y)-z|=|f(y)-f(z)|<|y-z|$$ which is a contradiction. Therefore any convergent subsequence of $\{x_n\}_n$ has limit $z$, which, along with the compactness of $K$, implies that $\{x_n\}_n$ converges to $z$.

P.S. Once we have established the existence of the fixed point the decreasing hypothesis is not needed anymore.

Note:$f(x)=x-\arctan(x)+\pi/2$ is a strictly increasing function which is a weak contraction in $\mathbb{R}$, but it has no fixed points.