# Revisiting a problem on Cauchy sequences

I posted earlier this week Proving a sequence is Cauchy given some qualities about the sequence

I believe I solved the question myself, but my roommate has a different method of solving it, and is as follows. I want to know if this is, also, correct and proves that a sequence is Cauchy and that the limit exists.

Given $|x_2-x_1|=1$ and $|x_{n+1}-x_n|\leq \frac{4}{9}|x_n-x_{n-1}|$:

\begin{align} |x_m-x_n| & = |x_m-x_{m-1}+x_{m-1}+...+x_{n+1}-x_n| \\ & \leq |x_m-x_{m-1}|+...+|x_{n+1}-x_n| \\ & \leq |x_m-x_{m-1}|+...+|x_{n+1}-x_n|+...+|x_2-x_1|\\ & \leq \left(\left(\frac{4}{9}\right)^m+\left(\frac{4}{9}\right)^{m-1}+...+1\right)|x_2-x_1|\\ &\leq \frac{9}{5}\cdot 1\\ &\leq 2 \end{align}

So: Fix $\epsilon > 0$. Then for all $n,m>\frac{2}{\epsilon}$, $|x_m-x_n|<\epsilon$. And so the sequence is Cauchy and so it converges.

• ? You showed that $\lvert x_m-x_n\rvert\leq 2$, not $\epsilon$. – Nick Peterson Oct 24 '13 at 1:44
• I thought so, but where is the problem in the proof? Where we jump from the summation to m to the summation to infinity? Or where he adds the terms down to $|x_2-x_1|$? EDIT: Nevermind. Don't add all the extraneous terms, and factor out a $\left(\frac{4}{9}\right)^n$ – druckermanly Oct 24 '13 at 1:48
• I was just confused because I wrote a script in c++ that validated his weird claim of $\frac{2}{\epsilon}$ was correct... but then I just considered the fact that $$\frac{2}{\epsilon} > log_{\frac{4}{9}}\left(\frac{\epsilon}{2}\right)$$ – druckermanly Oct 24 '13 at 1:55

Resolution: the chain of inequalities is correct, but is ultimately unhelpful because $\le 2$ is not strong enough conclusion to obtain a limit. The leap to "if $m,n>2/\epsilon$ then $\dots <\epsilon$" is without any supporting evidence.
To obtain a useful bound on $|x_n-x_m|$ ($n<m$), one runs the summation only over the differences that are needed in the generalized triangle inequality: $|x_j-x_{j-1}|$ where $j=n+1,\dots,m$. The sum is bounded by a multiple of $(4/9)^n$.