Sequences and Series

Sequences

Definition 1. Any function $a \colon N \to Y$ is called a sequence in $Y$.

Given a sequence $a \colon N \to Y$, we will typically write it as $(a_n)_{n \in \N}$, where $a_n = a(n)$. Often, we will abbreviate this further and write $(a_n)$ as the entire sequence.

Convergence

Definition 2. We say a sequence $(a_n)$ converges to a limit $\ell \in Y$ if for every $\epsilon > 0$ there exists $N \in \N$ such that $n \geq N$ implies $d(a_n, \ell) < \epsilon$.

Remark 3 (notation). When $(a_n)$ converges to a limit $\ell$, we often write $a_n \to \ell$ as $n \to \infty$, or $\lim_{n \to \infty} a_n = \ell$.

Proposition 4. The sequence $1/n \to 0$ as $n \to \infty$.

Proof. This follows from the Archemedian principle.

Remark 5. The standard theorems about sums, products, quotients hold for sequences. You can either reprove them directly from the definition, or use this problem to view the limit of a sequence as the limit in the metric space $\N \cup \set{\infty}$, with the metric defined in the problem.

Continuity using sequences

Theorem 6. Let $f \colon X \to Y$ be a function. The function $f$ is continuous at $a$ if and only if for every sequence $(a_n)$ such that $a_n \to a$ as $n \to \infty$, we have $f(a_n) \to f(a)$ as $n \to \infty$.

Problem 7. Let $A \subseteq X$. Show that the closure of $A$ is exactly the set of all points $\alpha \in X$ for which there exists a sequence $(a_n)$ such that $a_n \in A$ for every $n \in \N$, and $a_n \to \alpha$ as $n \to \infty$.

Problem 8. Let $f \colon X \to \R$ be a continuous function.

Show that $\overline{ \set{ f > 0 } } \subseteq \set{f \geq 0}$. (Here $\set{f > 0} = \set{x \in X \st f(x) > 0}$, and $\overline{ \set{ f > 0 } }$ denotes the closure of $\set{f > 0}$.)
Must $\overline{ \set{ f > 0 } } = \set{f \geq 0}$? Prove it, or find a counter example.

Monotone sequences

Definition 9. The sequence $a\colon \N \to \R$ is increasing if for every $n \in \N$ we have $a_n \leq a_{n+1}$.

Definition 10. The sequence $a\colon \N \to \R$ is decreasing if for every $n \in \N$ we have $a_n \geq a_{n+1}$.

Remark 11. If the inequalities above are strict, then we call the sequence strictly increasing or strictly decreasing. A sequence is called monotone if it’s either increasing, or decreasing.

Definition 12. A sequence $a \colon \N \to \R$ is bounded if $\set{a_n \st n \in \N}$ is bounded.

Proposition 13. Any bounded monotone sequence is convergent.

Problem 14. A bounded sequence need not be convergent.

Problem 15. A monotone sequence need not be convergent.

Problem 16. A convergent sequence must be bounded.

Connectedness

Theorem 17 (Intermediate value theorem). If $f \colon [a, b] \to \R$ is continuous, with $f(a) \leq 0$, $f(b) \geq 0$, then there exists $x \in [a, b]$ such that $f(x) = 0$.

Proof sketch. Use bisection, Theorem 6 and Proposition 13.

Problem 18. Show that any polynomial of odd degree has a real root.

Theorem 19 (Connectedness). $\R^d$ can not be expressed as the union of two non-empty disjoint open sets.

Proof sketch. For $d = 1$, suppose $\R = U \cup V$ with $U, V$ open and disjoint. Pick $v \in V$ and set $\alpha = \sup \set{u \in U \st u < v}$. Show that $\alpha \in U$ and $\alpha \not\in U$ to produce a contradiction.

For $d > 1$, pick $u \in U$, $v \in V$ and see if you can do something similar on the line joining $U$ and $V$.

liminf and limsup

Definition 20. Let $a \colon N \to \R$ be a sequence. Define \begin{equation} \liminf_{n \to \infty} a_n = \sup_{n \in \N} \paren[\big]{ \inf_{k \geq n} a_n } \quad\text{and}\quad \limsup_{n \to \infty} a_n = \inf_{n \in \N} \paren[\big]{ \sup_{k \geq n} a_n } \end{equation}

Remark 21. If $A$ is unbounded above, we define $\sup A = \infty$. So if the sequence $(a_n)$ above isn’t bounded, the $\limsup$ or the $\liminf$ may be $\pm \infty$.

