PSET5-18.100B.tex

\documentclass[psamsfonts]{amsart}

%-------Packages---------
\usepackage{amssymb,amsfonts}
\usepackage[all,arc]{xy}
\usepackage{enumerate}
\usepackage{mathrsfs}

%--------Theorem Environments--------
%theoremstyle{plain} --- default
\newtheorem{thm}{Theorem}[section]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{quest}[thm]{Question}

\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}
\newtheorem{defns}[thm]{Definitions}
\newtheorem{con}[thm]{Construction}
\newtheorem{exmp}[thm]{Example}
\newtheorem{exmps}[thm]{Examples}
\newtheorem{notn}[thm]{Notation}
\newtheorem{notns}[thm]{Notations}
\newtheorem{addm}[thm]{Addendum}
\newtheorem{exer}[thm]{Exercise}

\theoremstyle{remark}
\newtheorem{rem}[thm]{Remark}
\newtheorem{rems}[thm]{Remarks}
\newtheorem{warn}[thm]{Warning}
\newtheorem{sch}[thm]{Scholium}

\makeatletter
\let\c@equation\c@thm
\makeatother
\numberwithin{equation}{section}

\bibliographystyle{plain}

\voffset = -10pt
\headheight = 0pt
\topmargin = -20pt
\textheight = 700pt

%--------Meta Data: Fill in your info------
\title{18.100B \\
Problem Set 5}

\author{John Wang}

\begin{document}

\maketitle


\section{Problem 3.1}

\begin{thm}
The convergence of $\{ s_n \}$ implies the convergence of $\{ | s_n | \}$. The converse is not true, however.
\end{thm}

\begin{proof}
We will assume that $\{ s_n \}$ is a convergent set in $\mathbb{R}$ because the norm is not defined in Rudin for any other metric space. Since $\{ s_n \}$ is a convergent sequence, it must be Cauchy. Therefore, there exists and $N$ such that $m,n \geq N$ implies that $d(s_m,s_n) < \epsilon$ for all $\epsilon > 0$. We can use the traingle inequality, then, to show the following:

\begin{eqnarray}
|s_n| &=& |(s_n + s_m) - s_m | \\
& \leq & |(s_n + s_m) - s_n| + | s_n - s_m| \nonumber \\
&=& |s_m | + d(s_n,s_m) \nonumber \\
&<& |s_m| + \epsilon \nonumber
\end{eqnarray}

This shows that $|s_n| - |s_m| < \epsilon$, which further implies that $d(|s_n|,|s_m|) < \epsilon$ for $m,n \geq N$. Thus, we see that the sequence $\{ | s_n | \}$ is Cauchy, and since it is in $\mathbb{R}$, it converges.

It is easy to show that the converse is not true, namely that the convergence of $\{ |s_n | \}$ does not imply the convergence of $\{ s_n \}$. Take the sequence defined by $s_n = (-1)^n$. Thus, we can see that $|s_n| = |(-1)^n| = 1$ is a constant sequence, and thus definitely converges. However, $s_n$ switches between $-1$ and $1$ and thus will never converge for any $n$. 
 
\end{proof}

\section{Problem 3.2}

\begin{thm}
We show that $\lim_{ n \to \infty} \sqrt{n^2 + n} - n = \frac{1}{2}$.
\end{thm}

\begin{proof}
We multiply through by the conjugate to obtain the following:
\begin{eqnarray}
\lim_{ n \to \infty} \sqrt{n^2 + n} - n &=& \lim_{ n \to \infty} \sqrt{n^2 + n} - n \frac{\sqrt{n^2 + n} + n}{\sqrt{n^2 + n} + n} \\
&=& \lim_{n \to \infty} \frac{n^2 + n - n^2}{\sqrt{n^2 + n} + n} \nonumber \\
&=& \lim_{n \to \infty} \frac{n}{ n \sqrt{\frac{n^2 + n}{n^2} + n}} \nonumber \\
&=& \lim_{n \to \infty} \frac{1}{ \sqrt{1 + \frac{1}{n}} + 1} \nonumber \\
&=& \frac{1}{\sqrt{1} + 1} \nonumber \\
&=& \frac{1}{2} \nonumber
\end{eqnarray}
\end{proof}

\section{Problem 3.3}

\begin{thm}
If $s_1 = \sqrt{2}$ and $s_{n+1} = \sqrt{2 + \sqrt{s_n}}$ for $ n = 1,2,3, \ldots$ then $\{ s_n \}$ converges and $s_n < 2$ for all $n \in \mathbb{N}$. 
\end{thm}

