\magnification=\magstep1
\centerline{MATH 242 -- Principles of Analysis}
\centerline{Solutions for Problem Set 3 -- due:  Feb. 15}
\baselineskip=15pt
\bigskip
\noindent
{\it `A` Section}
\bigskip
\item{1.} A set $B$ is said to be {\it finite} if there is some $n \in {\bf N}$ (the number of
elements in $B$), and a one-to-one onto mapping $f : \{1,2,\ldots, n\} \to B$.  (Intuitively, we
think that $f(1) = b_1, f(2) = b_2, \ldots$ ``counts through'' all the elements of $B$ one at 
a time without repetitions and without missing any elements in $B$.)
For each of the following sets, either show $B$ is finite by determining the $n$ and constructing a mapping
$f$ as above, or say why no such mapping exists.
\itemitem{a.} $B = \{r = p/q \in {\bf Q} \mid 1 \le q \le 5, 0 < r < 1\}$
\itemitem{} {\it Solution:}  The distinct elements of $B$ are given by 
$$B = \{1/2, 1/3, 2/3, 1/4, 3/4, 1/5, 2/5, 3/5, 4/5\}$$ 
Hence we have $n = 9$, and we can construct the required mapping by taking $f(1) = 1/2$, $f(2)=1/3$, and
so on up to $f(9) = 4/5$.   
\itemitem{b.} $B = \{r = p/q \in {\bf Q} \mid 0 < r < 1\}$
\itemitem{} {\it Solution:}  This set is not finite, because it contains, for instance all the elements
$1/n$ for $n \ge 1$.  Since ${\bf N}$ is not a finite set, $B$ is not finite either.
\itemitem{c.} $B = \{n \in {\bf Z} \mid |n| \le 10^9\}$
\itemitem{} {\it Solution:}  This is a finite set with $n = 2\times 10^9 + 1$ elements, since 
$$B = \{-10^9, \ldots, -3,-2,-1,0,1,2,3, \ldots, 10^9 \}.$$  
There are many correct
mappings $f$.  Perhaps the most useful way to write one down is to alternate back and forth between
positive and negative elements like this $f(1) = 0$, $f(2) = 1$, $f(3) = -1$, $f(4) = 2$, $f(5) = -2$, etc.  The
general pattern is
$$f(n) = \cases{{1 - n\over 2} & if $n$ is odd\cr
                {n \over 2} & if $n$ is even\cr}$$
\item{2.}  Which of the following sequences converge to 0?  Explain your answers.
\itemitem{a.}  $\{x_n\}$, where
$$x_n = \cases{e^n & if $n \le 1000$\cr
               e^{-n} & if $n > 1000$\cr}$$
\itemitem{} {\it Solution:}  This does converge to $0$ since the part of the sequence
starting after $n = 1000$ converges to $0$.  In other words, given any $\varepsilon > 0$,
we can always take $n_0 > 1000$ and then the initial segment of the sequence does not
matter.  Since $e^{-1} < 1$, the sequence with $e^{-n} = (e^{-1})^n$ for $n \ge 1000$ does converge to 
zero by a result shown in class.
\itemitem{b.}  $\{y_n\}$, where
$$y_n = \cases{1 & if $n$ is evenly divisible by $1000$ \cr
               {1\over n} & if $n$ is not evenly divisible by $1000$\cr}$$
\itemitem{}  {\it Solution:}  This sequence does not converge to $0$ since there
are arbitrarily large numbers $n$ that are divisible by $1000$.  Hence
with $\varepsilon = 1$, for all $n_0$, there exist $n > n_0$ with $|x_n - 0| \ge \varepsilon = 1$.
\itemitem{c.}  $\{z_n\}$, where
$$z_n = \cases{n & if $n$ is a Fermat prime number (look up on Wikipedia)\cr
               {(-1)^n\over n^2} & if $n$ is not a Fermat prime number\cr}$$
