Lesson 0009: Sequences

For any $m\in\Bbb N$ we define $\Bbb N^{\ge m} = \Bbb N \cap [m,\infty)$.
For any set $X$, a sequence of $X$ starting at $m$ is any function $a:\Bbb N^m\to X$ for any $m\in\Bbb N$.
The image of $k$ under $a$ is written $a(k)$, using standard function notation. However, for sequences, we prefer to write this instead as $a_k$, and we prefer to call this the $k$th term of the sequence.
Although the function is denoted by $a$, for sequences we prefer to denote it as $(a_k)_{k=m}$, where $m$ is the "starting index" of the sequence.
If $m,p\in\Bbb N$ and if $m\le p$, then we may restrict $(a_k)_{k=m}$ to the domain $N^{\ge p}$. We denote this restriction as $(a_k)_{k=p}$, and we call this the $p$th tail of $(a_k)_{k=m}$.
If $(i_k)_{k=p} : \Bbb N^{\ge p} \to \Bbb N^{\ge m}$ is a strictly increasing sequence of $\Bbb N^{\ge m}$, then the composition $(a_k)_{k=m} \circ (i_k)_{k=p}$ is also a sequence of $X$. In this case, we write this sequence as $(a_{i_k})_{k=p}$ and call this a subsequence of $(a_k)_{k=m}$.
If $a,b$ are elements in an ordered field, we define the absolute value of $a$ by $$ |a| = \begin{cases} a & \text{ if } 0\preceq a \\ -a & \text{ if } a\prec 0 \end{cases}$$ We define the distance between $a$ and $b$ by $|a-b|$.
For a given $\varepsilon\in F^{\ge 0}$, we say that $a$ is within $\varepsilon$ of $b$ if $|a-b|\prec \varepsilon$.
For a given sequence of $F$, say $(a_k)_{k=m}$, we say that $(a_k)_{k=m}$ is within $\varepsilon$ of $b$ if every term of $(a_k)_{k=m}$ is within $\varepsilon$ of $b$.
We say that $(a_k)_{k=m}$ is eventually within $\varepsilon$ of $b$ if some tail of $(a_k)_{k=m}$ is within $\varepsilon$ of $b$.
We say that $(a_k)_{k=m}$ converges to $b$ if for every $\varepsilon\in F^+$, eventually $(a_k)_{k=m}$ is within $\varepsilon$ of $b$. In this case we say that $b$ is the limit of $(a_k)_{k=m}$ and we write $$ \lim_{k\to\infty}a_k = b $$ or $$ a_k \to b $$ Note that this notation does not allow you to determine the starting index of the sequence. Implicitly, the starting index is 1, or the least natural number for which the sequence is defined.
Throughout this section, assume that $m,p,q\in\Bbb N$, and $(a_k)_{k=m}, (b_k)_{k=m}, (c_k)_{k=m}$ are sequences of $\Bbb R$. Also assume that $(i_k)_{k=p}:\Bbb N^{\ge p}\to \Bbb N^{\ge m}$ is a strictly increasing sequence of $\Bbb N^{\ge m}$.
Theorem: Seq. thousand steps
Positive steps become arbitrarily large.
Statement and proof. Statement: Let $x\in\Bbb R^+$ and $y\in\Bbb R$. Then there is an $n\in\Bbb N$ such that $y < nx$.

Proof: Define $S = \{n\in\Bbb N: nx < y \}$. If $S = \emptyset$ then $y < 1x$ and the theorem holds, so assume for the rest of the proof that $S\ne \emptyset$.
$S$ is then bounded above by $y/x$. Since $S$ is a nonempty set of integers, bounded above, then $\max(S)$ exists.
Therefore $\max(S)+1\notin S$ and therefore $y < (\max(S)+1)x$ by definition of $S$.
Therefore the $n$ required by the theorem is $\max(S)+1$.
$\Box$
Theorem: Seq. no infinitesimals
There are no real infinitesimals.
Statement and proof. Statement: Let $a\in\Bbb R^+$. Then there is an $n \in\Bbb R$ such that $\frac 1 n < a$.
An infinitesimal is a nonzero number smaller than every positive rational number. As a corrolary, of this theorem, there is no infinitesimal real number.

