path: root/lacey/hw3.tex

\font\bigbf=cmbx12 at 24pt
\newfam\bbold
\font\bbten=msbm10
\font\bbsev=msbm7
\font\bbfiv=msbm5
\textfont\bbold=\bbten
\scriptfont\bbold=\bbsev
\scriptscriptfont\bbold=\bbfiv
\def\bb#1{{\fam\bbold #1}}
\input color

\newcount\pno
\def\tf{\advance\pno by 1\smallskip\bgroup\item{(\number\pno)}}
\def\endtf{\egroup\medskip}
\def\false{\centerline{TRUE\qquad{\color{blue} FALSE}}}
\def\true{\centerline{{\color{blue} TRUE}\qquad FALSE}}

\newcount\qno
\long\def\question#1{\ifnum\qno=0\else\vfil\eject\fi\bigskip\pno=0\advance\qno by 1\noindent{\bf Question \number\qno.} {\it #1}}

\def\proof{\medskip\noindent{\it Proof.}\quad}
\def\endproof{\leavevmode\hskip\parfillskip\vrule height 6pt width 6pt
depth 0pt{\parfillskip0pt\medskip}}

\let\bu\bullet

{\bigbf\centerline{Holden Rohrer}\bigskip\centerline{MATH 4317\qquad HOMEWORK \#3}}

\question{Answer True or False. No justification is needed.}

\tf
A sequence of reals that is bounded above converges.
\endtf

\false

\tf
A monotone sequence of reals converges.
\endtf

\false

\tf
A sequence of reals that is bounded above and is monotone converges.
\endtf

\false

\tf
If $\{x_n\}$ is a sequence, and $p_1=2, p_2=3, p_3=5,\ldots$ are the
primes listed in increasing order, then $\{x_{p_k}\}$ is a subsequence.
\endtf

\true

\tf
If $\{x_n\}$ is a sequence which converges, and
$p_1=2,p_2=3,p_3=5,\ldots$ are the primes listed in increasing order,
then $\{x_{p_k}\}$ converges.
\endtf

\true

\tf
If $\{x_n\}$ is a sequnce, then $\{x_{n+(-1)^n}\}$ is a subsequence.
\endtf

\false

\tf
The rationalso are closed under addition, multiplication, and division.
And a sequence of rationals that is convergent converges to a rational.
\endtf

\false

\tf
The supremum of the empty set is $\sup\emptyset = -\infty.$
\endtf

\true

\tf
If non-empty set $S$ has supremum $\pi,$ then there are infinitely many
elements $s\in S$ with $\pi-1/100<s\leq\pi.$
\endtf

\false

\question{Show directly, from the definition, and using elementary
methods that the three sequences below are Cauchy.}

\item{(1)} $\{1/n : n\in\bb N\}$

\proof
Let $\epsilon > 0.$
Choose $N \in\bb N$ such that $N > 1/\epsilon > 0.$

Let $m,n > N.$
$$0 < 1/m, 1/n < 1/N < \epsilon.$$

Subtracting,
$$-\epsilon < 1/n - 1/m < \epsilon \Longrightarrow |1/n-1/m| <
\epsilon,$$
giving us that the sequence is Cauchy.
\endproof

\item{(2)} $\{{3n-1\over 2n+5} : n\in\bb N\}$

\proof
$$a_n := {3n-1\over 2n+5} = {3n+7.5-8.5\over 2n+5} = {3\over 2} -
{8.5\over 2n+5}.$$

Let $\epsilon > 0.$
We choose $N = {4.25\over\epsilon}-2.5,$ and for all $n,m>N,$
$$|a_n-a_m| = \left|\left({3\over 2} - {8.5\over 2n+5}\right) -
\left({3\over 2} - {8.5\over 2m+5}\right)\right| = \left|{8.5\over 2n+5}
- {8.5\over 2m+5}\right| < {8.5\over 2N+5} = \epsilon,$$
with the inequality found by maximizing the absolute value variable (we
might also show this inequality by starting from $n,m > N$ and
rearranging).
%TODO: may be worth improving

We have shown the sequence is Cauchy.
\endproof

\item{(3)} Let $\{s_n\}$ be any sequence of digits with
$s_n\in\{0,1,2\}$ for all integers $n.$ Show that the sequence $\{x_n\}$
is Cauchy, where $x_n = \sum_{m=1}^n {s_m\over 3^m}.$

\proof
Let $\epsilon > 0.$
Pick $N$ such that $3^{-N} < \epsilon.$
We will show that $|x_n-x_m| < \epsilon$ for all $n,l > N.$
$$x_n = \sum_{m=1}^n {s_m\over 3^m} = \sum_{m=1}^N {s_m\over 3^m} +
\sum_{m=N}^n {s_m\over 3^m} \leq \sum_{m=1}^N {s_m\over 3^m} +
\sum_{m=1}^N {2\over 3^m} = \sum_{m=1}^N {s_m\over 3^m} + 3^{-N} -
3^{-n} \leq \sum_{m=1}^N {s_m\over 3^m} + 3^{-N},$$
and, eliminating the second term, we also get $x_n \geq \sum_{m=1}^N.$
Taking these together,
$|x_m-x_n| \leq 3^{-N} = \epsilon.$

\endproof

\question{}

\item{(1)} Show that the sequence below converges

$$\sqrt 2, \sqrt{2+\sqrt 2}, \sqrt{2 + \sqrt{2 + \sqrt 2}}, \ldots$$

\proof
Let $a_1 = \sqrt 2$ and for $n\geq 1,$ that $a_{n+1} = \sqrt{2+a_n}.$

We will show by induction that it is bounded by 2 and, later, that it is
monotonically increasing.

Clearly, $\sqrt 2 < 2,$ so $a_1 < 2.$
For $k\geq 1,$ we assume $a_k < 2,$ then $2+a_k < 4,$ so $\sqrt{2+a_k} <
2,$ or in other words, $a_{k+1} < 2.$
We have shown the sequence is bounded above.

$0 < a_k < 2,$ so $a_k-2 < 0$ and $a_k+1 > 0.$
Therefore,
$$(a_k-2)(a_k+1) = a_k^2 - a_k - 2 < 0,$$
Rearranging, and noting that both sides are positive, so the square root
function can be used and is monotonically increasing so as not to change
the direction of the inequality,
$$a_k < \sqrt{a_k+2} = a_{k+1},$$ showing that our sequence is
strictly monotonically increasing, so the set is bounded below by the
first element.

By the Monotone Convergence Theorem, the sequence converges.
\endproof

\item{(2)} Does the sequence below converge? If so, to what?

$$\sqrt 2, \sqrt{2\sqrt 2}, \sqrt{2\sqrt{2\sqrt 2}}, \ldots$$

\proof
Yes, this sequence converges to 2 (heuristically, $\sqrt{2x} = x$ has
roots 0 and 2, and all elements are positive)

We will show it is monotone, bounded by 2, and that the limit of the set
cannot be less than 2.
Let $x_1 = \sqrt 2$ and $x_n = \sqrt{2x_{n-1}}$ otherwise.

$x_1 = \sqrt 2 < 2,$ and assuming $x_k < 2,$ then $2x_k < 4,$ and
$\sqrt{2x_k} = x_{k+1} < 2.$
This shows the sequence is bounded by 2.

All elements are positive.
Specifically, $x_1 = \sqrt 2 > 0,$ and $\sqrt{2x_n}>0$ where $x_n>0,$ giving
the inductive step.
We have also already shown $2 > x_n,$ so $2x_n > x_n^2,$ so finally
$\sqrt{2x_n} = x_{n+1} > x_n,$ giving monotonicity.

To show the limit cannot be less than 2, assume for the sake of
contradiction that the limit is $1.5 < 2-\mu < 2$ (or, phrased
otherwise, $0 < \mu < .5$)

By the definition of convergence, we may find $x_n > 2-1.1\mu.$
We will show $\sqrt{2x_n} = x_{n+1} > 2-\mu.$
Note that $\mu < .9,$ so $.9-\mu > 0,$ and $\mu > 0.$
Therefore,
$$(.9-\mu)\mu = .9\mu-\mu^2 > 0 \Rightarrow 2-1.1\mu > 2-2\mu+\mu^2/2
\Rightarrow 2(2-1.1\mu) > (2-\mu)^2 \Rightarrow \sqrt{2(2-1.1\mu)} =
x_{n+1} > 2-\mu.$$
we have thus shown that the sequence may exceed the limit, instructing
us that the limit is 2.

\endproof

\question{}

\item{(1)} In Section 1.4, we used the Axiom of Completeness (AoC) to
prove the Archimedean Property of $\bb R$ (Theorem 1.4.2). Show that the
Monotone Convergence Theorem can also be used to prove the Archimedean
Property without making any use of AoC.

\proof

The sequence $a_n = n$ is monotone.

We will show the Archimedean Property by contradiction.
Let there be $x\in\bb R$ such that there is no $n\in\bb N$ satisfying
$n>x.$
Therefore, $a_n$ is bounded and converges to some number $a < n$ by the
Monotone Convergence Theorem.
Let $0 < \epsilon < 1/2.$

From the definition of convergence, there exists $N$ such that for all
$m\geq N,$ that $|a-a_N| < \epsilon.$
Rewriting, $a_N-\epsilon < a < a_N+\epsilon,$ and from our inequality
about $\epsilon,$
$$a < a_N+1/2 \to a < a_{N+1}-1/2,$$
which contradicts our convergence statement.

\endproof

\item{(2)} Use the Monotone Convergence Theorem to supply a proof for
the Nested Interval Property (Theorem 1.4.1) that doesn't make use of
AoC. These two results suggest that we could have used the Monotone
Convergence Theorem in place of AoC as our starting axiom for building a
proper theory of the real numbers.

\proof
Let $I_i = [a_i,b_i]$ be a sequence of nonempty closed intervals such
that $$I_1\supseteq I_2 \supseteq I_3 \supseteq \cdots.$$
$a_i$ is a weakly monotone increasing sequence because if $a_{i+1}<a_i,$
then $a_{i+1}\in I_{i+1},$ but $a_{i+1}\not\in I_i,$ violating the
interval condition.
It is clearly bounded by $b_1$ because if $a_i > b_1,$ then
$I_i\not\subseteq I_1,$ and $I_1$ is nonempty.

The Monotone Convergence Theorem tells us that $a_i$ converges to some
$x\geq a_i$ because $a_i$ is strictly increasing.

For the sake of contradiction, let there be $b_k < x.$
Let $\epsilon = x-b_k.$
Because $a_i$ converges to $x,$ there must be for some $i>k,$ an $a_i >
x-\epsilon = b_k,$ violating the definitions of our intervals.
We have thus obtained $x\in [a_i, b_i],$ for all $i\in\bb N,$ and
therefore in the intersection of these intervals.
\endproof

\question{Exercise 2.4.7 (Limit Superior). Let $(a_n)$ be a bounded
sequence.}

\item{a)} Prove that the sequence defined by $y_n = \sup\{a_k : k\geq
n\}$ converges.

\proof
$y_n \geq y_{n+1},$ because $\{a_k : k\geq n\}\supseteq\{a_k : k \geq
n+1\},$ so any upper bound for the former set is an upper bound for the
latter.
It is monotone and bounded by whatever bound $(a_n)$ is bounded by, so
it must converge by the Monotone Convergence Theorem.
\endproof

\item{b)} The limit superior of $(a_n)$ or $\limsup a_n,$ is defined
by $\limsup a_n = \lim y_n,$ where $y_n$ is the sequence from part
$(a)$ of this exercise. Provide a reasonable definition for $\liminf
a_n$ and briefly explain why it always exists for any bounded sequence.

