Prove $a_n$ is a Cauchy-sequence, with $a_0 \in \Bbb R$ and $a_{n+1}=f(a_n)$ Let $f: \Bbb R \to \Bbb R$ be a differentiable function with $m=sup${$|f'(x)||x \in \Bbb R$} $<1$.
Let $a_0 \in \Bbb R$ and define $a_{n+1} =f(a_n)$ for $n=0,1,2...$. Prove the sequence $(a_n)_{n \geq 0}$ is a Cauchy sequence.
So we have to prove that $\forall \epsilon >0 ,\exists N \in \Bbb N$ such that when $n,m >N$ then $d(a_n,a_m) < \epsilon$, but I don't really know how to continue from here.
 A: You know that $|a_2-a_1|=\bigl|f(a_1)-f(a_0)\bigr|<m|a_1-a_0|$, by the mean value theorem. For the same reason, $|a_3-a_2|<m^2|a_1-a_0|$, $|a_4-a_3|<m^3|a_1-a_0|$, and so on. So, if $p>q$,\begin{align*}|a_p-a_q|&=|a_p-a_{p-1}+a_{p-1}-a_{p-2}+\cdots-a_q|\\&\leqslant|a_p-a_{p-1}|+|a_{p-1}-a_{p-2}|+\cdots+|a_{q+1}-a_q|\\&<\bigl(m^{p-1}+m^{p-2}+\cdots+m^{q}\bigr)|a_1-a_0|\\&=m^q\frac{1-m^{p-q}}{1-m}|a_1-a_0|\\&<\frac{m^{q-1}}{1-m}|a_1-a_0|.\end{align*}Since $0\leqslant m<1$, the rest is easy.
A: Well, let $n,k\in\mathbb{N}$, with $k\geq n$.
Now, let $x,y\in\mathbb{R}$. Since $f$ is differentiable over $\mathbb{R}$, we have that, form the Mean Value Theorem, that there exists a $\xi\in(x,y)$ such that:
$$\begin{align*}f'(\xi)=&\frac{f(y)-f(x)}{y-x}\Rightarrow f(y)-f(x)=\\=&f'(\xi)(x-y)\Rightarrow|f(y)-f(x)|=\\=&|f'(\xi)||y-x|\leq m|y-x|\end{align*}$$
So, we have that:
$$|f(y)-f(x)|\leq m|y-x|$$
for every $x,y\in\mathbb{R}$. Then, we have:
$$|a_{n+1}-a_n|=|f(a_{n})-f(a_{n-1})|\leq m|a_{n}-a_{n-1}|=m|f(a_{n-1})-f(a_{n-2}))|\leq m^2|a_{n-1}-a_{n-2}|$$
By induction, it is easy to show that:
$$|a_k-a_n|\leq m^n|a_1-a_0|$$
Now, we have:
$$\begin{align*}|a_k-a_n|=&|a_k-a_{k-1}+a_{k-1}-\dots-a_{n+1}+a_{n+1}-a_n|\leq\\
\leq&|a_k-a_{k-1}|+\dots+|a_{n+1}-a_n|\leq\\
\leq&m^{k-1}+\dots+m^n=\\
=&m^n\left(m^{k-1-n}+\dots+m+1\right)=\\
=&m^{n}\left(\frac{1-m^{k-n}}{1-m}\right)\leq\\
\leq&m^n\frac{1}{1-m}\overset{n\to\infty}{\longrightarrow}0
\end{align*}$$
So, the requested follows.
Note: This is in general a really important theorem in Numerical Analysis.