Proof: Let $a\in\Bbb R^+$. By the Seq. thousand steps theorem, there is an $n\in\Bbb N$ such that $1 < an$.
Therefore $\frac 1 n < a$.
$\Box$
Theorem: Seq. equiv. incr.
A sequence is increasing if and only if $a_{k} < a_{k+1}$ for each $m\le k$.
Statement and proof. If $(a_k)_{k=m}$ is increasing then it follows trivially that $a_k < a_{k+1}$ for each $m\le k$.
Assume that $a_k < a_{k+1}$ for every $m\le k$. Now let $m\le p < q$.
Then $$ a_p < a_{p+1} < \cdots < a_{q} $$ $\Box$
Theorem: Seq. one over n
$\frac 1 n \to 0$.
Statement and proof. Statement: $\lim_{n\to\infty} \frac 1 n = 0$.

Proof: Let $a_k = \frac 1 k$, and let $\varepsilon\in\Bbb R^+$. Let $n\in\Bbb N$ such that $ \frac 1 k < \varepsilon$. Then for every natural number $n\le p$ $$\begin{aligned} |a_p-0| & = \frac 1 p \\ &\le \frac 1 n \\ &<\varepsilon \end{aligned}$$ Therefore the $n$th tail is within $\varepsilon$ of 0, which implies $(a_k)_{k=1}$ is eventually within $\varepsilon$ of 0.
Since $\varepsilon\in\Bbb R^+$ was arbitrary, therefore $(a_k)_{k=1}$ is eventually within $\varepsilon$ of 0, for every $\varepsilon\in\Bbb R^+$.
By definition, therefore $$ \lim_{k\to\infty}\frac 1 k = 0 $$ $\Box$
Theorem: Seq. no bound no lim.
If $(a_k)_{k=m}$ has no upper bound then $\lim_{k\to\infty}a_k$ does not exist.
Statement and proof. Statement: Suppose $(a_k)_{k=m}$ is not bounded above. Then $\lim_{k\to\infty}a_k$ does not exist.

Proof: We prove the contrapositive, so assume that $\lim_{k\to\infty} a_k = L$ exists.
Set $\varepsilon=1$ and therefore $(a_k)_{k=m}$ is eventually within 1 of $L$. Therefore let the $p$th tail be within 1 of $L$.
Then $L+1\in UB_{\text{Im}(a_k)_{k=p}}$.
Let $\alpha=\max\{a_k: m\le k\le p\}$.
Then $\max\{\alpha,L+1\} \in UB_{\text{Im}(a_k)_{k=m}}$ which shows that $(a_k)_{k=m}$ is bounded above.
$\Box$
Theorem: Seq. tails are subseqs.
Every tail is a subsequence.
Statement and proof. Statement: Let $(a_k)_{k=m}$ be a sequence, and $m\le p$ a natural number. Then there is a subsequence of $(a_k)_{k=m}$ which is equal to the $p$th tail.

Proof: Define $(j_k)_{k=p}$ by $j_k = k$. Then $a_{j_k} = a_k$ on the domain $\Bbb N^{\ge p}$. Therefore $(a_{j_k})_{k=p} = (a_k)_{k=p}$.
$\Box$
Theorem: Seq. lim. is subseq. lim.
If a sequence has a limit, then every subsequence has that limit.
Statement and proof. Statement: Suppose $\lim_{k\to\infty} a_k = L\in\Bbb R$ and let $(a_{i_k})_{k=1}$ be a subsequence. Then $$\lim_{k\to\infty} a_{i_{k}} = L$$ Proof: Let $\varepsilon\in\Bbb R$ and let the $p$th tail of $(a_k)_{k=m}$ be within $\varepsilon$ of $L$.
Since $i_k$ is strictly increasing, then for each $k\in\Bbb N$ we have $k \le i_k$. In particular, $p\le i_p$.
Moreover, for each $p\le q$ we have $p\le i_p\le i_q$ and therefore $a_{i_q}$ is within $\varepsilon$ of $L$. Hence the $p$th tail of $(a_{i_k})_{k=1}$ is within $\varepsilon$ of $L$.
This shows that $(a_{i_k})_{k=1}$ is eventually within $\varepsilon$ of $L$.
But since $\varepsilon$ was arbitrary, then $\displaystyle \lim_{k\to\infty}a_{i_k} = L$.
$\Box$
Theorem: Seq. lim. of dist.
Limit equivalence to limit of distance.
Statement and proof. Statement: $\lim_{k\to\infty} a_k = L$ if and only if $\lim_{k\to\infty}|a_k-L| = 0$.

