# Question about sequences

Let $f: \mathbb{R} \rightarrow \mathbb{R}$ and suppose there exists $K \in \mathbb{R}$ with $0 \leq K <1$ such that for all $x,y \in \mathbb{R}$ with $x \neq y$. $$|f(x)-f(y)|<K|x-y|$$ and define the sequence $(x_n)$ by $$x_1=f(x_0), x_2=f(x_1),...,x_{n+1}=f(x_n)$$ Show that if m>0 and n>0 then $$|x_{n+m}-x_n|<\dfrac{1}{1-K}|x_{n+1}-x_n|$$

My Attempt
We are given a hint to use, that;
$$|x_{n+m}-x_n|\leq |x_{n+m}-x_{n+m-1}|+...+|x_{n+2}-x_{n+1}|+|x_{n+1}-x_n|$$
I am struggling on how to use this to prove the above inequality.
I tried using the inequality to get this;
$$|x_{n+m}-x_n|\leq |x_{n+m}-x_{n+m-1}|+...+|x_{n+2}-x_{n+1}|+|x_{n+1}-x_n|<\dfrac{1}{K}|f(x_{n+m})-f(x_{n+m-1})|+...+\dfrac{1}{K}|x_{n+2}-f(x_{n+1})|+\dfrac{1}{K}|f(x_{n+1})-f(x_n)|=\dfrac{1}{K}(|x_{n+m+1}-x_{n+m}|+...+|x_{n+3}-x_{n+2}|+|x_{n+2}-x_{n+1}|)$$..
but I still don't seem to be an closer to what I want, any hints would be much appreciated.

-
Dont go upward. Comeback backward :) $\\$ Continue this again and again, and again : $|x_{n+m}-x_{n+m-1}|=|f(x_{n+m-1})-f(x_{n+m-2})|\leq K|x_{n+m-1}-x_{n+m-2}|$ – Fardad Pouran May 25 '14 at 9:47
This problem is part of the famous Banach's contraction principle <en.wikipedia.org/wiki/Banach_fixed-point_theorem>;. In fact, this is the part were we need to prove that the given sequence is a Cauchy sequence. – Emin May 25 '14 at 9:59

## 3 Answers

Hint: Fix $n$ and prove by induction on $m$ that

$$|x_{n+m} - x_n| < (1 + K +K^2 + \cdots + K^m) |x_{n+1} - x_n|$$

Then use

$$1 + K + \cdots K^m = \frac{1- K^{m+1}}{1-K}\ .$$

-

Each term can be reduced as $$|x_{n+m} -x_{n+m-1}|< K |x_{n+m-1} -x_{n+m-2}| < \dots < K^m |x_{n+1}- x_{n}|$$ this way you will get $$|x_{n+m}-x_n| < \left( 1+ K + \dots K^m \right)|x_{n+1}-x_n| = \frac{1-K^{m+1}}{1-K} |x_{n+1}-x_n| < \frac 1 {1-K} |x_{n+1}-x_n|$$

-

First by induction we have

$$|x_{n+k}-x_{n+k-1}|\le K^{k-1}|x_{n+1}-x_n|$$ and then using the triangle inequality

$$|x_{n+m}-x_n|\le\sum_{k=1}^m|x_{n+k}-x_{n+k-1}|\le |x_{n+1}-x_n|\sum_{k=1}^mK^{k-1}\\= |x_{n+1}-x_n|\frac{1-K^m}{1-K}\le\frac{1}{1-K}|x_{n+1}-x_n|$$

-
You've been busy in the last $24$ hours! – amWhy May 25 '14 at 13:38