Showing a sequence is Cauchy

Question

Let $f(x)$ be a function which is differentiable on $\mathbb{R}$ and for which $a = \sup\{|f ′(x)| : x ∈ \mathbb{R}\}$ is less than 1. Let $x_{0}$ be any fixed real number.

(a) Show that the sequence ${x_{i}}$ defined 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?

Answer 1

Hint:

1. 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$.

2. 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|.$$

3. $|f(f(x)) - f(f(y))| \leq a|f(x) - f(y)| \leq a^2|x-y|.$

Answer 2

(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$.