From a textbook:
A real sequence ($x_n$) is said to be contractive if there exists a constant $C \in (0,1)$ such that $\lvert x_{n+2} - x_{n+1} \rvert \le C\lvert x_{n+1} - x_{n} \rvert$ for all $n \ge 1$. Show that contractive sequences are necessarily Cauchy.
The proof for the property is as follows:
Note that $$\lvert x_{n+1} - x_{n} \rvert \le C\lvert x_{n} - x_{n-1} \rvert \le C^2\lvert x_{n-1} - x_{n-2} \rvert \le ... \le C^n\lvert x_{2} - x_{1} \rvert.$$
Hence if $m>n$, $$\lvert x_{n} - x_{m} \rvert \le \lvert x_{n} - x_{n+1} \rvert + \lvert x_{n+1} - x_{n+2} \rvert + ...+\lvert x_{m-1} - x_{m} \rvert,$$
from which it follows that
$$\le C^{n-1} \lvert x_2 - x_1 \rvert + C^{n} \lvert x_2 - x_1 \rvert + C^{n+1} \lvert x_2 - x_1 \rvert + ... + C^{m-2} \lvert x_2 - x_1 \rvert,$$
and therefore
$$\le \frac{C^{n-1}}{1-C} \lvert x_2 - x_1 \rvert.$$
Now take $\epsilon > 0$ and let $N$ be such that $\frac{C^{n-1}}{1-C} \lvert x_2 - x_1 \rvert < \epsilon$ for all $n$ (such $N$ exists since $C<1$ so that $C^n \to 0$). Then $\lvert x_m - x_n \rvert < \epsilon$ for all $n,m \ge N$ showing that ($x_n$) is Cauchy.
Q.E.D.
I am confused unfortunately in three main places. I'll enumerate where I get lost.
- From problem to statement 1: Why start at $\lvert x_{n+1} - x_{n} \rvert$ instead of $\lvert x_{n+2} - x_{n+1} \rvert$?
- From statement 1 to 2: That's just the triangle inequality, expanding that difference.
- From statement 2 to 3: I can see why $\lvert x_2 - x_1 \rvert \ge \lvert x_m - x_n \rvert$ $\forall n$, but where is this $C^{n-1}, C^n, C^{n+1},...,C^{m-2}$ coming from? And why end at $m-2$ and start at $n+1$?
- From statement 3 to 4: I think? I see why $C^{n-1} \ge C^{n-1}, C^n, C^{n+1},...,C^{m-2}$ but now why are we dividing by this $1-C$?
- From statement 4 to 5: This is just standard convergence theorem stuff, I understand, if all these inequalities hold, that if I make my $\epsilon$ larger than this then obviously I will converge.
I think my main concern here is point 3, but it's best to understand the whole proof anyways.
Thanks in advance!
Much of the confusion arises from confusion over indexes, I think.
re 1: You start with the difference $|x_{n+1}-x_{n}|$, since this will show you that the difference between the $n+1$th term and the $n$th term is at least $C^n$ times the difference between the second and the first term of the sequence. This property is a lemma that you can apply later in the proof.
The property of contractivity is expressed the way it is to take into account that the sequence starts at $x_1$. The property could have been written as
$|x_{n+1} - x_{n}| \leq C |x_{n} - x_{n-1}|$ for all $n \geq 2$
but all the property says is that the distance between any two subsequent terms is at least $C$ times the distance the terms in the previous step of the sequence.
re 3: Here is where you make use of the property that was established in the first line, namely that
$|x_{n+1} - x_{n}| \leq C^n |x_2 - x_1|$
This holds for any index $n$, so you can use it with index $n-1$ to get that
$|x_{n} - x_{n-1}| \leq C^{n-1} |x_2 - x_1|$
– and likewise for indexes $n-2$ and all the way down to $m-2$ (remember: $x_{m-1} = x_{m-2+1}$).
re 4: We know that $C \in [0;1]$ so dividing by $1-C$ will produce a larger value. In other words,
$C^{n-1} |x_2 - x_1| \leq \frac{C^{n-1}}{1-C} |x_2 - x_1|$