Theorem 22. Let $(a_n)$ be a bounded sequence in $\R$.

$\liminf a_n \leq \limsup a_n$.
$\liminf a_n = \limsup a_n$ if and only if the sequence is convergent. In this case \begin{equation} \lim_{n \to \infty} a_n = \limsup_{n \to \infty} a_n = \liminf_{n \to \infty} a_n \,. \end{equation}

Remark 23. For any sequence, convergent or not, $\liminf_{n \to \infty} a_n \leq \limsup_{n \to \infty} a_n$.

Problem 24. If $a, b \colon \N \to \R$ are two sequences, then \begin{equation} \liminf_{n \to \infty} a_n + \liminf_{n \to \infty} b_n \leq \liminf_{n \to \infty} (a_n + b_n) \leq \limsup_{n \to \infty} (a_n + b_n) \leq \limsup_{n \to \infty} a_n + \limsup_{n \to \infty} b_n \,. \end{equation}

Cauchy Sequences

Definition 25. A sequence $a \colon \N \to Y$ is called Cauchy if for every $\epsilon > 0$ there exists $N \in \N$ such that for every $m, n \geq N$ we have $d(a_m, a_n) < \epsilon$.

Proposition 26. Every convergent sequence is Cauchy.

Remark 27. The converse is false; in a general metric space, there may be Cauchy sequences which are not convergent.

Theorem 28 (Completeness of $\R^d$). Any Cauchy sequence in $\R^d$ is convergent.

Proof sketch. First suppose $d = 1$.

Show that any Cauchy sequence is bounded.
Pick $\epsilon > 0$, let $\alpha_k = \sup_{k \geq n} a_n$, $\beta_k = \inf_{k \geq n} a_n$. Find $N$ so that $\abs{a_m - a_n} < \epsilon$ whenever $m, n \geq N$.
For this $\epsilon, N$ check that $\beta_N - \alpha_N \leq \epsilon$.
This implies $0 \leq \limsup a_n - \liminf a_n \leq \beta_N - \alpha _N \leq \epsilon$.
Since $\epsilon > 0$ was arbitrary, this implies $\limsup a_n = \liminf a_n$, and hence the sequence is convergent by this theorem.

When $d \geq 1$, check that every coordinate is Cauchy, and use this proposition.

Definition 29. A metric space $X$ is called complete if every Cauchy sequence in $X$ is convergent.

Remark 30. The metric space $\Q$ is not complete. The metric spaces $\R$, $\R^d$ are both complete.

Proposition 31. Any closed subset of a complete metric space is also a complete metric space.

Dense sets

Definition 32. A set $D \subseteq X$ is called dense if for every $x \in X$ there exists a sequence $(d_n)$ in $D$ such that $d_n \to x$ as $n \to \infty$.

Proposition 33. $\Q^d$ and $\R^d - \Q^d$ are both dense in $\R^d$.

Example 34. $\Z^d$ is not dense in $\R^d$.

Proposition 35. If $U \neq \emptyset$ is open and $D$ is dense, then $U \cap D \neq \emptyset$.

Proposition 36. If $U_1$, $U_2$ are two open dense sets, then $U_1 \cap U_2$ is also an open dense set.

Theorem 37 (Baire category theorem). Let $X$ be a complete metric space. If $\set{U_n \st n \in \N}$ is a family of open dense sets in $X$ then $\bigcap_{n=1}^\infty U_n$ is also dense.

Proof sketch. We won’t need or use this in this class; If you’re curious a proof is here.

Series

Convergence

Let $(a_n)$ be a sequence in $\R^d$.

Definition 38. The $n$-th partial sum of the sequence $(a_n)$ is defined by $s_n = \sum_{k \leq n} a_k$. We say series $\sum_1^\infty a_k$ is convergent (or the sequence $(a_n)$ is sumable) if the sequence of partial sums $(s_n)$ is convergent. In this case we define $\sum_1^\infty a_k = \lim_{n \to \infty} s_n$.

Proposition 39. Let $r \in \R$. The series $\sum_0^\infty r^n$ is convergent if and only if $\abs{r} < 1$. In this case $\sum_0^\infty r^n = \frac{1}{1 - r}$.

Proposition 40. Let $s \in \R$. The series $\sum_1^\infty \frac{1}{n^s}$ is convergent if and only if $s > 1$.

Proof sketch. A common way this is proved in high-school is to use the integral test, which we aren’t in a position now. A direct proof can be done by noting \begin{equation} \frac{2^k}{2^{s(k+1)}} \leq \sum_{n = 2^k + 1}^{2^{k+1}} \frac{1}{n^s} \quad\text{and}\quad \sum_{n = 2^k}^{2^{k+1}-1} \frac{1}{n^s} \leq \frac{2^k}{2^{s k}} \,. \end{equation}

