Cauchy sequences

## Cauchy sequences
            ---
            ## Cauchy sequences
            A sequence $(a_n)\_{n=1}^\infty$ is *Cauchy* if

for all $\varepsilon>0$,   $\exists k\in\mathbb N$ such that $m,n>k \implies$ $\lvert a_n-a_m \rvert < \varepsilon$.

Informally, we think of a sequence being Cauchy meaning "the terms of the sequence get closer and closer to one another".
            But we need a more precise understanding for this course.

Note: there is no concept of limit in this definition (yet!).
 
 ---
 ## Cauchy sequences
 #### Definition
 A sequence $(a_n)\_{n=1}^\infty$ is *Cauchy* if

for all $\varepsilon>0$,   $\exists k\in\mathbb N$ such that $m,n>k \implies$ $\lvert a_n-a_m \rvert < \varepsilon$.

#### Or, in words,
 No matter how small we pick $\varepsilon>0$,

we can always go far enough (ie. $k$ far) down the sequence to ensure that

every term after that point (ie. after $k$),

is within $\varepsilon$ of every other term.
 #### How to prove Cauchyness
 Construct a machine (a function) that tells you $k$ for any given $\varepsilon$, and that $k$ does the job.
 
 ---
 ## Proof of Cauchyness: example 1
 #### Theorem
 Let $a_1=4$ and $a_2=14$, with $a_n = (a\_{n-1}+a\_{n-2})/2$.
 Then $(a_n)\_{n=1}^\infty$ is Cauchy.
 #### Definition
 A sequence $(a_n)\_{n=1}^\infty$ is *Cauchy* if

for all $\varepsilon>0$,   $\exists k\in\mathbb N$ such that $m,n \gt k \implies$ $\lvert a_n-a_m \rvert \lt \varepsilon$.

#### How to prove Cauchyness
 Construct a machine (a function) that tells you $k$ for any given $\varepsilon$, and that $k$ does the job.
 #### Proof
 For all $n\geqslant2$, $\lvert a\_{n+1}-a_n\rvert=\frac12\lvert a_n-a\_{n-1}\rvert$, so $\lvert a\_{n+1}-a_n\rvert=2\^{-(n-1)}\lvert a_2-a_1\rvert$.
 But also $a_1 \lt a_3 \lt a_5 \lt \ldots \lt a_6 \lt a_4 \lt a_2$.
 Fix any $\varepsilon>0$.
 Let $k=\lceil-\log_2(\frac\varepsilon{10})\rceil+1$.
 If $m,n>k$, then, we can assume $m\geqslant n$, so
 $\lvert a_m - a_n \rvert$ $\leqslant \lvert a\_{n+1}-a_n \rvert = 2\^{-(n-1)}\lvert a_2-a_1\rvert$ $\lt$ $2\^{-(k-1)}\times10 = 2\^{-\lceil-\log_2(\frac\varepsilon{10})\rceil}\times10 \leqslant 2\^{\log_2(\frac\varepsilon{10})}\times10 =$ $\varepsilon$.   □

Note:
            We can't use monotone convergence here, because the sequence is neither increasing nor decreasing.

It has increasing and decreasing subsequences (even and odd indexed terms) but the whole sequence is neither.
 
 ---
 ## Proof of Cauchyness: example 2
 #### Theorem
 Let $s_n=\sum\_{k=1}^n \frac1k$.
 Then $(s_n)\_{n=1}^\infty$ is not Cauchy.
 #### Definition
 A sequence $(s_n)\_{n=1}^\infty$ is *Cauchy* if

Therefore:

A sequence $(s_n)\_{n=1}^\infty$ is **not** Cauchy if

there exists $\varepsilon>0$ such that,   $\forall k\in\mathbb N$, $m,n>k \\;\not\nobreak\\!\\!\\!\\!\implies$ $\lvert s_n-s_m \rvert < \varepsilon$.

#### How to prove not Cauchyness
 Pick an $\varepsilon$ as small as you need.
 Then construct a machine that tells you $m,n$ for any given $k$, with $m,n>k$, yet $\lvert s_n-s_m \rvert>\varepsilon$.
 
 ---
 ## Proof of Cauchyness: example 2
 #### Theorem
 Let $ s_n=\sum\_{k=1}^n \frac1k$.
 Then $(s_n)\_{n=1}^\infty$ is not Cauchy.
 #### Definition
 A sequence $(s_n)\_{n=1}^\infty$ is **not** Cauchy if

#### How to prove not Cauchyness
 Pick an $\varepsilon$ as small as you need.
 Then construct a machine that tells you $m,n$ for any given $k$, with $m,n>k$, yet $\lvert s_n-s_m \rvert>\varepsilon$.
 #### Proof
 Let $\varepsilon=\frac12$.
 For any $k\in\mathbb N$,
 let $n>k$ and $m=2n>k$.

Then
 $\lvert s_m - s_n \rvert$ $= \frac1{n+1}+\frac1{n+2}+\ldots+\frac1{2n}$ $>$ $\frac n{2n} = $ $\varepsilon$.   □
 
 ---
 ## Why do we care about Cauchyness?
 #### Theorem
 Every Cauchy sequence is convergent, and every convergent sequence is Cauchy.
 #### Proof
 See lecture notes.
 #### Application
 We can prove a sequence is convergent by (often easier) showing it is Cauchy.

We can prove a sequence is divergent by (often easier) showing it is not Cauchy.
            #### Examples
            The sequence $(a_n)\_{n=1}^\infty$ given by $a_1=4$ and $a_2=14$, with $a_n = (a\_{n-1}+a\_{n-2})/2$ for $n>2$ is convergent.

The sequence $(s_n)\_{n=1}^\infty$ given by $s_n=\sum\_{k=1}^n \frac1k$ is divergent.