Sequences

# Sequences

A sequence $$\{p_n\}$$ in a metric space $$X$$ is a function $$f : \mathbb{N} \rightarrow X$$ which maps $$n$$ to $$p_n$$, a point in $$X$$.

A sequence $$\{p_n\}$$ converges if there exists a point $$p \in X$$ such that for any $$\epsilon > 0$$, there exists an index $$\mathcal{N} \in \mathbb{N}$$ such that $$n \geq \mathcal{N}$$ implies $$d(p_n, p) < \epsilon$$. A convergent sequence is denoted as $$p_n \rightarrow p$$, read as $$p_n$$ converges to $$p$$, or $$\lim\limits_{n \rightarrow \infty} p_n = p$$, read as $$p$$ is the limit of a sequence $$p_n$$.

For example,

1. In $$\mathbb{R}$$, the sequence $$p_n = \frac{n + 1}{n}$$ converges to $$1$$.

Proof. Consider any $$\epsilon > 0$$. Choose $$\mathcal{N} = \left\lceil\frac{1}{\epsilon}\right\rceil + 1$$. For any integer $$n \geq \mathcal{N}$$, $$n > \frac{1}{\epsilon}$$. Hence, $$\frac{1}{n} < \epsilon$$. So, $$d(p_n, 1) = \left|\frac{n + 1}{n} - 1\right| = \left|\frac{1}{n}\right| < \epsilon$$. QED.

2. If $$p_n \rightarrow p$$ and $$p_n \rightarrow p'$$ then $$p = p'$$.

Proof (by contradiction). Assume $$p_n \rightarrow p$$ and $$p_n \rightarrow q$$. Let $$\epsilon = d(p, q)$$. Then, due to convergence, there exists $$\mathcal{N}_p$$ such that $$n \geq \mathcal{N}_p$$ implies $$d(p_n, p) < \frac{\epsilon}{2}$$. Also, there exists $$\mathcal{N}_q$$ such that $$n \geq \mathcal{N}_q$$ implies $$d(p_n, q) < \frac{\epsilon}{2}$$. Let $$\mathcal{N} = \max \{\mathcal{N}_p, \mathcal{N}_q\}$$. Then $$n \geq \mathcal{N}$$ implies $$\epsilon = d(p, q) \leq d(p_n, p) + d(p_n, q) < \frac{\epsilon}{2} + \frac{\epsilon}{2} = \epsilon$$, which is a contradiction. QED.

3. If $$\{p_n\}$$ is bounded (the range of $$p_n$$ is bounded) then $$p_n$$ converges.

False.

4. If $$p_n$$ converges then $$p_n$$ is bounded.

Proof. Use $$\epsilon = 1$$. Then there exists $$\mathcal{N}$$ such that $$n \geq \mathcal{N}$$ implies $$d(p_n, p) < 1$$. Let $$R = \max\{1, d(p, p_1), \dots, d(p, p_{\mathcal{N} - 1})\}$$. All $$\{p_n\}$$ are in the open ball $$B_{R + 1}(p_n)$$. QED.

5. If $$p_n \rightarrow p$$ then $$p$$ is a limit point of the range of $$\{p_n\}$$.

False.

6. If $$p$$ is a limit point of $$E$$ in $$X$$, there exists a sequence $$\{p_n\}$$ in $$E$$ such that $$p_n \rightarrow p$$.

Proof. Choose a sequence $$\{p_n\}$$, where each $$p_n$$ is in an open ball $$B_\frac{1}{n}(p)$$. Then $$p_n \rightarrow p$$. QED.

7. $$p_n \rightarrow p$$ if and only if every neighborhood of $$p$$ contains all but finitely many $$p_n$$.

TRUE.

IMPORTANT IDEA: to show convergence, you must fine an $$\mathcal{N}$$ for every $$\epsilon$$.