Proof: The proof comes entirely from definitions, and the fact that $|a_k-L| = ||a_k-L|-0|$.
$\Box$
Theorem: Seq. alg. lims.
Algebraic limit laws.
Statement and proof. Statement: Assume that $a_n\to A, b_n\to B$ and $c\in\Bbb R$.

  1. $\lim_{k\to\infty} ca_k = c A$.
  2. $\lim_{k\to\infty} (a_k+b_k) = A+B$.
  3. $\lim_{k\to\infty} a_kb_k = AB$.
  4. If $b_k\ne 0$ for every $k\ge m$, and if $B\ne 0$, then $\lim_{k\to\infty}\frac{a_k}{b_k} = \frac AB$.
Proof:
$\lim_{k\to\infty} ca_k = cA$. Let $\varepsilon\in\Bbb R^+$ and set $p$ such that $(a_k)_{k=p}$ is within $\varepsilon / |c|$ of $A$.
Then for $k\ge p$, $$ \begin{aligned} |ca_k - cA| &= |c| |a_k-A| \\ &< |c| \cdot \varepsilon / |c| \\ &= \varepsilon \end{aligned}$$
$\lim_{k\to\infty}(a_k+b_k) = A+B$. Let $\varepsilon\in\Bbb R^+$. Set $p$ such that $(a_k)_{k=p}$ is within $\varepsilon/2$ of $A$. Set $q$ such that $(b_k)_{k=q}$ is within $\varepsilon/2$ of $B$.
Now set $r = \max\{ p,q \}$, which implies that $(a_k)_{k=r}$ is within $\varepsilon/2$ of $A$, and also $(b_k)_{k=r}$ is within $\varepsilon/2$ of $B$.
Therefore, for $k\ge r$, we have, by algebra and then the triangle inequality, $$\begin{aligned} |(a_k+b_k)- (A+B)| &= |(a_k-A)+(b_k-B)| \\ & \le |a_k-A|+|b_k+B| \\ & < \frac \varepsilon 2 + \frac \varepsilon 2 \\ &= \varepsilon \end{aligned} $$
$\lim_{k\to\infty}a_kb_k = AB$. Note that from an earlier theorem (ref needed), if a sequence has a limit then it is bounded. Let $\alpha$ be a bound on $(a_k)_{k=m}$.
Let $\varepsilon\in\Bbb R^+$.
First assume that one of the two limits is zero. Without loss of generality, assume $B=0$.
Let $(b_k)_{k=q}$ be within $\varepsilon/\alpha$ of 0.
Then for all $k\ge \max\{p,q\}$, $$\begin{aligned} |a_kb_k - AB| &= |a_kb_k| \\ &= |a_k||b_k| \\ &< \alpha \cdot \varepsilon/\alpha \\ &= \varepsilon \end{aligned}$$ Next we assume that $B\ne 0$.
Set $p$ such that $(a_k)_{k=p}$ is within $\varepsilon/|B|$ of $A$. Set $q$ such that $(b_k)_{k=q}$ is within $\varepsilon/\alpha$ of $B$.
Set $r=\max\{p,q\}$. Then $\forall k\ge r$, $$ \begin{aligned} |a_kb_k - AB| &= |a_kb_k - a_kB + a_kB - AB| \\ &\le |a_k||b_k-B| + |B||a_k-A| \\ & < \alpha\varepsilon/\alpha + |B|\varepsilon/|B| \\ &= 2\varepsilon \end{aligned}$$
If $b_n\ne 0\ne B$ then $\lim_{k\to\infty}\frac{a_k}{b_k} = \frac AB$. This follows immediately from $\frac{a_k}{b_k} = a_k\cdot\frac{1}{b_k}$ and the previous result, once we have shown $\lim_{k\to\infty}\frac 1 {b_k} = \frac 1 B$.
To show this, let $\varepsilon\in\Bbb R^+$ and let $(b_k)_{k=p}$ be within $\frac{\varepsilon|B|^2}2$ of $B$.
Let $(b_k)_{k=q}$ be such that $\frac{|B|}{2} < |b_k|$. Then for $k\ge \max\{p,q\}$, $$ \begin{aligned} \left| \frac{1}{b_k} - \frac{1}{B} \right| &= {\Huge|} \frac{B - b_k}{b_k B} {\Huge|} \\ &= \frac{ |b_k - B| }{ |b_k| \, |B| } \\ &< \frac{ \varepsilon |B|^2 / 2 }{ (|B|/2) |B| } \\ &= \varepsilon \end{aligned} $$
$\Box$