# Differences, geometric sequences and convergence - $|x_{n+1} - x_n| \leq ac^n \implies \exists\ L : x_n \to L$

I've got a lingering question from a midterm in real analysis that I'd really like to have answered. The first time I answered the question, I received a 2/10 for absolutely mangling the definition of convergence. (By my logic, $\frac{1}{n}, \sqrt{n}$ converged.) I re-did the problem for what amounted to karma, and got a 4/10. A formal statement of what I'm trying to prove is, given a sequence $x_n$ of real numbers: $$\exists\ a > 0 \land c \in (0, 1) : \forall\ n \geq 1, |x_{n+1} - x_n| \leq ac^n \implies \exists\ L : x_n \to L$$

Essentially, we are given a sequence $x_n$ in the real numbers where the difference of consecutive terms $|x_{n+1} - x_n|$ was always less than the appropriate term in some geometric sequence, $ac^n$. We were told to prove that this sequence was pre-convergent, where pre-convergence was defined as: $$\forall\ \varepsilon > 0, \exists\ N \in \Bbb N : n \geq N \implies |a_n - a_N| < \varepsilon$$ I tackled the problem first by proving that the set of pre-convergent sequences is equivalent to the set of Cauchy sequences (and thus convergent in complete sets). Then, I noted that $\forall\ r \in \Re, 0 \leq |r|$, so I constructed the sequences $z_n = 0$ where the following held: $$z_n \leq |x_{n+1}-x_n| \leq ac^n$$ By applying the Squeeze theorem, it was easy to show that the sequence of differences converged to zero, but I have no idea where to go from there...

Can anyone shed some definite light on this?

-
Try to show that $(x_n)$ is Cauchy, using the formula for the geometric series. Try to expand $|x_n-x_N|=|(x_n-x_{n-1})+(x_{n-1}-x_{n-2})+\dots+(x_{N+1}-x_N)|$ –  Stefan Dec 13 '12 at 0:32
Dont overdo "logical" notation. May interfere with understanding. The $\exists x_n\in \Re$ makes no sense here. –  André Nicolas Dec 13 '12 at 2:46
I suppose not... –  Sean Allred Dec 13 '12 at 3:58

The idea is to use geometric series. Namely, $$|x_M-x_N|=\left|\sum_{n=N+1}^M x_n-x_{n-1}\right|\leq\sum_{n=N+1}^M |x_n-x_{n-1}|\leq\sum_{n=N+1}^M ac^n=\frac{ac^{N+1}-ac^M}{1-c}\leq\frac{ac^{N+1}}{1-c}.$$ As $c\in(0,1)$, the right hand side goes to zero when $N\to\infty$. Now, given $\varepsilon>0$, you can choose $N$ appropriately to show that the sequence is Cauchy (or pre-convergent).

-

Let $n\gt m$. We have $$|x_m-x_n|=(x_m-x_{m+1})+(x_{m+1}-x_{m+2}) +\cdots +(x_{n-1}-x_n).$$ By the Triangle Inequality, it follows that $$|x_m-x_n|\le |x_m-x_{m+1}|+|x_{m+1}-x_{m+2}| +\cdots +|x_{n-1}-x_n|.$$ By our assumption, $$|x_m-x_n|\le ac^m +ac^{m+1}+\cdots +ac^{n-1}.$$ The expression on the right is less than the sum of the infinite geometric series $ac^m+ac^{m+1}+\cdots$.

That sum is $c^m \dfrac{a}{1-c}$. It goes to $0$ as $m\to\infty$, so our sequence $(x_n)$ is a Cauchy sequence, and therefore converges.

-
(Sorry for my late responses; I've been trying to sort through each of these answers to the best of my ability.) So then what's left to do is to provide an $N$ for some $\varepsilon > 0$ where these things hold true? –  Sean Allred Dec 13 '12 at 1:13
If you are expected to. For me, no need, you nust have among earlier theorems that $\lim c^n=0$ if $|c|\lt 1$. If you don't, can use $m\gt (1/\log c)\log(\epsilon(1-c)/a)$. –  André Nicolas Dec 13 '12 at 2:18
So, since the finite sum can be made as small as we want (since it $\to 0$), we may as well call that sum $\varepsilon$ - and the rest is simply the definition of Cauchy. Am I understanding this? –  Sean Allred Dec 13 '12 at 4:16
I think we can be casual, and say that $ac^m/(1-c)$ has limit $0$. But for strict application of Cauchy Criterion, we are at the beginning given an $\epsilon$. So we have to use something like what I suggested in a comment. By the way, that probably has a mistake, sort of. If the thing inside the log is $\ge 1$ (which is only for silly big $\epsilon$) we may need to add something to the effect we also want $m\ge 1$. –  André Nicolas Dec 13 '12 at 4:25