\begin{proof}
We know that $0 < \sqrt{2} < 2$, so we have $0 < s_1 < 2$. Moreover, if we add 2 to each side of the inequality, we obtain $2 < 2 + \sqrt{2} < 4$. Taking the square roots, we obtain $\sqrt{2} < \sqrt{2 + \sqrt{2}} < 2$. Adding 2 to each side of this, we obtain $2 + \sqrt{2} < 2 + \sqrt{2 + \sqrt{2}} < 4$. Taking square roots, we have $\sqrt{2} < \sqrt{ 2 + \sqrt{2 + \sqrt{2}}} < 2$. We can repeat the process infinitely many times and notice that $s_1 = \sqrt{2}, s_2 = \sqrt{2 + \sqrt{2}}, s_3 = \sqrt{2 + \sqrt{2 + \sqrt{2}}}, \ldots$. Thus, we see that $s_1 < s_2 < s_3 < \ldots < 2$. We have therefore shown that $\{ s_n \}$ is a monotonically increasing sequence that is bounded because $s_n < 2$ $ \forall n \in \mathbb{N}$. By a theorem in Rudin, we know that $\{ s_n \}$ must converge.
\end{proof}

\section{Problem 3.4}

\begin{thm}
Consider the sequence $\{ s_n \}$ defined by $s_1 = 0$ with $s_{2m} = \frac{s_{2m} - 1}{2}$ and $s_{2m+1} = \frac{1}{2} + s_{2m}$. The lower limit of the sequence is $\frac{1}{2}$ and the upper limit is $1$. 
\end{thm}

\begin{proof}
If we compute the sequence, then we see the following, starting at $s_1 = 0$:

\begin{equation}
\{ s_n \} = 0, 0, \frac{1}{2}, \frac{1}{4}, \frac{3}{4}, \frac{3}{8}, \frac{7}{8}, \ldots
\end{equation}

We can use induction to derive the following formulas:

\begin{equation*}
\text{Even n} \rightarrow s_n = \frac{2^{\frac{n}{2}-1} - 1 }{2^{\frac{n}{2} -1}} = \frac{1}{2} - \frac{1}{2^{\frac{n}{2}-1}} \hspace{1cm} \text{Odd n} \rightarrow s_n = \frac{2^{\frac{n-1}{2}} - 1}{2^{\frac{n-1}{2}}} = 1 - \frac{1}{2^n}
\end{equation*}

We can see that for even $n$, we have $s_n < \frac{1}{2}$ and for odd $n$, we have $s_n < 1$. It is clear by inspection that they are subsequential limits. Moreover, we can show that these are the only two subsequential limits of $\{ s_{n} \}$. This is because each subsequence $\{ s_{n_k} \}$, in order to converge, must contain either a finite number of even terms or a finite number of odd terms. There must exist some $N$ such that $n_k \geq N$ implies that each subsequent $s_{n_k}$ is either all odd or all even. If this is not the case, and for $n_k \geq N$ we have $s_{n_k}$ odd (even) and $s_{n_{k+1}}$ even (odd), then $d(s_{n_k},s_{n_{k+1}}) = \frac{1}{2}$ because $s_{2m+1} - s_{2m} = \frac{1}{2}$. This would imply that the subsequence does not converge. Thus, it is clear that $\{\frac{1}{2},1 \}$ are the only two subsequential limits. Thus, we have that the upper bound $s^{*} = \sup \{ \frac{1}{2}, 1 \} = 1$ and the lower bound $s_{*} = \inf \{ \frac{1}{2},1 \} = \frac{1}{2}$. 

\end{proof}

\section{Problem 3.20}
\begin{thm}
Suppose $\{ p_n \}$ is a Cauchy sequence in a metric space $X$, and some subsequence $\{ p_{n_i} \}$ converges to a point $p \in X$. Then the full sequence $\{ p_n \}$ converges to $p$. 
\end{thm}

\begin{proof}
Since we know that $\{ p_{n_i} \}$ converges, we know that there exits an $N_0$ such that $n_i \geq N_0$ implies $d(p_{n_i}, p) < \epsilon$ for all $\epsilon > 0$. Since the sequence $\{ p_n \}$ is Cauchy, there exists an $M$ such that $n \geq M$ and $m \geq M$ implies $d(p_n, p_m) < \epsilon$ for all $\epsilon > 0$. By the triangle inequality, we obtain for $n, n_i \geq \max \{ N_0, M \} $ that

