\magnification=\magstep1
\centerline{Mathematics 242 -- Principles of Analysis}
\centerline{Solutions for Problem Set 5}
\centerline{{\bf Due:} March 15, 2013}
\bigskip
\noindent
{\it `A' Section}
\bigskip
\noindent
1.  For each of the following sequences, determine three different subsequences,
each converging to a different limit.  For each one, express your three subsequences
as $x_{n_k}$ for a suitably chosen (strictly increasing) index sequence $n_k$, and give an explicit formula
for $n_k$ as a function of $k$:
\bigskip
\item{(a)}  $x_n = \cos\left({\pi\sqrt{n}\over 2}\right)$
\medskip 
\item{} {\it Solution:}  If $n_k = (4k)^2$, then $x_{n_k} = 1$ for all $k$, so that subsequence
converges to $1$.  If $n_k = (2(2k+1))^2$, then $x_{n_k} = -1$ for all $k$, so that subsequence 
coverges to $-1$.  Finally, if $n_k = (2k-1)^2$, then $x_{n_k} = 0$ for all $k$ so that subsequence
converges to $0$.  There are infinitely many other correct examples too.  
\medskip
\item{(b)}  $x_n = {n\over 3} - \left[{n\over 3}\right]$  (as usual, $[\ ]$ denotes the greatest integer function)
\medskip
\item{} {\it Solution:}  Let $n_k = 3k$, then $x_{3k} = k - k = 0$ for all $k$, so that subsequence 
converges to $0$.  Let $n_k = 3k + 1$, then $x_{3k+1} = k + 1/3 - k = 1/3$ for all $k$, so that 
subsequence converges to $1/3$.  Finally, if $n_k = 3k+2$, then the subsequence $x_{3k+2}$ converges
to $2/3$.  
\bigskip
\noindent
2.  Let $x_n = n^{1/4}$.  For each of the following sequences, either express that sequence
as a subsequence of
the sequence $x_{n_k}$ for some explicit (strictly increasing) index sequence $n_k$, or say why that is impossible:
\bigskip
\item{(a)}  $\{2,3,4,5,\ldots\}$
\medskip
\item{} {\it Solution:}  This is the subsequence $x_{n_k}$ for $n_k = (k+1)^4$, $k \ge 1$.  
\medskip
\item{(b)}  $\{\sqrt{3},\sqrt{6},\sqrt{9},\sqrt{12},\ldots\}$
\medskip
\item{} {\it Solution:}  This is the subsequence $x_{n_k}$ for $n_k = (3k)^2$, $k \ge 1$.  
\medskip
\item{(c)}  $\{1,2,4,8,16,32,\ldots\}$
\medskip 
\item{} {\it Solution:}  This is the subsequence $x_{n_k}$ for $n_k = 2^{4k-4}$, $k \ge 1$.  
\bigskip
\noindent
3.  Let $x_n = \sin\left({n\pi\over 4}\right)$ and $y_n = \cos\left({n\pi\over 4}\right)$.
\bigskip
\item{(a)}  Find a (strictly increasing) index sequence $n_k$ such that both $x_{n_k}$ and $y_{n_k}$ 
converge.
\medskip
\item{}  {\it Solution:}  The sequence $n_k = 8k + 1$ is such an index sequence since
$$\sin\left({(8k+1)\pi\over 4}\right) = \sin\left(2k\pi + {\pi\over 4}\right) = {\sqrt{2}\over 2}$$
and 
$$\cos\left({(8k+1)\pi\over 4}\right) = \cos\left(2k\pi + {\pi\over 4}\right) = {\sqrt{2}\over 2}$$
for all $k \ge 1$.  
\medskip
\item{(b)}  Find a second (strictly increasing) index sequence $n_k$ such that both $x_{n_k}$ and $y_{n_k}$ 
diverge.
\medskip
\item{} {\it Solution:}  The sequence $n_k = k$ is such a sequence.  
\medskip
\item{(c)}  Find a third (strictly increasing) index sequence $n_k$ such that one of $x_{n_k}$ and $y_{n_k}$ 
converges and the other diverges. 
\medskip
\item{} {\it Solution:}  The sequence $n_k = 4k$ is such an example since $\sin(k\pi) =0$ for 
all $k$, but $\cos(k\pi) = (-1)^k$ does not converge.  
\bigskip
\noindent
{\it `B' Section}
\bigskip
\noindent
1.  (True or False) -- If the statement is true give a proof; if it is false give a counterexample.
\bigskip
\item{(a)}  If $x_n$ is a sequence of strictly negative numbers converging to $0$, then 
$x_n$ has a strictly increasing subsequence $x_{n_k}$.  
\medskip
\item{} {\it Solution:}  This is TRUE.  Here is one way to see it, constructing a strictly 
increasing subsequence inductively.  We start with $n_1 = 1$, so $x_{n_1} = x_1$.  This is the 
base case.  Now assume we have found $x_{n_1} < x_{n_2} < \ldots < x_{n_k}$ for 
$1 = n_1 < n_2 < \cdots < n_k$.   Since $x_n \to 0$, 
given $\varepsilon = |x_{n_k}|$, there exists $N_0$ in ${\bf N}$ such that $|x_n - 0| < |x_{n_k}|$
for all $n \ge N_0$.  Take $n_{k+1} = \max(N_0,n_k + 1)$.  Then we have $|x_{n_{k+1}}| < |x_{n_k}|$, 
so $x_{n_{k+1}} > x_{n_k}$ (since they are both negative) and $n_{k+1} > n_k$.  This 
shows we can continue to construct a strictly increasing subsequence.     
\medskip
\item{(b)}  If $x_n \to 0$, then $x_n$ contains
a strictly increasing subsequence or a strictly decreasing subsequence (or both).  
\medskip
\item{} {\it Solution:}  This is FALSE.  Counterexamples are the constant sequence $x_n = 0$
for all $n\ge 1$, or any ``eventually constant'' sequence with $x_n = 0$ for all $n \ge n_0$
for some $n_0 \in {\bf N}$.  (Comment:  The statement would be true if we assumed $x_n \ne 0$ for
all $n$ (or even all $n\ge n_0$ for some $n_0 \in {\bf N}$).  
Any such sequence contains either infinitely many positive terms or
infinitely many negative terms, or both.  If there are infinitely many negative terms, we get
a strictly increasing subsequence of the negative terms by part (a) of this question. 
If there are infinitely many strictly positive terms, then there is a strictly decreasing
subsequence, as can be seen by taking negatives, using part (a), then flipping signs
again.)
\medskip 
\item{(c)}  If $x_n$ is a decreasing sequence with a bounded subsequence $x_{n_k}$, then 
$x_n$ converges.
\medskip
\item{} {\it Solution:}  This is TRUE.  Since the whole sequence is decreasing, so is the 
subsequence $x_{n_k}$.  But that subsequence is bounded (below), say by $a \in {\bf R}$.  We claim that
the whole sequence $x_n$ is also bounded below by $a$.  To see
that, let $n$ be any natural number.  Since $\{n_k\}$ is a strictly increasing sequence of natural numbers, 
it follows that it is not bounded above.  So there is some $k$ such that $n_k \ge n$.  But 
then since $x_n$ is decreasing and $a$ is a lower bound for the subsequence, 
$a \le x_{n_k} \le x_n$.  It follows that $x_n \ge a$ for all $n$, and hence
the whole sequence is bounded below.  Then $\{x_n\}$ converges as well by the Monotone Convergence Theorem.   
(You can also show that the limit of the whole sequence must be the same as the limit
of the subsequence, but that was not required.)

\bigskip
\noindent
2.  Consider the sequence $x_n = \cos(n)$ (where we think of $n$ as an angle expressed in radians).
\bigskip
\item{(a)}  Prove that $x_n$ has a convergent subsequence.
\medskip
\item{} {\it Solution:}  Since $|\cos(n)| \le 1$ for all $n\ge 1$, this is a bounded sequence.  The
statement to be proved is a direct consequence of the Bolzano-Weierstrass Theorem. 
\medskip
\item{(b)}  In this part of the question we will show that $x_n$ is not convergent, though.
Suppose $\lim_{n\to\infty} \cos(n) = a$ for some real number $a$.  Using a trig identity for 
$\cos(n + 1)$ and considering $\lim_{n\to\infty} (\cos(n+1) - \cos(n))$, show that 
$${a (\cos(1) - 1)\over \sin(1)} = \lim_{n\to\infty} \sin(n).$$  But then use the sequence
$\lim_{n\to\infty} (\sin(n+1) - \sin(n))$ to deduce that $a = 0$, so 
$\lim_{n\to\infty} \cos(n) = \lim_{n\to\infty} \sin(n) = 0$.  But this is a contradiction.
Explain why to conclude the proof.  
\medskip
\item{} {\it Solution:}  The addition formula for $\cos$ implies that 
$\cos(n + 1) = \cos(n)\cos(1) - \sin(n)\sin(1)$.  If we assume that $\lim_{n\to\infty} \cos(n) = a$, then
using parts of the ``Big Theorem'' and rearranging algebraically, we see
$$\eqalign{
0 &= \lim_{n\to\infty} (\cos(n+1) - \cos(n)) \cr
&= \lim_{n\to\infty} \cos(n)(\cos(1) - 1) - \lim_{n\to\infty} \sin(n) \sin(1)\cr
&= a(\cos(1) - 1) - \sin(1) \lim_{n\to\infty} \sin(n).\cr}$$
Thus, 
$$\lim_{n\to\infty} \sin(n) = {a(\cos(1) - 1)\over \sin(1)}. \leqno(1) $$
as claimed.  Now the addition formula for $\sin$ shows 
$$\sin(n+1) = \sin(n) \cos(1) + \cos(n) \sin(1)$$
Taking the limit as $n \to \infty$ on both sides and substituting from (1), we get:
$${a(\cos(1) - 1)\over \sin(1)} = {a(\cos(1) - 1)\over \sin(1)} \cos(1) + a\sin(1),$$
so 
$$a(\cos(1) - 1) = a(\cos(1) - 1)\cos(1) + a\sin^2(1),$$
and hence (because $\cos^2(1) + \sin^2(1) = 1$), 
$$a(\cos(1) - 1) = a(1 - \cos(1)).$$
The only way this can be true is if $a = 0$.  But then this implies that 
$$\lim_{n\to\infty} \sin(n) = 0 = \lim_{n\to\infty} \cos(n).$$
But that is impossible because it would say $\lim_{n\to\infty} \cos^2(n) + \sin^2(n) = 0$ by
parts (a) and (b) of the ``Big Theorem.''  However, we know by the basic identity for the 
trigonometric functions that  
$$\cos^2(n) + \sin^2(n) = 1$$ 
for all $n\ge 1$.  Hence
$\lim_{n\to\infty} \cos^2(n) + \sin^2(n) = 1$ as well if the two limits exist.   This 
contradiction shows that $\lim_{n\to\infty} \cos(n)$ cannot exist.  
\bigskip
\noindent
3.  A {\it cluster point} of a sequence $x_n$ is a limit of a convergent subsequence $x_{n_k}$.
(See question 1 on the A section for examples of sequences with several different cluster points.)
\bigskip
\item{(a)}  Show that there exists a sequence $x_n$ whose set of cluster points is all of 
${\bf R}_+ = \{x \in {\bf R}\mid x > 0\}$.
(Hint:  Look at the solution for the Extra Credit problem on Exam 1, which shows how to get
a sequence containing all the positive rational numbers.  Think rational approximations to 
decimals to get a subsequence converging to any given positive $a \in {\bf R}$.  However,
note that you will need to be careful to produce an actual subsequence $x_{n_k}$ with a 
strictly increasing index sequence $n_k$.   In fact, this example
can be ``jazzed up'' to get a sequence whose set of cluster points consists is all of ${\bf R}$!)
\medskip
\item{} {\it Solution:}  As shown in the solution to the Extra Credit problem there is a sequence $\{x_n\}$
whose terms contain all the positive fractions $p/q$ with $p, q$ integers $\ge 1$.  We claim that {\it every positive
real number is cluster point of that sequence}.  Note that because of the ``zig-zag''
way that sequence is constructed, in the sequence $\{x_n\}$, all the fractions 
$p/q$ with $p + q = \ell$ occur before those with $p + q = \ell + 1$, etc.  In other words, 
the sum of the numerator and the denominator of $x_n$ is an increasing function of $n$.   Now, 
if $p/q$ is a positive fraction in lowest terms, then we can also consider the fractions 
$(pk)/(qk)$ for all $k\ge 1$.  These form a subsequence of the $x_n$ sequence since the sum
$pk + qk = (p+q)k$ is strictly increasing as a function of $k$.   Hence the indices $n_k$ 
that give $(pk)/(qk) = x_{n_k}$
must also be strictly increasing.  That subsequence converges to $a = p/q$ since all the fractions 
$(pk)/(qk)$ reduce to $p/q$, so it's actually a constant sequence.  
Next, any positive irrational number can be expressed with
an infinite (nonrepeating) decimal expansion
$$a = d_k d_{k-1} \ldots d_0 . f_1 f_2 \cdots $$
(where the $d_i$ and the $f_j$ are the decimal digits).  As we saw in class, that 
expansion is equivalent to a monotone increasing
sequence of rational approximations with denominators that are powers of $10$:
$$d_k \ldots d_0/1, d_k \ldots d_0f_1/10, d_k \ldots d_0 f_1 f_2/100, \ldots .$$
The notation means something like this:  If $a = \sqrt{2}$, for instance, where 
$\sqrt{2} = 1.4142\cdots$, then our sequence of rational approximations is 
$$1/1, 14/10, 141/100, 1414/1000, \ldots\ . $$
When we add one 
more decimal digit to get the next term in a sequence approximating a given positive real $a$, the
corresponding fraction will definitely occur {\it later} in the $x_n$ sequence, since the sum of the numerator
and the denominator always increases when we include an additional digit.  
This shows that we have a subsequence converging to $a$.  Hence $a$ is a cluster point of the $x_n$ sequence.  
\medskip    
\item{(b)}  Show that if $a_m$ is a convergent sequence of cluster points of a given sequence $x_n$,
then $a = \lim_{m\to\infty} a_m$ is also a cluster point of the $x_n$ sequence.  
\medskip
\item{} {\it Solution:}  We let $a_m$ be a convergent sequence of cluster points of $x_n$ with 
$a = \lim_{m\to\infty} a_m$.  Since each $a_m$ is a cluster point of the $x_n$ sequence, there
is a subsequence of $x_n$ converging to $a_m$.  From the subsequence converging to $a_1$,
select any $x_{n_1}$ with $|x_{n_1} - a_1| < 1$. Then from the subsequence converging 
to $a_2$, select any $x_{n_2}$ with $n_2 > n_1$ and $|x_{n_2} - a_2| < {1\over 2}$, then 
from the subsequence converging to $a_3$, select $x_{n_3}$ with $|x_{n_3} - a_3| < {1\over 3}$
and $n_3 > n_2$.  By an induction argument, we can always continue this process since for 
any $\ell\ge 1$, there are infinitely many index values $n_\ell$ for which $|x_{n_\ell} - a_\ell| < {1\over \ell}$
(all the indices giving terms in the subsequence converging to $a_\ell$ that are distance ${1\over \ell}$
or less from $a_\ell$).    
In this way we get a subsequence $\{x_{n_\ell}\}$ (indexed by $\ell \in {\bf N}$)
with $n_\ell$ strictly increasing and $|x_{n_\ell} - a_\ell| < {1\over \ell}$
for all $\ell \ge 1$.  We claim that the subsequence $x_{n_\ell}$ converges to $a$.  To see this note
that given any $\varepsilon > 0$, there exists $\ell_0 \in {\bf N}$ such that ${1\over \ell} < {\varepsilon \over 2}$
and $|a_\ell - a| < {\varepsilon\over 2}$ for all $\ell \ge \ell_0$.  Then by the triangle inequality, 
for all $\ell \ge \ell_0$,
$$|x_{n_\ell} - a| = |x_{n_\ell} - a_\ell + a_\ell - a| \le |x_{n_\ell} - a_\ell| + |a_\ell - a| < {\varepsilon\over 2} + {\varepsilon\over 2} = \varepsilon.$$
This shows that the subsequence $\{x_{n_\ell}\}$ converges to $a$, so $a$ is also a cluster point of the $\{x_n\}$ sequence.   

\bye    
