\magnification=\magstep1
\overfullrule=0pt
\centerline{Mathematics 242 -- Principles of Analysis}
\centerline{Selected Solutions -- Problem Set 5}
\centerline{October 26, 2004}
\bigskip
\noindent
Section 17/4a:  First we show that if $\lim_{n\to \infty}s_n = s$
and $k$ is a constant, then $\lim_{n\to \infty}ks_n = ks$.
Let $\varepsilon > 0$.  Then since $\lim_{n\to \infty}s_n = s$,
there exists an $N$ such that $|s_n - s| < \varepsilon/|k|$ for all $n \ge N$.
But then for all $n > N$ (the same $N$),
$$\eqalign{|ks_n - ks| &= |k||s_n - s|\cr
&< \varepsilon/|k| \cdot |k|\cr
&=\varepsilon\cr}$$
This shows that $\lim_{n\to \infty}ks_n = ks$.  

Next, we show that then $\lim_{n\to \infty}k + s_n = k + s$.
As above, given any $\varepsilon > 0$, 
there exists an $N$ such that $|s_n - s| < \varepsilon$ for all $n \ge N$.
But then for all $n > N$, 
$$\eqalign{|(k + s_n) - (k + s)| &= |s_n - s|\cr
&< \varepsilon\cr}$$
This shows that $\lim_{n\to \infty}k + s_n = k + s$. 
\bigskip
\noindent
Section 17/13:  We assume that $\lim_{n\to \infty}s_n = s$
and $\lim_{n\to \infty}t_n = t$.  Then for all $\varepsilon > 0$,
there exist $N_1$ such that $|s_n - s| < \sqrt{\varepsilon/3}$
for all $n \ge N_1$.  Similarly, there exists $N_2$ such that
$|t_n - t| < \sqrt{\varepsilon/3}$ for all $n \ge N_2$.  Moreover, there
exist $N_3$ such that $|s_n - s| < \varepsilon/(3|t|)$
for all $n \ge N_3$ and $N_4$ such that $|t_n - t| < \varepsilon/(3|s|)$
for all $n \ge N_4$.  Then for all $n > \max(N_1,N_2,N_3,N_4)$, we
have (using the triangle inequality on the identity given 
in the problem)
$$\eqalign{|s_nt_n - st| &\le |s_n-s||t_n-t| + |s||t_n-t| + |t||s_n-s|\cr
&< (\sqrt{\varepsilon/3})^2 + |s| \varepsilon/(3|s|) + |t| \varepsilon/(3|t|)\cr
&= \varepsilon/3 + \varepsilon/3 + \varepsilon/3\cr
&= \varepsilon\cr}$$
This shows that $\lim_{n\to \infty}s_nt_n = st$.
\bigskip
\noindent
Section 18/3d:  Let $s_n$ be the sequence defined by 
$s_1 = 2$, $s_{n+1} = \sqrt{2s_n+1}$ for all $n\ge 1$.  First we show
that $(s_n)$ is bounded above by 3 {\it by mathematical induction on $n$}.
The base case is $n = 1$, and $s_1 = 2 < 3$ is given.  Next, assume
$s_k < 3$.  Then $s_{k+1} = \sqrt{2s_n+1} < \sqrt{6 + 1} = \sqrt{7} < 3$.
Hence $s_n < 3$ for all $n \ge 1$.  

Next, we show that $s_n$ is monotone increasing (i.e. 
$s_n \le s_{n+1}$ for all $n \ge 1$), by induction again.
The base case is $s_1 = 2 \le s_2 = \sqrt{5}$ which is clearly true.
Assume $s_k \le s_{k+1}$.  By the order properties of the real numbers,
this implies $2s_k+1 \le 2s_{k+1} + 1$, which implies 
$s_{k+1} = \sqrt{2s_k+1} \le \sqrt{2s_{k+1} + 1} = s_{k+2}$.
Hence $s_n \le s_{n+1}$ for all $n$.  

Finally, we want to identify the limit $s$.  Taking $\lim_{n\to \infty}$ in the 
equation: $s_{n+1} = \sqrt{2s_n+1}$ we get $s = \sqrt{2s +1}$,
which shows that $s$ must be a solution of the quadratic polynomial equation
$s^2 - 2s  - 1 = 0$.  The quadratic formula gives $s = 1 \pm \sqrt{2}$.
The negative sign gives a negative value, which is not possible
since $s_n \ge 0$ for all $n$.  Hence $s = 1 + \sqrt{2} \doteq 2.414$.

\bigskip
\noindent
Section 18/10:  We let $s_n = \left(1 + {1\over n}\right)^n$.
First, we show that $s_n$ is bounded above by $3$.  By the binomial theorem
we have
$$\eqalign{
\left(1 + {1\over n}\right)^n &= \sum_{k=0}^n {n\choose k} {1\over n^k}\cr
&= 1 + 1 + {1\over 2!}{n(n-1)\over n^2} + {1\over 3!}{n(n-1)(n-2)\over n^3} + \cdots\cr
&\le 1 + 1 + {1\over 2!} + {1\over 3!} + \cdots + {1\over n!}\cr
&\le 1 + 1 + {1\over 2} + {1\over 2^2} + {1\over 2^3} + \cdots + {1\over 2^{n-1}}\cr
&< 3\cr}$$
(Explanation:  from the first line to the second, we use the definition
of the binomial coefficient ${n\choose k}$, then note that 
${n(n-1)\cdots (n-k+1) \over n^k} \le 1$ for all $k$ to get the next line.
Replacing all factors $>1$ in the factorials by $2$ gives a larger result.
Finally we use the result from 18.6 to sum the geometric series with
ratio $1/2$ (there's an extra term of 1 at the start).

Next, we need to see that $s_n$ is a monotone increasing sequence.
This can be done by comparing the second line above:
$$1 + 1 + {1\over 2!}{n(n-1)\over n^2} + {1\over 3!}{n(n-1)(n-2)\over n^3} + \cdots
= 1 + 1 + {1\over 2!} \left(1 - {1\over n}\right) + {1\over 3!}
\left(1 - {1\over n}\right)\left(1 - {2\over n}\right) + \cdots$$
to what we get in a similar fashion from 
$s_{n+1}$:
$$\eqalign{&1 + 1 + {1\over 2!}{(n+1)n\over (n+1)^2} + {1\over 3!}{(n+1)n(n-1)\over (n+1)^3} + \cdots\cr
&= 1 + 1 + {1\over 2!} \left(1 - {1\over n+1}\right) + {1\over 3!}
\left(1 - {1\over n+1}\right)\left(1 - {2\over n+1}\right) + \cdots}$$
(There is one more term in the sum for $n+1$ than for $n$ as well.)
Note that $n+1 > n$, so $(1 - k/n) < (1 - k/(n+1))$ for all $k$.
Hence $s_{n+1} > s_n$ for all $n$.  Since the sequence $s_n$
is monotone increasing and bounded above, it converges.  The limit
is (by definition) the number $e$ (base of the natural logarithms).

\bye
