Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
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

3 Answers 3

up vote 3 down vote accepted

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

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer
1  
... 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
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. –  Alfonso Fernandez Dec 27 '12 at 4:40

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.