\begin{eqnarray}
d(p_n,p) &\leq& d(p_n, p_{n_i}) + d(p_{n_i},p) \\
&<& \epsilon + \epsilon = 2 \epsilon \nonumber
\end{eqnarray}

We know that $d(p_n, p_{n_i} ) < \epsilon$ by the fact that $\{ p_n \}$ is Cauchy, because $p_{n_i} \in \{ p_n \}$ as it $p_{n_i}$ part of a subsequence of $\{ p_n \}$. We obtain $d(p_{n_i},p) < \epsilon$ because the subsequence $\{ p_{n_i} \}$ converges to $p$. Thus, since $\epsilon$ is arbitrary, we obtain that the full sequence $\{ p_n \}$ converges to $p$.
\end{proof}

\section{Problem 3.21}
\begin{thm}
If $\{ E_n \}$ is a sequence of closed, nonempty, and bounded sets in a complete metric space $X$, if $E_n \supset E_{n+1}$, and if $\lim_{n \to \infty} \text{diam} E_n = 0$, then $\bigcap_1^\infty E_n$ consists of exactly one point. 
\end{thm}

\begin{proof}
Suppose $\{ p_n \}$ is any sequence with $p_n \in E_n$. Then the assumption that $\lim_{n \to \infty} \text{diam} E_n = 0$ means that there exists an $N$ such that for all $\epsilon > 0$, we have $d(\text{diam} {E_n},0) < \epsilon$ for $n \geq N$. Thus, we have $\text{diam} E_n < \epsilon$. Moreover, since we have $E_m \supset E_n$ for $m \geq n \geq N$, we know that $ d(p_n, p_m) < \text{diam} E_n < \epsilon $ for $p_n \in E_n$ and $p_m \in E_m$. This implies that $\{ p_n \}$ is Cauchy, and since we have assumed that $X$ is complete, $\{ p_n \}$ must converge to some limit $p$ in $X$. Moreover, since $p$ is the limit of $\{ p_n \}$, it is also a limit point of $ E_n$. This is because for $n > N$, $ d(p_n, p) < \epsilon $ which implies that there exists a point $p_n \in E_n$ for every neighborhood of $p$. Since we assumed each $E_n$ is closed, we know that $p$ must be contained in each $E_n$. Thus, we know that $ p \in \bigcap_1^\infty E_n$.

It is clear that there are no more elements in  $\bigcap_1^\infty E_n$. Assume by contradiction that there exists a $q \neq p$ such that $q \in \bigcap_1^\infty E_n $. Since $q \neq p$, we know that $d(p,q) > 0$ by definition of a metric space. Since both $p$ and $q$ belong to $E_1, E_2, \ldots$ we see that $ \sup d(p_n,q_n) > 0$ for $p_n, q_n \in E_n$. Thus, the diameter $\text{diam} E_n > 0$ for all $n$. Thus shows that $\lim_{n \to \infty} \text{diam} E_n \neq 0$, which is a contradiction of our assumption. Thus, the set $\bigcap_1^\infty E_n$ contains exactly one element.
\end{proof}

\section{Problem 3.23}

\begin{thm}
Suppose $\{ p_n \}$ and $\{ q_n \}$ are Cauchy sequences in a metric space $X$. Show that the sequence $\{ d(p_n, q_n) \}$ converges. 
\end{thm}

\begin{proof}
Since $\{ p_n \}$ is a Cauchy sequence, we know that there exists some $N$ such that $d(p_n,p_m) < \epsilon$ for all $\epsilon > 0$ and $m,n \geq N$. Since $\{q_n \}$ is Cauchy, we know there exists some $M$ such that $d(q_n,q_m) < \epsilon$ for all $\epsilon > 0$ and $m,n \geq N$. Using the triangle inequality, we find that 

\begin{eqnarray}
d(p_n,q_n) &\leq& d(p_n, p_m) + d(p_m, q_n) \\
&\leq& d(p_n,p_m) + d(p_m, q_m) + d(q_m, q_n) \nonumber \\
&<& 2 \epsilon + d(p_m, q_m) \nonumber \\
d(p_n,q_n) - d(p_m,q_m) &<& 2 \epsilon 
\end{eqnarray}

This implies that $d( d(p_n,q_n), d(p_m,q_m) ) = |d(p_n,q_n) - d(p_m, q_m) | < 2 \epsilon$ for all $\epsilon >0$ and $m,n \geq N$. Thus we know that $\{ d(p_n,q_n) \}$ is a Cauchy sequence. Since $\mathbb{R}$ is complete, we know that $\{ d(p_n,q_n) \}$ converges.
\end{proof}


\end{document}