# Let $0 \leq \alpha < 1$ and let f be a function from $\mathbb{R}$ into $\mathbb{R}$ which satisfies…

Let $0 \leq \alpha < 1$ and let f be a function from $\mathbb{R}$ into $\mathbb{R}$ which satisfies $$| f(x) - f(y)| \leq \alpha|x-y| \; \forall x,y \in \mathbb{R}.$$ Let $a_{1} \in \mathbb{R}$ and let $a_{n+1} = f(a_{n})$ for $n=1,2....$ Prove that $\{a_{n}\}$is a Cauchy Sequence.

I have noticed that the sequence values are getting closer together but I haven't been able to show that they get arbitrarily close together. Also I know that if I can show that the sequence is bounded and monotone it is convergent and hence a Cauchy sequence by a theorem.

-
I'm afraid you forgot to use that $\,\alpha\,$ somewhere in your question, @Jmaff – DonAntonio Dec 27 '12 at 2:48
The same argument (in a more general setting) is used in the proof of Banach fixed-point theorm. – Martin Sleziak Dec 27 '12 at 9:20

$$|a_3-a_2|=|f(f(a_1))-f(a_1)|\leq\alpha|f(a_1)-a_1|$$

$$|a_4-a_3|=|f(f(a_2))-f(f(a_1))|\leq\alpha|f(a_2)-f(a_1)|=\alpha|a_3-a_2|\leq\alpha^2|f(a_1)-a_1|$$

Can you see the pattern?: $\,|a_n-a_{n-1}|\leq\alpha^{n-2}|f(a_1)-a_1|\,$

Well, now:

1) Evaluate $\,|a_n-a_m|\,$

2) Use the fact that $\,q^n\xrightarrow [n\to\infty]{}0\,$ whenever $\,|q|<1\,$

-

You can't generally show that the sequence will be monotone since it's not true. Once you show that the sequence is Cauchy it follows by the completeness of $\mathbb R$ that it converges.

Here is a hint to showing that the sequence is Cauchy: for all $n>m$ holds that $|a_n-a_m|\le |a_n-a_{n-1}|+|a_{n-1}-a_{n-2}| + \cdots + |a_{m+1}-a_m|$. Apply the definition of $a_k$ and the condition on $f$ to simplify this inequality and obtain an upper bound on the LHS.

Note: This is a step towards proving that $f$ has a unique fixed point. This result, known as Banach's fixed points theorem, holds in the much more general case of a contracting self map $f$ on a complete metric space.

-

A Cauchy sequence $\{a_n\}$ is one where for any $\varepsilon>0$ there exists $N$ such that any $m,n>N$ satisfy $|a_n - a_m| < \varepsilon$.

Let's try to give a bound on $|a_n-a_m|$. Start by substituting what we know: $|a_n-a_m| = |f(a_{n-1})-f(a_{m-1})| \le \alpha |a_{n-1}-a_{m-1}|$. Also, assuming WLOG that $n>m$, $|a_n-a_m| = |(a_n-a_{n-1})+(a_{n-1}-a_{n-2})+\ldots+(a_{m+1}-a_m)|$, which, by the triangle inequality, is at most $|a_n-a_{n-1}|+|a_{n-1}-a_{n-2}|+\ldots+|a_{m+1}-a_m|$

From here, the result follows from some induction, the fact that $\alpha^n\to0$, and the finiteness of the sum of geometric series.

-
... for any \epsilon >0 .... However, the induction you allude to will give that the expression to bound is bounded by something like \alpha^k*|a_n-a_0| (assuming n>m) which doesn't get you much farther. – Ittay Weiss Dec 27 '12 at 3:05
I wanted to leave the interesting (and standard, I think) part to the asker. I will mend my answer in light of your answer and comment. – Alfonso Fernandez Dec 27 '12 at 4:40