aboutsummaryrefslogtreecommitdiff
path: root/lacey/hw3.tex
blob: 93a275a35c4a692d7665b9bcd9b172ec54aadf92 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
\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