1
$\begingroup$

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.

  • 0
    The same argument (in a more general setting) is used in the proof of [Banach fixed-point theorm](http://en.wikipedia.org/wiki/Banach_fixed-point_theorem).2012-12-27

3 Answers 3

3

$|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\,$

2

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.

1

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.

  • 1
    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.2012-12-27