\proof
We can define $$\liminf a_n := -\limsup (-a_n).$$
If $|a_n| < b$ for some $b,$ then $|-a_n| = |a_n| < b$ too.
Clearly, this exists because $(-a_n)$ is also a bounded sequence where
$\limsup$ exists.

Also, this is equivalent to the more intuitive definition
$$\liminf a_n := \lim(\inf\{a_k : k\geq n\})$$ because the lower bound of that set maps
onto the upper bound of its negation.
This would also exist because the infimum would be monotonically
increasing and bounded in the same way.
\endproof

\item{c)} Prove that $\liminf a_n \leq \limsup a_n$ for every bounded
sequence, and give an example of a sequence for which the inequality is
strict.

\proof
For all sets of bounded numbers $S_k = \{a_k : k\geq n\},$
we know $\inf S_k \leq \sup S_k$ (the lower bound must be below the
upper bound).
By the Nested Interval Property, and because the infimum and supremum
should create a set of nested intervals (they are increasing and
decreasing respectively), we should have some $x\in [\liminf a_n,
\limsup a_n],$ meaning $\liminf a_n \leq \limsup a_n.$
The inequality is strict for the sequence $(0)_{n\in\bb N}.$
\endproof

\item{d)} Show that $\liminf a_n = \limsup a_n$ if and only if $\lim
a_n$ exists. In this case, all three share the same value.

\proof
$(\Rightarrow)$
Let $x := \liminf a_n = \limsup a_n.$
Let $\epsilon > 0.$

Using the definition of convergence, for some $N,$
$$|\inf\{a_k : k \geq N\} - x| < \epsilon \Rightarrow x > \inf\{a_k :
k\geq N\}-\epsilon \Rightarrow x > a_j-\epsilon,$$
for all $j\geq N.$
Similarly, we can obtain $a_j+\epsilon > x.$
This means for all $j>N,$ the sequence converges as $|a_j-x| <
\epsilon,$ so $\lim a_n = x$ exists.

$(\Leftarrow)$
Let $\lim a_n = x$ exist.
Let $\epsilon > 0.$
We must have $N$ such that for all $n > N,$ $|a_n - x| < \epsilon.$
That means $$\limsup a_n \leq \sup\{a_n : n > N\} < x+\epsilon,$$ and a
similar lower limit for $\liminf.$
$|\limsup a_n - \liminf a_n| < 2\epsilon,$ and by the "give me some
room" principle, $\limsup a_n = \liminf a_n = x.$
\endproof

\bye