Consider sequences $$\{s_n\}$$, $$\{t_n\}$$ in $$\mathbb{C}$$ where $$s_n \rightarrow s$$ and $$t_n \rightarrow t$$.

Theorem. $$\lim\limits_{n \rightarrow \infty} (c + s_n) = c + s$$.

Proof. Fix $$\epsilon > 0$$. Then, there exists $$\mathcal{N}$$ such that $$n \geq \mathcal{N}$$ implies $$|s_n - s| < \epsilon$$. Hence, for this $$\mathcal{N}$$, $$n \geq \mathcal{N}$$ implies $$|(c + s_n) - (c - s)| = |s_n - s| < \epsilon$$, as desired. QED.

Theorem. $$\lim\limits_{n \rightarrow \infty} (s_n + t_n) = s + t$$.

Proof. Given $$\epsilon > 0$$, there exist $$\mathcal{N}_s$$ and $$\mathcal{N}_t$$ such that if $$n \geq \mathcal{N}_s$$ then $$|s_n - s| < \frac{\epsilon}{2}$$ and if $$n \geq \mathcal{N}_t$$ then $$|t_n - t| < \frac{\epsilon}{2}$$. Let $$\mathcal{N} = \max\{\mathcal{N}_s, \mathcal{N}_t\}$$. Then, for $$n \geq \mathcal{N}$$, $$|(s_n + t_n) - (s + t)| \leq |s_n - s| + |t_n - t| < \frac{\epsilon}{2} + \frac{\epsilon}{2} = \epsilon$$, as desired. QED.

Theorem. $$\lim\limits_{n \rightarrow \infty} (cs_n) = cs$$.

Proof. Fix $$\epsilon > 0$$. Then, there exists $$\mathcal{N}$$ such that $$n \geq \mathcal{N}$$ implies $$|s_n - s| < \frac{\epsilon}{|c|}$$. Hence, for this $$\mathcal{N}$$, $$n \geq \mathcal{N}$$ implies $$|cs_n - cs| = |c||s_n - s| < \epsilon$$, as desired. QED.

Theorem. $$\lim\limits_{n \rightarrow \infty} (s_nt_n) = st$$.

Proof. Fix $$\epsilon > 0$$. Let $$k = \max\{1, \epsilon, s, t\}$$. Then, there exist $$\mathcal{N}_s$$ and $$\mathcal{N}_t$$ such that if $$n \geq \mathcal{N}_s$$ then $$|s_n - s| < \frac{\epsilon}{3k}$$ and if $$n \geq \mathcal{N}_t$$ then $$|t_n - t| < \frac{\epsilon}{3k}$$. Let $$\mathcal{N} = \max\{\mathcal{N}_s, \mathcal{N}_t\}$$. Then, for $$n \geq \mathcal{N}$$, $$|s_nt_n - st| = |(s_n - s)(t_n - t) + s(t_n - t) + t(s_n - s)| < \frac{\epsilon^2}{9k^2} + \frac{\epsilon}{3} + \frac{\epsilon}{3} < \frac{\epsilon}{9k} + \frac{\epsilon}{3} + \frac{\epsilon}{3} < \epsilon$$, as desired. QED.

# Subsequences

Suppose $$\{p_n\}$$ is a sequence. Let $$n_1 < n_2 < n_3 < \dots$$, where $$n_i \in \mathbb{N}$$, be an increasing sequence. Then, $$\{p_{n_i}\}$$ is a subsequence.

If $$p_n \rightarrow p$$ then every subsequence converges to $$p$$.

For example,

1. The sequence $$\{1, \pi, \frac{1}{2}, \pi, \frac{1}{3}, \pi, \dots\}$$ does not converge. But it has a subsequence $$\{1, \frac{1}{2}, \frac{1}{3}, \dots\}$$ that converges to $$0$$ and another subsequence $$\{\pi, \pi, \pi, \dots\}$$ that converges to $$\pi$$, which is called a subsequential limit.

A metric space is sequentially compact if every sequence has a convergent subsequence.