\itemitem{} {\it Solution:} The portion of the sequence for $n$ equal to some
Fermat prime is clearly {\it not tending to zero}.   However, the only reasonable answer
here is that {\it no one knows!}  Fermat primes are prime numbers of the form $p = 2^{2^n} + 1$,
like $17 = 2^{2^2} + 1$.  There are only 5 known Fermat primes and all the numbers
of the form $2^{2^n} + 1$ after the largest known prime that have been factored
successfully are composite (not prime).  But there is no proof known
that those five are the only ones.  Hence the convergence of this sequence is an open
question in mathematics(!)
\bigskip
\item{3.}  Let $f(x) = [x]$ be the greatest integer function, defined as $[x] = $ the greatest integer $\le x$.
\itemitem{a.}  If $x_n \to a$, does it follow that $[x_n] \to [a]$?  Prove or give a counterexample.
\itemitem{}  This is not true.  For instance, let $x_n = 1-1/n \to a = 1$.  But
$[x_n] = 0$ for all $n$, while $[a] = 1$.
\itemitem{b.}  If $[x_n] \to [a]$, does it follow that $x_n \to a$?  Prove or give a counterexample.
\itemitem{}  This is not true either.  For instance let $x_n = {1\over 2}$ for all $n\ge 1$.  Then
$[x_n] \to 0 = [0]$.  But $x_n$ does not converge to $0$.   
\item{4.}
\itemitem{a.}  Suppose that $x_n \to e$ (the base of the natural logarithm).  Show that there exists
an $n_0$ such that $x_n < 3$ for all $n \ge n_0$.
\itemitem{}  {\it Solution:}  $e \doteq 2.71828 < 3$, so $3 - e > 0$.  Applying the definition of 
convergence of the sequence $x_n$ with $\varepsilon = 3 - e$, we see that there exists
an $n_0$ such that $|x_n - e| < 3 - e$ for all $n \ge n_0$.  However, $|x_n - e| < 3 - e$
is equivalent to $e - 3 < x_n - e < 3 - e$.  Adding $e$ to both sides of the second 
inequality here shows $x_n < 3$ for all $n \ge n_0$.     
\itemitem{b.}  Suppose $x_n \to 6$ and $y_n \to 9$.  Show that there exists an $n_0$ such that
$x_n + y_n > 14$ for all $n \ge n_0$.
\itemitem{} {\it Solution:}  The idea is similar to what we did for part a.  Since $x_n \to 6$, if 
we take $\varepsilon = 1/2$ (or any smaller positive number), 
there must be an $n_{0,x}$ such that $x_n > {11\over 2}$ for all
$n\ge n_{0,x}$.  Similarly, there exists an $n_{0,y}$ such that $y_n > {17\over 2}$ for all 
$n \ge n_{0,y}$.  Hence if $n_0 = \max(n_{0,x}, n_{0,y})$, then $n \ge n_0$ implies
$x_n + y_n > {11\over 2} + {17 \over 2} = 14$. 
\bigskip
\noindent
{\it `B` Section}
\bigskip
\item{1.}
\itemitem{a.}  Prove that $\sqrt{5}$ is an irrational number.
\itemitem{} {\it Solution:}  Suppose $\sqrt{5} = {m\over n}$ in lowest terms.  
Then $m^2 = 5n^2$, which shows that $5$ must divide $m^2$.  Since $5$ is prime, this
implies that $5$ divides $m$, so $m = 5k$ for some integer $k$. But then we have
$25k^2 = 5n^2$, so $5k^2 = n^2$.  The same reasoning shows that $n$ must also 
be divisible by $5$.  But that contradicts the fact that the fraction $m/n$
was supposed to be in lowest terms.
\itemitem{b.}  If $r \ne 0$ and $s$ are rational numbers, show that $r\sqrt{5} + s$ is an irrational
number.
\itemitem{} {\it Solution:}  The set of rational numbers ${\bf Q}$ is closed under
addition and multiplication.  So if $r \sqrt{5} + s = t\in {\bf Q}$, then 
we get $\sqrt{5} = {t - s\over r} \in {\bf Q}$.  This is a contradiction to 
what was proved in part a.
\itemitem{c.} If $x = r\sqrt{5} + s$ and $y = r'\sqrt{5} + s'$ are two numbers as in part b, what
can be said about $x + x'$ and $xx'$?  Are they irrational too?
\itemitem{} {\it Solution:}  Nothing can be said here since there are cases where these are
rational and others where they are irrational.  For instance, if $x = \sqrt{5}$ and $y = -\sqrt{5} + 1$, 
then $x + y = 1 \in {\bf Q}$.  But if $x = \sqrt{5} = y$, then $x + y = 2\sqrt{5} \notin {\bf Q}$, by part a.
Similarly, if $x = \sqrt{5} + 1$ and $y = -\sqrt{5} + 1$, then $xy = -4\in {\bf Q}$.  But
if $x = \sqrt{5} + 1 = y$, then $xy = 6 + 2\sqrt{5} \notin {\bf Q}$, by part a again. 
\item{2.}  Let $A$ and $B$ be two nonempty sets of real numbers. 
\itemitem{a.}  Assume that $x \le y$ for all $x \in A$
and $y\in B$.  Show that ${\rm lub}\ A$ and ${\rm glb}\ B$ must exist.
\itemitem{} {\it Solution:}  Any element of $B$ is an upper bound for $A$.  Hence by the lub axiom, 
$A$ has a least upper bound.  Similarly, any element of $A$ is a lower bound for $B$, 
so $B$ has a greatest lower bound.
\itemitem{b.} Under the same assumptions as in part a, show that ${\rm lub}\ A \le {\rm glb}\ B$.
\itemitem{} {\it Solution:}  (By contradiction.) Suppose that the contrary inequality is true:
$a = {\rm lub}\ A > {\rm glb}\ B = b$.  By definition, that would say that the number $a = {\rm lub}\ A$
is {\it not} a lower bound for $B$ and similarly, $b = {\rm glb}\ B$ is {\it not} an upper bound for $A$.  
Hence by definition, there exist $x \in A$ such that $b < x \le a$.  But then $x$ is not a lower
bound for $B$, so there exists $y \in B$ with $b \le y < x$.   But this 
contradicts the assumption that $x \le y$ for all $x \in A$ and $y \in B$.  Hence
the desired statement must be true.    
\itemitem{c.} Now assume that $A,B$ are bounded subsets of ${\bf R}$.
Is it true that ${\rm lub}\ A \le {\rm glb}\ B$ implies that $x \le y$ for all $x \in A$
and $y\in B$?  Prove or give a counterexample.
\itemitem{} {\it Solution:}  This is true.  Write $a = {\rm lub}\ A$ and $b = {\rm glb}\ B$.
By definition, every $x \in A$ satisfies $x \le a$ and similarly every $y \in B$ satisfies
$b \le y$.  But then it follows that $x \le a \le b \le y$.  Hence by transitivity, 
$x \le y$.  
\item{3.}  Let $A$ be a bounded set of real numbers and let $B = \{kx\mid x \in A\}$, where
$k < 0$ is a strictly negative number.  Show that $B$ is also bounded.  Then, determine formulas
for computing  ${\rm lub}\ B$
and ${\rm glb}\ B$ in terms of ${\rm lub}\ A$ and ${\rm glb}\ B$, and prove your assertions.
\item{} {\it Solution:}   First, if $A$ is bounded, there exist real numbers $m,M$ such 
that $m \le x \le M$ for all $x \in A$.  Then since $k < 0$, we have $km \ge kx \ge kM$.
But this shows that $B$ is also bounded (below by $kM$ and above by $km$).  
 The general statements here are that (because $k < 0$), 
