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.
 A: 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$.
A: 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.
