\magnification=\magstep1
\centerline{Mathematics 242 -- Principles of Analysis}
\centerline{Solutions for Problem Set 4}
\centerline{{\bf Due:} March 1, 2013}
\bigskip
\noindent
{\it `A' Section}
\bigskip
\noindent
1.  Using the `Big Theorem' on limits of sequences (Theorem 2.2.5 in the text), find
the limit of each of the following:
\bigskip
\item{(a)}  $x_n = {(3^n + 4^{n/2})^2\over 9^n}$
\medskip
\item{} {\it Solution:}  Expanding the top by the binomial theorem, then dividing by $9^n$, we have 
$$\eqalign{x_n &= {9^n + 2\cdot 6^n + 4^n\over 9^n}\cr
&= {1 + 2\cdot (6/9)^n + (4/9)^n}.\cr}$$
Hence by Theorem 2.2.5(a), and the fact that $(6/9)^n \to 0$ and $(4/9)^n \to 0$, the
limit is 1.  
\medskip
\item{(b)}  $x_n = \sqrt{n}(\sqrt{16n + 3} - 4\sqrt{n})$ (Hint: 
$\sqrt{a} - \sqrt{b} = {a - b\over \sqrt{a} + \sqrt{b}}$ -- do you see why?  Also, you may use the result of question 1 in the B section if needed.)
\medskip
\item{} {\it Solution:}  By the algebraic identity in the Hint, we have:
$$\eqalign{x_n &= \sqrt{n} \cdot {(16n + 3) - 16n \over \sqrt{16n + 3} + 4\sqrt{n}}\cr
&= {3\sqrt{n} \over  \sqrt{16n + 3} + 4\sqrt{n}}\cr
&= {3\over \sqrt{16 + 3/n} + 4}.\cr}$$
By Theorem 2.2.5(c) and question 1 in the B section, 
$\lim_{n\to\infty} x_n = {3\over 8}$.  
\medskip
\item{(c)}  $x_n = {1\over n^4} \sum_{k=0}^4 {n\choose k} {1\over 2^k}$.  (The ${n\choose k}$ are the binomial coefficients as in Problem Set 2.)
\medskip
\item{} {\it Solution:}  By the definition, after cancellation 
$${n \choose k} = {n!\over k! (n-k)!} = {n(n-1)\cdots (n-(k-1))\over k!},$$
with $k$ factors on the top.  As a polynomial in $n$, the degree of the top is $k$.  
Hence, for $k < 4$, we will have $\lim_{n\to\infty} {1\over n^4} {n\choose k} = 0$ and 
$\lim_{n\to\infty} {1\over n^4} {n\choose 4} = {1\over 4!}$ by applying the Limit Sum Rule.  
Therefore 
$$\lim_{n\to\infty} x_n = {1\over 4!}\cdot {1\over 2^4} = {1\over 384}.$$ 
\bigskip
\noindent
2.  For each of the following statements, first say whether the statement is true.  Then, if the 
statement is true, give a reason; if it is false give a counterexample.
\bigskip
\item{(a)}  Let $\{x_n\}$ and $\{y_n\}$ be sequences.  If it is known that $\{x_n\}$ and 
$\{x_n + y_n\}$ converge, then $\{y_n\}$ converges too.
\medskip
\item{} {\it Solution:}  This is true, since we can apply part (a) of Theorem 2.2.5
to deduce that $y_n = (x_n + y_n) - x_n$ converges.
\medskip
\item{(b)}  If $\{x_n\}$ and $\{y_n\}$ both diverge, then so does $\{x_n\cdot y_n\}$.
\medskip
\item{} {\it Solution:}  This is false.  A counterexample:  Let $x_n = (-1)^n = y_n$.
Then both $x_n$ and $y_n$ diverge, but $x_n\cdot y_n$ is the constant sequence $1$, which
certainly converges. 
\medskip
\item{(c)}  If $x_n \to a$, $y_n \to b$ and $x_n < y_n$ for all $n\in {\bf N}$, then $a < b$. 
\medskip
\item{} {\it Solution:}  This is false.  Consider $x_n = {1\over 2n}$ and $y_n = {1\over n}$, for 
instance.  Then $x_n < y_n$ for all $n \ge 1$.  But $x_n \to 0$ and $y_n \to 0$ also.  
(The thing that is true is $a \le b$.  See Theorem 2.2.7 in the text.)
\medskip   
\item{(d)}  If $x_n > 0$ and ${x_{n+1}\over x_n} \le 1$ for all $n \ge 1$, then $x_n \to 0$.
\medskip
\item{} {\it Solution:}  This is also false.  The given information says $x_n$ is strictly 
positive for all $n$, hence $x_{n+1} \le x_n$.  So $x_n$ is a monotone decreasing sequence
that is bounded below by $0$.  It must converge, but not necessarily to zero.  For example 
$x_n = 1 + {1\over n}$ satisfies all the conditions, but $x_n \to 1$.    
\bigskip
\noindent
3.  For each of the following sequences, first explain why the sequence is monotonic and bounded,
then determine the limit:
\bigskip
\item{(a)}  $x_{n+1} = \sqrt{6 + x_n}$, $x_1 = 1$.
\medskip
\item{} {\it Solution:} We have $x_1 = 1$ and $x_2 = \sqrt{7} > 1$.  Now assume we know 
$x_{k+1} > x_k$ and consider $x_{k+2} = \sqrt{6 + x_{k+1}}$.  Since $x_{k+1} > x_k$, 
we have $6 + x_{k+1} > 6 + x_k$, hence $x_{k+2} = \sqrt{6 + x_{k+1}} > \sqrt{6 + x_k} = x_{k+1}$.
By induction, it follows that $x_n$ is a monotone strictly increasing sequence.  We claim next that 
$x_n$ is bounded above.  For instance, we claim $x_n < 10$ for all $n$.  This can 
also be proved by induction:  $x_1 = 1 < 10$ for the base case.  If we assume $x_k < 10$, then
$x_{k+1} = \sqrt{6 + x_k} < \sqrt{6 + 10} = 4 < 10$ also.  Therefore by induction, $x_n$
is bounded above.  By the Monotone Convergence Theorem, it follows that $x_n$ converges to 
some $\alpha \in {\bf R}$.  If we take the limit as $n\to\infty$ in the recursion equation,
we get 
$$\alpha = \lim_{n\to\infty} x_{n+1} = \sqrt{6 + \lim_{n\to\infty}x_n} = \sqrt{6 + \alpha}$$
Squaring, we get $\alpha^2 = 6 + \alpha$, which has the roots $\alpha = 3, -2$.  Since 
$x_n > 0$ for all $n$, the limit must be $\alpha = 3$.     
\medskip
\item{(b)}  $x_{n+1} = {4x_n + 7\over 10}$, $x_1 = 2$.  
\medskip
{\it Solution:}  We hve $x_1 = 2$ and $x_2 = {15\over 2} = {3\over 2}$.  Assuming $x_{k+1} \le x_k$, 
consider 
$$x_{k+2} = {4 x_{k+1} + 7 \over 10} \le {4 x_{k} + 7\over 10} = x_{k+1}.$$
By induction the sequence is monotone decreasing.  It is easy to see that $x_n > 0$ for all $n$, 
so the sequence is also bounded below, hence converges to some $\beta \in {\bf R}$.  
Taking limits as in part (a), we get $\beta = {4 \beta + 7\over 10}$, so $\beta = {7\over 6}$.   
\bigskip
\noindent
{\it `B' Section}
\bigskip
\noindent
1.  Let $a > 0$.  Show that if $x_n \to a$ and $x_n \ge 0$ for all $n$, then $\sqrt{x_n} \to \sqrt{a}$.  
(Hint:  See part (b) of question 1 in the A section.)
\bigskip
\noindent
{\it Solution:}  Let $\varepsilon > 0$.  Since $x_n \to a$, there exists a natural number $n_0$
such that $|x_n - a| < \varepsilon\sqrt{a}$ for all $n\ge n_0$.  Then for all $n \ge n_0$ we have, 
using the identity from question 1 in the A section:
$$|\sqrt{x_n} - \sqrt{a}| = \left|{x_n - a \over \sqrt{x_n} + \sqrt{a}}\right| \le {|x_n - a|\over \sqrt{a}}
< {\varepsilon\sqrt{a}\over \sqrt{a}} = \varepsilon.$$
This shows $\sqrt{x_n} \to \sqrt{a}$.  
\bigskip
\noindent
2. In this problem, you will show that the sequence $x_n = \sum_{k=1}^n {1\over k!}$ converges.
\bigskip
\item{(a)}  First show that ${1\over k!} \le {1\over 2^{k-1}}$ for all integers $k \ge 1$.
\medskip
\item{} {\it Solution:}  With $k = 1$, we have $1 \le 1$ so the base case for an induction
is established.  Now assume that the inequality has been shown for $k = \ell$ and consider
$${1\over (\ell+1)!} = {1 \over \ell!} \cdot {1\over \ell+1} \le {1\over 2^{\ell-1}} \cdot {1\over 2} = {1\over 2^\ell}.$$
Hence the inequality is true for all $k \ge 1$.  
\medskip 
\item{(b)}  Show that for all $n \ge 1$, 
$$1 + {1\over 2} + \cdots + {1\over 2^{n-1}} = {1 - {1\over 2^n} \over 1 - {1\over 2}}$$
and deduce that $x_n$ is bounded above by $2$. 
\medskip
\item{} {\it Solution:}  Let $y_n = 1 + {1\over 2} + \cdots + {1\over 2^{n-1}}$.  We see that
$y_n - {1\over 2}y_n$ ``telescopes'' as follows:
$$ y_n - {1\over 2}y_n = {1 - {1\over 2^n}},\ {\rm hence}\ y_n = {1 - {1\over 2^n}\over 1 - {1\over 2}}$$
as claimed.  (This can also be proved by induction, of course.)  Note that after some rearrangement, 
$$y_n = 2 - {1\over 2^{n-1}} < 2$$
for all $n$.  
To make the connection with $x_n$ above, we apply the inequality from part (a) term by term
to the sum in the formula for $x_n$:
$$x_n = {1\over 1!} + {1\over 2!} + \cdots + {1 \over n!} \le 1 + {1\over 2} + \cdots + {1\over 2^{n-1}} = y_n$$
Combining these observations we have
$$x_n = \sum_{k=1}^n {1\over k!} \le \sum_{k=1}^n {1\over 2^n} < 2$$
\medskip
\item{(c)}  Use part (b) to show that $x_n$ converges.  
\medskip
\item{} {\it Solution:} 
We see $x_n$ is a monotone increasing sequence since the terms that are added into 
$x_n$ are all positive.  Hence $x_{n+1} = x_n + {1\over (n+1)!} > x_n$ for all $n\ge 1$.
By part (b) $x_n$ is also bounded above.  It follows from 
the Monotone Convergence Theorem that $x_n$ converges to some $\alpha \in {\bf R}$.  (The 
limit is actually the number $e - 1$ (where $e$ is the base of the natural logarithms).
\bigskip
\noindent
3.  In class, we proved the Monotone Convergence Theorem for sequences, 
the result stated as Theorem 2.3.3 in the text.  In the proof we used the Least Upper Bound
Axiom in a crucial way.  It is an interesting fact that the implication goes the other
way too.  Namely if we assume that monotone increasing sequences of reals always converge
to real numbers, it follows that that every set of reals that is bounded above has
a least upper bound.  You will show this in this problem using the following construction.
Let $A$ be any nonempty set of real numbers that is bounded above.  The proof is based on 
constructing two sequences
$x_n$ and $y_n$ by this inductive procedure:
\bigskip
\item{(i)}  Let $x_1 \in A$ be any element of $A$, and let $y_1$ be any upper bound for $A$.  
\item{(ii)}  Assuming $x_k$ and $y_k$ have been constructed such that $x_k \in A$ and
$y_k$ is an upper bound for $A$, 
find $x_{k+1}$ and $y_{k+1}$ like this:  Let $m_k = {x_k + y_k\over 2}$.  
If $m_k$ is also an upper bound for $A$, then set 
$x_{k+1} = x_k$ and $y_{k+1} = m_k$.  Otherwise, there is some $x \in A$ with $m_k < x \le y_k$, and 
in this case let $x_{k+1} = x$ and $y_{k+1} = y_k$.  
\bigskip
\noindent
Note that an easy induction argument shows that this construction will produce
sequences such that $x_n \in A$ for all $n\ge 1$ and $y_n$ is an upper bound for $A$
for all $n\ge 1$.    
\bigskip
\noindent
Now prove the following statements to show that $A$ has a least upper bound in ${\bf R}$ assuming
the Monotone Convergence Theorem:
\bigskip
\item{(a)}  Prove that both sequences $\{x_n\}$ and $\{y_n\}$ converge to elements of ${\bf R}$, using the Monotone Convergence Theorem and its Corollary.
\medskip
\item{} {\it Solution:}  The $x_n$ are all bounded above by $y_1$ and the $y_n$ are all bounded
below by $x_1$.  By the construction, we also see $x_n$ is monotone increasing (whenever $x_{n+1} \ne x_n$, 
we necessarily have $x_{n+1} > x_n$), and similarly $y_n$ is 
monotone decreasing.  Therefore both sequences converge in ${\bf R}$ by the Monotone Convergence
Theorem and its Corollary.  
\medskip
\item{(b)}  Show that $\lim_{n\to\infty} x_n = \lim_{n\to\infty} y_n$ by showing that 
$|x_n - y_n| \le {|x_1 - y_1| \over 2^{n-1}}$ for all $n \ge 1$. 
\medskip
\item{} {\it Solution:}  First, note that each time we go from one integer $k$ to 
the next integer $k + 1$, the construction of the sequences $x_n$ and $y_n$
using the midpoints $m_n$ shows
$$|x_{k+1} - y_{k+1}| \le {1\over 2} |x_k - y_k|.$$
It follows that $|x_n - y_n| \le {|x_1 - y_1| \over 2^{n-1}}$ for all $n \ge 1$ as claimed.
Now, say $\lim_{n\to\infty} x_n = \alpha$ and $\lim_{n\to\infty} y_n = \beta$.  We want
to show that $\alpha = \beta$.  To see this, note that we have, for all $n$, 
$$x_n \le \alpha \le \beta \le y_n$$
Therefore 
$$|\alpha - \beta| \le |x_n - y_n| = {|x_1 - y_1| \over 2^{n-1}}$$
for all $n\ge 1$.  Since ${1\over 2^{n-1}} \to 0$ as $n \to \infty$, while $|x_1 - y_1|$ is 
constant, it follows that 
$$|\alpha - \beta| = 0,\ {\rm hence}\ \alpha = \beta.$$ 
\item{(c)}  Let $\alpha$ be the common limit of the $x_n$ and $y_n$ sequences.  Show that 
$\alpha = {\rm lub}(A)$ by showing it satisfies the definition of a least upper bound.
\medskip
\item{} {\it Solution:}  We must show first that $\alpha \ge x$ for all $x \in A$, and
second that no number $\alpha - \varepsilon$ for $\varepsilon > 0$ is an upper bound
for $A$.  The first statement follows since each of the $y_n$ satisfy $y_n \ge x$ for
all $x\in A$.  It follows from Theorem 2.2.7 in the text (applied to the $y_n$ sequence
and the constant sequence $z_n = x$) that $\lim_{n\to\infty} y_n = \alpha \ge x$ for all $x \in A$.
Now let $\varepsilon > 0$ and consider $\alpha - \varepsilon$. Since we have 
$\lim_{n\to\infty} x_n = \alpha$, 
it follows that there exists an $n_0 \in {\bf N}$ such that $\alpha - \varepsilon < x_{n_0} \le \alpha$.
Since $x_{n_0} \in A$, it follows that $\alpha - \varepsilon$ is not an upper bound for $A$.
Therefore $\alpha = {\rm lub}(A)$.    
\bye    