Theorem. If a metric space $$X$$ is compact then $$X$$ is sequentially compact. Or, equivalently, in a compact metric space, every sequence has a subsequence converging to a point of $$X$$.

(In fact, compactness is equivalent to sequential compactness.)

Proof. Let $$R = \text{range}\{p_n\}$$. If $$R$$ is finite, then some $$p \in p_n$$ is achieved infinitely many times. Use that subsequence. If $$R$$ is infinite, then by previous theorem, since $$X$$ is compact, $$R$$ has a limit point $$p$$. Use that point $$p$$ and its nested neighborhoods to construct a subsequence convergent on $$p$$. QED.

Corollary. Every bounded sequence in $$\mathbb{R}^k$$ contains a convergent subsequence.

# Cauchy Sequence

A sequence $$\{p_n\}$$ is a Cauchy sequence if for every $$\epsilon > 0$$, there exists $$\mathcal{N}$$ such that $$m, n > \mathcal{N}$$ implies $$d(p_m, p_n) < \epsilon$$.

Theorem. If $$\{p_n\}$$ converges, then $$\{p_n\}$$ is a Cauchy sequence.

Proof. Given $$\epsilon > 0$$, there exists $$\mathcal{N}$$ such that if $$n \geq \mathcal{N}$$ then $$|p_n - p| < \frac{\epsilon}{2}$$. Then, for this $$\mathcal{N}$$, $$m, n > \mathcal{N}$$ implies $$d(p_m, p_n) \leq d(p_m, p) + d(p_n, p) < \frac{\epsilon}{2} + \frac{\epsilon}{2} = \epsilon$$, as desired. QED.

# Complete Spaces

A metric space $$X$$ is complete if every Cauchy sequence converges to a point of $$X$$.

For example,

1. $$\mathbb{Q}$$ is not complete.

Theorem. Compact metric spaces are complete.

Proof. Let $$\{x_n\}$$ be a Cauchy sequence in $$X$$. Since $$X$$ is compact, it is sequentially compact. So, there exists a subsequence $$\{x_{n_k}\}$$ converging to a point $$x \in X$$. Fix $$\epsilon > 0$$. The fact that sequence $$\{x_n\}$$ is a Cauchy sequence implies there exists $$\mathcal{N}_1$$ such that if $$i, j > \mathcal{N}$$ then $$d(x_i, x_j) < \frac{\epsilon}{2}$$. The fact that $$\{x_{n_k}\}$$ converges to $$x$$ implies there exists $$\mathcal{N}_2$$ such that if $$n_k \geq \mathcal{N}_2$$ then $$d(x_{n_k}, x) < \frac{\epsilon}{2}$$. Let $$\mathcal{N} = \max\{\mathcal{N}_1, \mathcal{N}_2\}$$. Fix any $$n_k, n > \mathcal{N}$$. By triangle inequality, $$d(x_n, x) \leq d(x_n, x_{n_k}) + d(x_{n_k}, x) < \frac{\epsilon}{2} + \frac{\epsilon}{2} = \epsilon$$. Since $$\{x_n\}$$ is arbitary, $$X$$ is complete. QED.

Corollary. $$[0, 1]$$ is complete.

Corollary. $$k$$-cells in $$\mathbb{R}^k$$ are complete.

Corollary. Any closed subset of a compact set is complete.

Corollary. $$\mathbb{R}^k$$ is complete.

Proof. If $$\{x_n\}$$ is Cauchy, it’s bounded. So it’s in some $$k$$-cell in $$\mathbb{R}^k$$. Hence, $$\{x_n\}$$ converges because $$k$$-cells are complete. QED.

For example,

1. $$x_n = 1 + \frac{1}{2} + \dots + \frac{1}{n}$$ does not converge.