${\rm lub}\ B = k\cdot {\rm glb}\ A$ and vice versa ${\rm glb}\ B = k\cdot {\rm lub}\ A$.
We will prove the first one of these (the other is similar; the proof consists of 
reversing some inequalities and changing glbs to lubs.  So let $\ell = {\rm glb}\ A$.  Then
$\ell \le x$ for all $x \in A$.  Hence since $k < 0$, $k\ell \ge k\cdot x$ for 
all $x \in A$.  But this shows that $k\cdot \ell$ is an upper bound for $B$.  Now let 
$m$ be any other upper bound for $B$, so $k x \le m$ for all $x \in A$.  This implies
$x \ge m/k$ for all $x \in A$ since.  But then $m/k$ is a lower bound for $A$.  Since $\ell$
was the greatest lower bound for $A$, $m/k \le \ell$.  But that implies $m \ge k\ell$.  
Therefore, $k\ell$ is the least upper bound for $B$.      
\item{4.}  Determine whether each of the following series converge and prove your assertions using 
the $\varepsilon, n_0$ definition of convergence.
\itemitem{a.}  $x_n = {3n^2\over n^2 + 5}$
\itemitem{}  {\it Solution:}  By rearranging algebraically, we see
$${3n^2\over n^2 + 5} = {3 \over 1 + 5/n^2}$$
Intuitively, as $n \to \infty$, the $5/n^2$ is tending to $0$, and we see the $x_n \to 3$.
To prove this rigorously, we start out with our ``preparation for the proof:''
$$\left|{3n^2 \over n^2 + 5} - 3\right| = {15\over n^2 + 5} < {15\over n^2}$$
To make this $ < \varepsilon$ it will suffice to take $n > \sqrt{15\over \varepsilon}$.
\bigskip
\itemitem{} {\it Formal proof:}  Let $\varepsilon > 0$, and let $n_0 > \sqrt{15\over \varepsilon}$.
Then for all $n \ge n_0$, we have ${15\over n^2} < \varepsilon$, so
$$\left|{3n^2 \over n^2 + 5} - 3\right| = {15\over n^2 + 5} < {15\over n^2} < \varepsilon. $$
This shows that $x_n \to 3$.
\itemitem{b.}  $x_n = {1\over \ln(n)}$
\itemitem{} {\it Solution:}  The numbers $\ln(n)$ increase without bound, so this sequence
should be converging to $0$.  The ``preparation for the proof'' is to notice that
$${1\over \ln(n)} < \varepsilon \Leftrightarrow \ln(n) > {1\over \varepsilon} \Leftrightarrow n > e^{1\over \varepsilon}.$$
\bigskip
\itemitem{} {\it Formal proof:}  Let $\varepsilon > 0$ and let $n_0 > e^{1\over\varepsilon}$.  Then
for all $n \ge n_0$, we have (since $\ln$ is a strictly increasing function)
$$\left|{1\over \ln(n)} - 0\right| = {1\over \ln(n)} < {1\over \ln(e^{1\over \varepsilon})} = \varepsilon.$$
This shows ${1\over \ln(n)} \to 0$.
\itemitem{c.}  $x_n = \cases{{3n + 1\over 4n} & if $n$ is even\cr
                             {6n - 3\over 8n + 1} & if $n$ is odd\cr}$
\itemitem{} {\it Solution:}  The even and odd parts of the sequence are both tending to $3/4$ by rearrangements similar to what we did in part a.  For the even part,
$$\left|{3n+1 \over 4n} - {3\over 4}\right| = {1\over 4n},$$
which will be $< \varepsilon$ whenever $n > {1\over 4\varepsilon}$.  Similarly, for the odd part,
$$\left|{6n - 3\over 8n + 1} - {3\over 4}\right| = {15 \over 32n + 4} < {15\over 32n}.$$
This will be $<\varepsilon$ whenever $n > {15\over 32\varepsilon}$.   If we take $n$ greater
than {\it the larger of these bounds}, then we can use them both.  That is the reason for
the $\max$ below.
\bigskip
\itemitem{} {\it Formal proof:}  Let $\varepsilon > 0$, and let
$$n_0 > \max\left({1\over 4\varepsilon},{15\over 32\varepsilon}\right) = {15\over 32\varepsilon}.$$
Then whenever $n \ge n_0$ and $n$ is even we have
$$\left|x_n - {3\over 4}\right| = \left|{3n+1 \over 4n} - {3\over 4}\right| = {1\over 4n} < \varepsilon.$$
Similarly, when $n$ is odd, we have
$$\left|x_n - {3\over 4}\right| = \left|{6n - 3\over 8n + 1} - {3\over 4}\right| = {15 \over 32n + 4} < {15\over 32n} < \varepsilon.$$
This shows that $x_n \to {3\over 4}$.  
\itemitem{d.}  Show that the sequence $x_n = \sin\left({n\pi\over 2}\right)$ does not converge to any $a \in {\bf R}$.
\item{} {\it Solution:}  If we list out the first few terms in this sequence, we can see
that the pattern will be repeating the four values $1,0,-1,0,\ldots$ forever.  
Thus it is pretty clear that the
the terms are not approaching any single limit.  To prove that this is not the case rigorously,
we have to show that for every $a \in {\bf R}$, there exist $\varepsilon > 0$ such that
for all $n_0$, there exist $n \ge n_0$ with $|x_n - a| \ge \varepsilon$.  We consider the
case where $a \ne -1,0,1$ first.  In this case, let $\varepsilon = \min(|a+1|,|a|,|a-1|)$
(the shortest distance from $a$ to any one of the three special values $-1,0,1$).  Then
in fact $|x_n - a| \ge \varepsilon$ for all $n$, and this shows the sequence cannot
be converging to $a$.  If $a = -1,0,1$, we need to argue slightly differently.  Say
$a = -1$ for instance (the others will be similar).  If we take $\varepsilon = 1$ in 
this case, then notice there are infinitely many values of $n$ for which $|x_n - (-1)| \ge 1 = \varepsilon$,
namely, all the $n$'s for which $x_n = 0$ or $1$, or $n \ne 3,7,11,\ldots$.  (In MATH 243 terms
$|x_n - (-1)| \ge 1$ for all $n$ with $n \not\equiv 3 \bmod 4$.)  
Hence there are such $n \ge n_0$ for any given $n_0$.  This shows the definition 
of convergence does not hold with $a = -1$.

\end