Proposition 41. If the series $\sum_1^\infty a_k$ is convergent, then $a_k \to 0$ as $k \to \infty$.

Problem 42. Show that the converse is false; if $a_k \to 0$ as $k \to \infty$, then the series $\sum_1^\infty a_k$ need not converge.

Absolute convergence

Definition 43. We say the series $\sum_1^\infty a_k$ is absolutely convergent if the series $\sum_1^\infty \abs{a_k}$ is convergent.

Proposition 44. Any absolutely convergent series in $\R^d$ is convergent.

Problem 45. Show that a convergent series need not be absolutely convergent.

A series which is convergent but not absolutely convergent is called conditionally convergent. Rearranging the order of terms in an absolutely convergent series won’t change it’s value. But for a conditionally convergent series, the terms can be rearranged to converge to any given value.

Definition 46. Let $\sigma \colon \N \to \N$ be a bijection. We say the series $\sum_{n=1}^\infty a_{\sigma(n)}$ is a rearrangement of the series $\sum_{n=1}^\infty a_n$.

Theorem 47. If $\sum a_n$ is absolutely convergent then for any bijection $\sigma \colon \N \to \N$ we have $\sum_1^\infty a_{\sigma(n)} = \sum_1^\infty a_n$.

Theorem 48 (Riemann series theorem). Let $\sum a_n$ be a conditionally convergent series in $\R$. For every $\alpha \in \R$ there exists a bijection $\sigma \colon \N \to \N$ such that $\sum_1^\infty a_{\sigma(n)} = \alpha$.

Note In class I accidentally attributed this to Hardy; that’s incorrect, it’s due to Riemann. The higher dimensional version of this is the Lévy-Steinitz theorem, which says that the set of values of all rearrangements is either the empty set, or of the form $\alpha + V$, where $V \subseteq \R^d$ is a subspace.

Proof sketch. Let’s use the convention that $b:\N \to [0, \infty)$ is a sequence of nonnegative reals, then we say $\sum b_n < \infty$ if the series is convergent. Also define $x^{+} = x \varmax 0 = \max \set{ x, 0}$, and $x^{-} = -(x \varmin 0) = -\min\set{x, 0}$.

Let $p_n = a_n^{+}$, $q_n = a_n^{-}$. Note $\sum_1^\infty a_n = \sum_1^{\infty} (p_n - q_n)$ and $\sum_1^\infty \abs{a_n} = \sum_1^{\infty} (p_n + q_n)$.
Use $\sum \abs{a_n} = \infty$ to show either $\sum p_n = \infty$ or $\sum q_n = \infty$.
Use $\sum q_n = \sum (p_n - a_n)$ to show both $\sum q_n = \infty$, and $\sum p_n = \infty$.
Choose $m_1 = \min \set{ n \st \sum_1^n p_k > \alpha }$, and set $s_1 = \sum_1^{m_1} p_k$ (justify why this exists).
Choose $n_1 = \min \set{ n \st s_1 + \sum_1^n q_k > \alpha }$ and set $s_2 = s_1 + \sum_1^{n_1} q_k$ (justify why this exists).
Choose $m_2 = \min \set{ n \st s_2 + \sum_{m_1 + 1}^{n} p_k > \alpha }$, and set $s_3 = s_2 + \sum_{m_1 + 1}^{m_2} p_k$ (justify why this exists).
Continue inductively; show that $s_n \to \alpha$ as $n \to \infty$, and use this to build $\sigma$.

Tests for convergence

Theorem 49 (Comparison test). If $a\colon \N \to \R^d$, and $b \colon \N \to [0, \infty)$ are such that $\abs{a_n} \leq b_n$ for every $n \in \N$. Then if $\sum_1^\infty b_k < \infty$ the series $\sum_1^\infty a_n$ is absolutely convergent.

Proposition 50 (Root test). Let $\rho = \limsup \abs{a_n}^{1/n}$.

If $\rho < 1$ the series $\sum a_n$ is absolutely convergent.
If $\rho > 1$ the series $\sum a_n$ is divergent.

Proposition 51 (Ratio test).

If $\limsup \abs{a_{n+1}} / \abs{a_n} < 1$ the series $\sum a_n$ is absolutely convergent.
If $\liminf \abs{a_{n+1}} / \abs{a_n} > 1$ the series $\sum a_n$ is divergent.