Chapter 3 Numerical Sequences and Series
- Part A: Exercise 1 – Exercise 14
- Part B: Exercise 15 – Exercise 17
- Part C: Exercise 18 – Exercise 25
Exercise 18
Lemma: For an integer $p \geq 1$ and real $a$ where $0 < a < 1$ \[ p(1-a) \geq 1 – a^p \,. \]
Proof: We have\begin{align*}
p &= \sum_{n=0}^{p-1} 1 = \sum_{n=0}^{p-1} 1^n \geq \sum_{n=0}^{p-1} a^n && \text{(equality when $p=1$)}\\
&= \frac{1-a}{1-a} \sum_{n=0}^{p-1} a^n = \frac{1}{1-a} \left(\sum_{n=0}^{p-1} a^n – a\sum_{n=0}^{p-1} a^n\right) && \text{(since $1-a \neq 0$)} \\
&= \frac{1}{1-a} \left(\sum_{n=0}^{p-1} a^n – \sum_{n=0}^{p-1} a^{n+1}\right) \\
&= \frac{1}{1-a} \left(\sum_{n=0}^{p-1} a^n – \sum_{n=1}^{p} a^n\right) \\
&= \frac{1}{1-a} \left(a^0 + \sum_{n=1}^{p-1} a^n – \sum_{n=1}^{p-1} a^n – a^p\right) \\
&= \frac{1}{1-a} \left(1 – a^p\right) \,.
\end{align*}From this the desired result follows immediately since $1-a > 0$.
Now we assume that for this family of sequences we always have $x_1 > \sqrt[p]\alpha$ and we claim that the sequence converges to $\sqrt[p]\alpha$ for a given $p$. So assume that $p$ is a fixed positive integer. First we claim that $x_n > \sqrt[p]\alpha$ for all $n \geq 1$. We show this by induction. The $n=1$ case is by construction so assume that $x_n > \sqrt[p]\alpha$. We then have \[ x_n > \sqrt[p]\alpha > 0 \]\[ 1 > \frac{\sqrt[p]\alpha}{x_n} > 0\,. \]So then by Lemma~3.18.1 above we have\begin{align*}
p\left(1 – \frac{\sqrt[p]\alpha}{x_n}\right) &\geq 1 – \left(\frac{\sqrt[p]\alpha}{x_n}\right)^p \\
p – p\frac{\sqrt[p]\alpha}{x_n} &\geq 1 – \frac{\alpha}{x_n^p} \\
p + \frac{\alpha}{x_n^p} &\geq 1 + p\frac{\sqrt[p]\alpha}{x_n} \\
p x_n + \frac{\alpha}{x_n^{p-1}} &\geq x_n + p\sqrt[p]\alpha && \text{(since $x_n > 0$)} \\
(p-1) x_n + \frac{\alpha}{x_n^{p-1}} &\geq p\sqrt[p]\alpha \\
\frac{p-1}{p} x_n + \frac{\alpha}{p x_n^{p-1}} &\geq \sqrt[p]\alpha \\
x_{n+1} &\geq \sqrt[p]\alpha \,.
\end{align*}Given this it is easy to show that $\{x_n\}$ decreases monotonically. Since $x_n \geq \sqrt[p]\alpha$ for any $n \geq 1$, clearly $x_n^p \geq \alpha$.Therefore we have \[
x_{n+1} = \frac{p-1}{p} x_n + \frac{\alpha}{p x_n^{p-1}} \leq
\frac{p-1}{p} x_n + \frac{x_n^p}{p x_n^{p-1}} =
\frac{p-1}{p} x_n + \frac{x_n}{p} =
\frac{p – 1 + 1}{p} x_n = \frac{p}{p} x_n = x_n \,.
\]So since $\{x_n\}$ is bounded (above by $x_1$ and below by $\sqrt[p]\alpha$) and monotic, it converges by Theorem 3.14. So let $x = \lim_{n\to\infty} x_n$, and then clearly $\lim_{n\to\infty} x_{n+1} = \lim_{n\to\infty} x_n = x$ also. Therefore we have
\[ \lim_{n\to\infty} x_{n+1} = \lim_{n\to\infty} \left(\frac{p-1}{p} x_n + \frac{\alpha}{p x_n^{p-1}}\right) \]\[ = \left(\frac{p-1}{p} \lim_{n\to\infty} x_n + \frac{\alpha}{p \lim_{n\to\infty} x_n^{p-1}}\right) \]\[= \left(\frac{p-1}{p} x + \frac{\alpha}{p x^{p-1}}\right) = x \,. \]Solving this straightforward equation for $x$ results in $x = \sqrt[p]\alpha$.
Thus these sequences provide a means by which the $p$th root of a real number can be calculated (approximately), and it is worth mentioning that the $p=2$ case corresponds to the sequence in Exercise 3.16 for the square root.
Exercise 19
(By Dan kyp44 Whitman) Let $A$ denote the set of all $\alpha$ sequences as defined in the text and let $x(A) = \{x(\alpha) : \alpha \in A\}$.
For a given sqeuence $\alpha \in A$ let \[ \beta_n = \frac{\alpha_n}{3^n} \] We first show that $x(\alpha) = \sum \beta_n$ converges. So consider any $\alpha \in A$. If $\{\alpha_n\}$ ends in all zeros (i.e. there is an $N\geq 1$ where $\alpha_n=0$ for all $n \geq N$) then clearly $\sum \beta_n$ is effectively finite and so therefore converges. If this is not the case then $\{\alpha_n\}$ clearly has a subsequence $\{\alpha_{k_n}\}$ where $\alpha_{k_n} = 2$ for all $n \geq 1$. Then, noting that obviously $\beta_n \geq 0$, we have\[
\limsup_{n \to \infty} \sqrt[n]{|\beta_n|} =
\limsup_{n \to \infty} \sqrt[n]{\beta_n} =
\limsup_{n \to \infty} \sqrt[n]{\frac{\alpha_n}{3^n}} =
\limsup_{n \to \infty} \frac{\sqrt[n]{\alpha_n}}{3} =
\lim_{n \to \infty} \frac{\sqrt[n]{\alpha_{k_n}}}{3} =
\lim_{n \to \infty} \frac{\sqrt[n]{2}}{3} = \frac{1}{3} \,,
\]where we have invoked Theorem~3.20b. It follows then from the Root Test (Theorem~3.33) that $\sum\beta_n$ converges.
Now, for a sequence $\alpha \in A$, $x(\alpha)$ is the real number whose representation in base three is $0.\alpha_1 \alpha_2 \alpha_3 \ldots$, i.e. $\alpha_n$ is the $n$th digit after the decimal point. Clearly if $\alpha_n = 0$ for all $n \geq 1$ then $x(\alpha) = 0$. We also note that if $\alpha_n = 2$ for all $n \geq 1$ then we have \[
x(\alpha) =
\sum_{n=1}^\infty \frac{\alpha_n}{3^n} =
\sum_{n=1}^\infty \frac{2}{3^n} =
2\sum_{n=1}^\infty \left(\frac{1}{3}\right)^n =
2\left[ \sum_{n=0}^\infty \left(\frac{1}{3}\right)^n – 1 \right] =
2\left[\frac{1}{1- \frac{1}{3}} – 1 \right] = 1 \,,
\]analagously to the way in which $0.99999\ldots = 1$. It follows then that $x(A) \subseteq [0, 1]$.
First consider any $m \geq 1$ for any $\alpha \in A$. We then have\[
3^m x(\alpha) = 3^m \sum_{n=1}^\infty \frac{\alpha_n}{3^n} =
\sum_{n=1}^\infty \frac{\alpha_n}{3^{n-m}} =
\sum_{n=1}^{m-1} \frac{\alpha_n}{3^{n-m}} + \sum_{n-m}^m \frac{\alpha_n}{3^{n-m}} + \sum_{n=m+1}^\infty \frac{\alpha_n}{3^{n-m}} \,,
\]where we adopt the convention that $\sum_{n=p}^q = 0$ for $p > q$, which is needed for the first sum if $m=1$. Continuing, we have \begin{gather}
3^m x(\alpha) = \sum_{n=1}^{m-1} 3^{m-n}\alpha_n + \alpha_m + \sum_{n=m+1}^\infty \frac{\alpha_n}{3^{n-m}} =
3j_{\alpha,m} + \alpha_m + \sum_{n=m+1}^\infty \frac{\alpha_n}{3^{n-m}} \,, \label{eqn:ex3.19-1}
\end{gather}where we define \[ j_{\alpha,m} = \sum_{n=1}^{m-1} 3^{m-n-1}\alpha_n \, \]noting that for the sum \[ m-1 \geq n \geq 1 \]\[ 1-m \leq -n \leq -1 \]\[ 1 \leq m-n \leq m-1 \]\[ 0 \leq m-n-1 \leq m-2 \]\[ 0 \leq j_{\alpha,m} \leq m-2 \]so that $j_{\alpha,m}$ is an integer (since the $\alpha_n$ are). Note also that $j_{\alpha,1} = 0$, following the convention. Now we examine the last sum in \eqref{eqn:ex3.19-1}. Letting $l = n-m$ so that $n = l+m$ we let \[
\delta_{\alpha,m} =
\sum_{n=m+1}^\infty \frac{\alpha_n}{3^{n-m}} =
\sum_{l=1}^\infty \frac{\alpha_{m+l}}{3^l} \,.
\]This sum of course depends on $\alpha$ but we can find its bounds. Clearly it will be the lowest when $\alpha_{l+m} = 0$ for $l \geq 1$ and the largest when $\alpha_{l+m} = 2$ for $l \geq 1$. We therefore have \[ 0 \leq \delta_{\alpha,m} \leq \sum_{l=1}^\infty \frac{2}{3^l} = 1 \,. \]Recombining this with \eqref{eqn:ex3.19-1} we have \begin{gather}
3^m x(\alpha) = 3j_{\alpha,m} + \alpha_m + \delta_{\alpha,m} \,, \label{eqn:ex3.19-2}\end{gather}where $j_{\alpha,m} \in \mathbb N$ (where $0 \in \mathbb N$) and $0 \leq \delta_{\alpha,m} \leq 1$.
Moving along, let $P$ denote the Cantor set. Now, by equation (2.24) in the text\[ y \notin P \iff \exists m \in \mathbb Z^+ \exists k \in \mathbb N \left[ y \in \left(\frac{3k+1}{3^m}, \frac{3k+2}{3^m} \right) \right]\,, \] where $\mathbb Z^+$ denotes the set of positive integers.Note that the text says that $k \in \mathbb Z^+$ but this should really be $k \in \mathbb N$ as written above. This is logically equivalent to \begin{gather}
y \in P \iff \forall m \in \mathbb Z^+ \forall k \in \mathbb N \left[ y \notin \left(\frac{3k+1}{3^m}, \frac{3k+2}{3^m} \right) \right] \nonumber \\
y \in P \iff \forall m \in \mathbb Z^+ \forall k \in \mathbb N \left[ \neg \left(y > \frac{3k+1}{3^m} \land y < \frac{3k+2}{3^m} \right) \right] \nonumber \\
y \in P \iff \forall m \in \mathbb Z^+ \forall k \in \mathbb N \left[ y \leq \frac{3k+1}{3^m} \lor y \geq \frac{3k+2}{3^m} \right] \nonumber \\
y \in P \iff \forall m \in \mathbb Z^+ \forall k \in \mathbb N \left[ 3^m y \leq 3k+1 \lor 3^m y \geq 3k+2 \right] \label{eqn:ex3.19-3}
\end{gather}
Finally we show that $x(A) = P$.
($\subseteq$) Consider any $\alpha \in A$ and consider any $m \in \mathbb Z^+$ and $k \in \mathbb N$.
If $\alpha_m = 0$ then by \eqref{eqn:ex3.19-2} \[ 3j_{\alpha,m} \leq 3^m x(\alpha) = 3j_{\alpha,m} + \delta_{\alpha,m} \leq 3j_{\alpha,m} + 1 \,.\]
So in the sub-case where $j_{\alpha,m} > k$ we have $j_{\alpha,m} \geq k+1$ so that\[ 3^m x(\alpha) \geq 3j_{\alpha,m} \geq 3(k+1) = 3k + 3 \geq 3k+2 \,. \]In the other sub-case when $j_{\alpha,m} \leq k$ we have\[ 3^m x(\alpha) \leq 3j_{\alpha,m} + 1 \leq 3k + 1 \]On the other hand if $\alpha_m = 2$ then again by \eqref{eqn:ex3.19-2}\[ 3j_{\alpha,m} + 2 \leq 3^m x(\alpha) = 3j_{\alpha,m} + 2 + \delta_{\alpha,m} \leq 3j_{\alpha,m} + 3 \]So in the sub-case where $j_{\alpha,m} \geq k$ we have\[ 3^m x(\alpha) \geq 3j_{\alpha,m} + 2 \geq 3k + 2\,, \]and the other sub-case where $j_{\alpha,m} < k$ we we have $j_{\alpha,m} + 1 \leq k$ so that \[ 3^m x(\alpha) \leq 3j_{\alpha,m} + 3 = 3(j_{\alpha,m} + 1) \leq 3k \leq 3k + 1 \]Thus, since the cases are exhaustive, we have shown that the right side of \eqref{eqn:ex3.19-3} is true, from which it follows that $x(\alpha) \in P$. Since $\alpha$ was an arbitrary sequence, $x(A) \subseteq P$.
($\supseteq$) Consider any $y \in P$. Then clearly $y \in [0, 1]$. So let $\alpha$ be the sequence corresponding to the base three representation of $y$ as described above; thus $y = x(\alpha)$. If $\alpha$ contains only zeros and twos, i.e. $\alpha_n \in \{0, 2\}$ for all $n \geq 1$ then clearly $\alpha \in A$ so that $y \in x(A)$. So suppose that there is an $n \geq 1$ where $\alpha_n = 1$. We will show that this is the only digit that is one and that, furthermore, there is an $\alpha’$ such that $\alpha’ \in A$ and $x(\alpha’) = x(\alpha) = y$.
So let $m$ be the index of the first digit that is a one, i.e. $m = \min\{k \in \mathbb Z^+ : \alpha_k = 1 \}$. Then since $y \in P$, $m \in \mathbb Z^+$, and $j_{\alpha,m} \in \mathbb N$ we have $3^m y \leq 3j_{\alpha,m} +1$ or $3^m y \geq j_{\alpha,m} + 2$ by \eqref{eqn:ex3.19-3}.
If $3^m y \leq 3j_{\alpha,m} +1$ then since $y = x(\alpha)$ we have by \eqref{eqn:ex3.19-2}\[ 3^m y \leq 3j_{\alpha,m} +1 \]\[ 3j_{\alpha,m} + \alpha_m + \delta_{\alpha,m} \leq 3j_{\alpha,m} + 1 \]\[ 1 + \delta_{\alpha,m} \leq 1 \]\[ \delta_{\alpha,m} \leq 0 \,. \]Since also we know that $\delta_{\alpha,m} \geq 0$ it has to be that $\delta_{\alpha,m} = 0$, which implies that every digit after $\alpha_m$ is zero so that $\alpha_m$ is the only digit that is one. But then we can form $\alpha’$ where\[
\alpha_k’ =
\begin{cases}
\alpha_k & \text{if $k < m$} \\
0 & \text{if $k=m$} \\
2 & \text{if $k > m$} \,.
\end{cases}
\]Clearly $x(\alpha’) = x(\alpha) = y$ and $\alpha’ \in A$.
If $3^m y \geq 3j_{\alpha,m} + 2$ then we again have by \eqref{eqn:ex3.19-2}\[ 3^m y \geq 3j_{\alpha,m} + 2 \]\[ 3j_{\alpha,m} + \alpha_m + \delta_{\alpha,m} \geq 3j_{\alpha,m} + 2 \]\[ 1 + \delta_{\alpha,m} \geq 2 \]\[ \delta_{\alpha,m} \geq 1 \,. \]Since we also know that $\delta_{\alpha,m} \leq 1$ it has to be that $\delta_{\alpha,m} = 1$, which means that $\alpha_k = 2$ for $k > m$, i.e. the base three representation of $x(\alpha)$ ends in infinitely many twos after the one. Then we can construct a terminating $\alpha’$ where\[
\alpha_k’ =
\begin{cases}
\alpha_k & \text{if $k < m$} \\
2 & \text{if $k=m$} \\
0 & \text{if $k > m$} \,.
\end{cases}
\]Again clearly $x(\alpha’) = x(\alpha) = y$ and $\alpha’ \in A$.
Thus in either case there is an $\alpha’ \in A$ where $y = x(\alpha) = x(\alpha’)$ so that $y \in x(A)$. Since $y$ was arbitrary this shows that $P \subseteq x(A)$, which completes the proof since it has been shown that $x(A) = P$.
Exercise 20
(By ghostofgarborg) Choose $\epsilon > 0$. Since $ p_n $ is Cauchy, we can choose an $N$ such that $d(p_m, p_n) < \frac \epsilon 2$ whenever $m, n > N$. Assume $p_{n_i} \to p$. Then there is an $M$ such that whenever $i > M$, $d(p_{n_i}, p) < \frac \epsilon 2$. For $n > N$, there is an $i > M$ such that $n_i > N$. Then \[ d(p_n, p) \leq d(p_n, p_{n_i}) + d(p_{n_i}, p) < \frac \epsilon 2 + \frac \epsilon 2 = \epsilon \] This implies that the sequence converges to $p$.
Exercise 21
(By ghostofgarborg) Pick $x_n \in E_n$ for each $n$. Since $ \{x_k\}_{k=n}^\infty \subset E_n$ and $\lim \operatorname{diam} E_n = 0$, $x_n$ is Cauchy. Since $X$ is complete, $x_n$ converges to a point $x$. Since $x$ is a limit point for each $E_n$ and each $E_n$ is closed, $x \in E_n$ for all $n$. Consequently, $ x \in \bigcap_{n=1}^\infty E_n$. There cannot be more than one point in this intersection, since that would contradict $\lim \operatorname{diam} E_n = 0$.
Exercise 22
(By ghostofgarborg) Since $G_1$ is open, we can find a neighborhood $E_1$ such that $\bar E_1 \subset G_1$, and $\operatorname{diam}E_1 < 1$ by letting $E_1 = N_\epsilon(x)$ for a sufficiently small $\epsilon$ around $x \in G_1$.
Assume $E_n$ is open, that $\bar E_n \subset G_n$, that $\bar E_{n} \subset \bar E_{n-1}$ and that $\operatorname{diam} E_n < \frac 1 n$. Since $G_{n+1}$ is dense in $X$ and open, $E_n \cap G_{n+1}$ is non-empty and open. We can therefore choose a neighborhood $E_{n+1}$ in the same manner as above such that $\operatorname{diam} E_{n+1} < \frac 1 {n+1}$, $\bar E_{n+1} \subset G_{n+1}$ and $\bar E_{n+1} \subset \bar E_n$. This gives us a sequence of sets with the desired properties.
By ex. 21, $\bigcap \bar E_n$ contains a point $x$. Since $x \in G_n$ for all $n$, $\bigcap E_n$ is non-empty as well, which is what we wanted to show.
Exercise 23
(By ghostofgarborg) By applying the triangle inequality, we see that \[ d(p_n, q_n) – d(p_m,q_m) \leq d(p_n, p_m) + d(q_m, q_n) \]By interchanging the roles of $m$ and $n$, we in fact get \[ |d(p_n, q_n) – d(p_m,q_m)| \leq d(p_n, p_m) + d(q_m, q_n) \]Let $\epsilon > 0$. Since $p_n$ and $q_n$ are Cauchy, we can find an $N$ such that $m, n > N$ implies that $d(p_n, p_m) < \frac \epsilon 2$ and $d(q_m, q_n) < \frac \epsilon 2$. Then \[ |d(p_n, q_n) – d(p_m,q_m)| \leq \epsilon \]This shows that $d(p_n, q_n)$ is Cauchy, hence convergent.
Exercise 24
(By ghostofgarborg)
(a) Let $\equiv$ be the relation. Assume $ p_n \equiv q_n$ and $q_n \equiv r_n$. We know that $d(p_n, p_n) \to 0$ whenever $p$ is Cauchy, so that $p_n \equiv p_n$. By the symmetry of $d$, it is clear that $q_n \equiv p_n$. By the triangle inequality,\[ d(p_n, r_n) \leq d(p_n, q_n) + d(q_n, r_n) \] which shows that $ d(p_n, r_n) \to 0$ and $p_n \equiv r_n$. This shows that $\equiv$ is an equivalence relation.
(b) Let $p_n \equiv p^\prime_n$. It suffices to show that $\lim d(p_n,q_n) = \lim d(p^\prime_n, q_n)$. \[ d(p_n, q_n) \leq d(p_n, p^\prime_n) + d(p^\prime_n, q_n) \]Consequently, since $d(p_n, p^\prime_n) \to 0$, $\lim d(p_n, q_n) \leq \lim d(p^\prime_n, q_n)$.By interchanging $p_n$ and $p^\prime_n$, we also get that $\lim d(p^\prime_n, q_n) \leq \lim d(p_n, q_n)$, which proves equality. $\Delta$ is therefore well-defined. We now need to show that it is a metric. It is clear that $\Delta$ is positive, and that $\Delta(P, Q) = 0$ iff $P = Q$. The symmetry of $\Delta$ follows from the symmetry of $d$. It remains to be shown that $\Delta$ satisfies the triangle inequality. \[ \Delta (P,R) = \lim_{n \to \infty} d(p_n, r_n) \leq \lim_{n \to \infty} d(p_n, q_n) + \lim_{n \to \infty} d(q_n, r_n) = \Delta(P, Q) + \Delta(Q, R) \](c) We first prove a lemma: Let $r_k$ be a sequence, and define the family of equivalence classes $Q_k = [q_k]$ by letting $q_k$ be constant sequences given by $q_{k,n} = r_k$ for all $n$. If $r_n$ is Cauchy, then $Q_k$ converges to the equivalence class $R = [r]$. To see this, choose an $\epsilon > 0$ and pick $N$ such that $d(r_k, r_\ell) < \epsilon$ whenever $k, \ell > N$. Then \[ \lim_{n \to \infty} d(q_{k,n}, r_n) = \lim_{n \to \infty} d(r_k, r_n) < \epsilon \]Consequently \[ \lim_{k \to \infty} \Delta (Q_k, R) = \lim_{k \to \infty} \lim_{n \to \infty} d(q_{k,n}, r_n) = 0 \]as desired.
Now for the main result, let $P_k = [p_k]$ be a Cauchy sequence in $X^*$. For each $k$, choose a number $N(k)$ such that $d(p_{k,m}, p_{k,n}) < \frac 1 {2^k}$ whenever $m, n > N(k)$, and let $r_k = p_{k,N(k)}$. We now want to show that $r$ is Cauchy: Choose an $\epsilon > 0$. First remember that $P_i$ is Cauchy, so that $$ \Delta(P_m, P_n) = \lim_k d(p_{m,k}, p_{n,k}) < \frac \epsilon 6$$ when the indices are sufficiently large. The convergence of that limit means that $d(p_{m,s}, p_{n,s}) < \frac \epsilon 3 $ whenever $s$ is sufficiently large. Also note that $\frac 1 {2^m} < \frac \epsilon 3$ and $\frac 1 {2^m} < \frac \epsilon 3$ whenever $m$ and $n$ are sufficiently large. Choose $m,n$ sufficiently large to fulfill these criteria simultaneously. Then \begin{align*}
d(r_m, r_n) &= d(p_{m, N(m)}, p_{n, N(n)}) \\
&\leq d(p_{m, N(m)}, p_{m,s}) + d(p_{m,s}, p_{n,s}) + d(p_{n,s}, p_{n, N(n)}) \\
&\leq \frac \epsilon 3 + \frac \epsilon 3 + \frac \epsilon 3 \\
&= \epsilon
\end{align*} So $r$ is Cauchy as desired.
This allows us to reach our desired conclusion: Define $Q_k$ in terms of $r$ as we did above. Now note that $\Delta(P_k, Q_k) < \frac 1 {2^k}$, so that $ \Delta(P_k, Q_k) \to 0$. Since $Q$ converges to $R$, so does $P$. Consequently, any Cauchy sequence in $X^*$ converges. This makes $X^*$ complete.
(d) We have\[ \Delta(P_p, P_q) = \lim_n d(p,q) = d(p,q)\](e) Let $R = [r]$ be any element of $X^*$. We have shown that $Q_k$ as defined above is a sequence in $X$ that converges to $R$. This implies that $X$ is dense in $X^*$.
Exercise 25
(By Dan kyp44 Whitman) The completion of $\mathbb Q$ in the manner described in Exercise 3.24 results in the real numbers. In fact this is one way to define the real numbers.