Proof. Given $$n > m$$, consider $$|x_n - x_m| = \frac{1}{m + 1} + \frac{1}{m + 2} + \dots + \frac{1}{n} \geq \frac{n - m}{n} = 1 - \frac{m}{n}$$. Let $$n = 2m$$. We have $$|x_{2m} - x_m| \geq \frac{1}{2}$$. So the sequence is not Cauchy. Thus, it does not converge. QED.

2. Let $$x_1 = 1$$, $$x_2 = 2$$, and $$x_n = \frac{x_{n - 1} + x_{n - 2}}{2}$$. Every subsequence of it is Cauchy so it is convergent.

Theorem. Every metric space $$(X, d)$$ has a completion $$(X^\star, d)$$.

Idea: Given $$X$$, let $$X^\star$$ be the set of all Cauchy sequences in $$X$$ under an equivalent relation $$\sim$$, where $$\{p_n\} \sim \{q_n\}$$ if $$\lim\limits_{n \rightarrow \infty} d(p_n, q_n) = 0$$. For $$P, Q \in X^\star$$, let $$\Delta(P, Q) := \lim\limits_{n \rightarrow \infty} d(p_n, q_n)$$, where $$\{p_n\}$$ and $$\{q_n\}$$ are representatives of $$P$$ and $$Q$$, respectively.

# Bounded Sequences

Monotonically increasing sequences: $$\dots \leq s_{n - 1} \leq s_n \leq \dots$$

Monotonically decreasing sequences: $$\dots \geq s_{n - 1} \geq s_n \geq \dots$$

Theorem. Bounded monotonic sequences converge to their suprema (if increasing) or to their infima (if decreasing).

Proof. Fix a bounded monotonically increasing sequence \${x_n}. Let $$s = \sup(\text{range}\{x_n\})$$. So, for all $$\epsilon > 0$$, there exists $$\mathcal{N}$$ such that $$s - \epsilon \leq x_\mathcal{N} \leq s$$. Then, for all $$n \geq \mathcal{N}$$, $$s - \epsilon \leq x_\mathcal{N} \leq x_n \leq s$$, as desired. QED.

# Divergent Sequences

Write $$x_n \rightarrow +\infty$$ if for all $$\mathcal{M} \in \mathbb{R}$$, there exist $$\mathcal{N}$$ such that $$n \geq \mathcal{N}$$ implies $$x_n > \mathcal{M}$$.

Write $$x_n \rightarrow -\infty$$ if for all $$\mathcal{M} \in \mathbb{R}$$, there exist $$\mathcal{N}$$ such that $$n \geq \mathcal{N}$$ implies $$x_n < \mathcal{M}$$.

Given sequence $$\{x_n\}$$, let $$E$$ be the set of all possible subsequential limits of $$\{x_n\}$$ (allowing $$+\infty$$ and $$-\infty$$, i.e. $$E$$ is in extended $$\mathbb{R}$$). Then $$E$$ is closed. Let $$s^\star = \sup E$$ and $$s_\star = \inf E$$. Then $$\limsup\limits_{n \rightarrow \infty} s_n = s^\star$$, called the upper limit of $$s_n$$, and $$\liminf\limits_{n \rightarrow \infty} s_n = s_\star$$, called the lower limit of $$s_n$$.

Alternatively, $$\limsup\limits_{n \rightarrow \infty} s_n = \lim\limits_{n \rightarrow \infty}\left(\sup\limits_{k \geq n} s_k\right)$$. Similarly, $$\liminf\limits_{n \rightarrow \infty} s_n = \lim\limits_{n \rightarrow \infty}\left(\inf\limits_{k \geq n} s_k\right)$$.

For example,

1. If $$s_n \rightarrow s$$ then $$\liminf s_n = \limsup s_n = s$$.
2. If $$\{s_n\} = \{0.1, \frac{3}{2}, 0.11, \frac{4}{3}, 0.111, \frac{5}{4}, 0.1111, \frac{6}{5}, \dots\}$$ then $$\limsup s_n = 1$$ and $$\liminf s_n = \frac{1}{9}$$.