# Proof review: cauchy sequences

Problem statement:

a) Let $(s_n)$ be a sequence such that $\mid s_{n+1} - s_{n} \mid < 2^{-n}$ for all $n \in \mathbb{N}$. Prove that $(s_n)$ is a Cauchy sequence and hence a convergent sequence.

b) Is the result in (a) treu if we only assume that $\mid s_{n+1} - s_{n} \mid < \frac{1}{n}$ for all $n \in \mathbb{N}$?

My proof for (a):

Take any $\epsilon > 0$. Let $N = \log_2{2/\epsilon}$. Take $m, n > N$. Without loss of generality, we may take $m > n$. Let $\delta = m-n$.

$\mid s_{n+1} - s_{n} \mid < \frac{1}{2^n}$

$\mid s_{n+2} - s_{n+1} \mid < \frac{1}{2^{n+1}}$

...

$\mid s_{n+\delta} - s_{n+\delta-1} \mid < \displaystyle{\frac{1}{2^{n+\delta-1}}}$

Adding up the inequalities and using the triangle inequality:

$\mid s_{n+\delta} - s_n \mid = \mid s_{m} - s_{n} \mid < \displaystyle{\frac{1}{2^{n}} + \frac{1}{2^{n+1}} ... \frac{1}{2^{n+\delta-1}}}$

Using the geometric series sum formula:

$\displaystyle{\frac{1}{2^{n}} + \frac{1}{2^{n+1}} ... \frac{1}{2^{n+\delta-1}}} = \frac{1}{2^{n-1}} - \frac{1}{2^{n+\delta-1}} < \frac{1}{2^{n-1}} - \frac{1}{2^n} < \frac{1}{2^n-1} < \frac{1}{2^{N-1}} = \epsilon$

Therefore,

$\mid s_m - s_n \mid < \epsilon$.

For (b), it doesn't work because the argument is that $\sigma \frac{1}{n}$ does not converge, but I'm not sure how to flesh that out.

-
For b) take the partial sums of the harmonic series, i.e., $s_{n+1}=s_n+\frac1n$. –  LutzL Feb 23 '14 at 3:10
Would the answer still be a "no"? The issue is that the book does not introduce series yet, so I assume I cannot use them for the proof. –  Dhaivat Pandya Feb 23 '14 at 3:11
Do you know that $1+x\le e^x$? Then $\ln(1+\tfrac1n)\le\tfrac1n$, that is, with $s_n=\ln(n)$ you also get the estimate of b) for a diverging sequence. –  LutzL Feb 23 '14 at 3:17

For part (b), try this counter-example: $$s_n = \sum_{k=1}^{n} \frac{1}{n}.$$ Then $$|s_{n+1} - s_{n}| = \frac{1}{n+1} < \frac{1}{n},$$ but $s_n \to \infty$.
The fact that $s_n \to \infty$ is fairly well-known, so I would safely assume it. –  N-7 Feb 23 '14 at 3:16