Showing a sequence is Cauchy Let $f(x)$ be a function which is diﬀerentiable on $\mathbb{R}$ and for which $a = \sup\{|f
′(x)| : x ∈ \mathbb{R}\}$ is less than 1. Let $x_{0}$ be any ﬁxed real number.
(a) Show that the sequence ${x_{i}}$ deﬁned by $x_{i+1} = f(x_{i})$ for $i ≥ 0$
is a Cauchy sequence, hence convergent.
(b) Show that $f(x)$ has a fixed point.
I really wish I had an attempt to show you guys, but I don't lol. I'm very lost with this question.
I know that to be Cauchy the terms in a sequence have to be arbitrarily close together. How can I show this given the above information?
 A: Hint:


*

*For any two different points $x,y\in\mathbb{R}$, we have
$$\big|\frac{f(x) - f(y)}{x-y}\big|< 1,$$
or $|f(x) - f(y)| < |x-y|.$ Else, you could get a contradiction using mean value theorem that there exists point $c$ in the interval say $(x,y)$ such that $1 > |f'(c)| = \big|\frac{f(x) - f(y)}{x-y}\big| \geq 1$.

*And since $a = \sup\{|f'(x)|\} < 1$, the above statement can be strengthened to 
$$\big|\frac{f(x) - f(y)}{x-y}\big|\leq a,$$
or
$$|f(x) - f(y)| \leq a|x-y|.$$

*$|f(f(x)) - f(f(y))| \leq a|f(x) - f(y)| \leq a^2|x-y|.$
A: (a) Note that by induction plus the Mean Value Theorem 
$$|x_{k+1} - x_k| \leq a^{k}|x_1-x_0|$$
for all $k \in \mathbb{N}$. 
(More Detail: Key to inductive step: $|x_{k+2} - x_{k+1}| = |f(x_{k+1}) - f(x_k)| \leq a|x_{k+1} - x_k|$, by the MVT.) 
Hence for any $m>n$ in $\mathbb{N}$ we have that 
$$|x_m - x_n| \leq |x_m- x_{m-1}| + \cdots + |x_{n+1}-x_n| $$
$$ \leq a^{m-1}|x_{1} - x_{0}| + \cdots +a^n|x_1-x_0|$$
$$ = a^n|x_1-x_0|\sum_{k=0}^{m-n-1}a^k$$
$$\leq a^n|x_1-x_0|\sum_{k=0}^{\infty}a^k $$
$$ = a^n|x_1-x_0| \dfrac{a}{1-a},$$
from which the Cauchy property follows easily (because $a^n \rightarrow 0$ as $n \rightarrow \infty$, independently of $m$; and the remaining terms in the final product are constant).
(b) We now know that $\lim_{n \rightarrow \infty} x_n$ exists and we denote this limit by $x$. Taking limits in the equation $x_{n+1} = f(x_n)$ and using the continuity of $f$ shows that $f(x) = x$. 
