\magnification=\magstep1
\centerline{Mathematics 242 -- Principles of Analysis}
\centerline{Problem Set 2 -- Selected Solutions}
\centerline{September 27, 2004}
\bigskip
\noindent
8.4e/  We must construct a bijective mapping $f: (0,1) \to {\bf R}$.
In order to get the whole real line as the image of a function on 
a finite interval, we expect the graph must have vertical asymptotes
at both $x=0$ and $x=1$, say with $\lim_{x\to 0^+} f(x) = -\infty$
and $\lim_{x\to 1^-} f(x) = +\infty$.  We recall from calculus 
that the tangent function has a graph with the right general
shape.  However $\tan(x)$ has successive vertical asymptotes at
$x = -\pi/2$ and $x = \pi/2$.  So we must shift and ``squeeze''
the graph horizontally to place the asymptotes at $x = 0$ and $x = 1$.
The function $f(x) = \tan(\pi x - \pi/2)$ will work for this purpose.
Note that $x = 0$ corresponds to $-\pi/2$ and $x = 1$ corresponds
to $-\pi/2$.  Since $\tan(x)$ is strictly increasing on the 
open interval $(-\pi/2, \pi/2)$, it is injective.  It is continuous
and surjective onto
${\bf R}$.  (A full proof of this requires a result called the 
Intermediate Value Theorem that we will prove in a few weeks.)
Hence our $f$ is a bijection from $(0,1)$ to ${\bf R}$.

\bigskip
\noindent
8.11/  a)  We must show that there is a bijection $f: (0,1) \to (m,n)$.
The linear function with $f(0) = m$ and $f(1) = n$ will work for this
purpose, since both endpoints of both intervals are omitted.  We
obtain $f(x) = (n-m)x + m$.  This is injective since 
$$f(x) = f(x') \Rightarrow (n-m)x + m = (n-m)x' + m \Rightarrow (n-m)x = (n-m)x' \Rightarrow
x = x'.$$
The surjectivity can be proved directly here (without recourse
to the Intermediate Value Theorem).  Given any $y \in (m,n)$,
we can solve the equation $y = (n-m)x + m$ for $x$:
$x = {y-m\over n-m}$.  If $m < y < n$, we see $0 < x < 1$.

\bigskip
b) Using part a, we have bijections $f : (0,1) \to (m,n)$ and $g: (0,1) \to (m',n')$.
The function $h = g \circ f^{-1}$ maps $(m,n)$ to $(m',n')$.  Moreover
$h$ is a bijection since $f^{-1}$ and $g$ are bijections.
\bigskip
\noindent
10.15/ We assume that $p(n)$ is a collection of statements, one
for each $n \in {\bf N}$, satisfying 
\medskip
\item{1)} $p(1)$ is true, and 
\item{2)} $p(1) \wedge p(2) \wedge \cdots \wedge p(k) \Rightarrow p(k+1)$ for all $k \ge 1$.
\medskip
\noindent
We claim that $p(n)$ is true for all $n \in {\bf N}$ (the principle of strong induction).
The proof is by contradiction.  Let $F = \{ n : p(n) {\rm\ is\ false} \}$, 
so we assume $F$ is nonempty.  By the Well-Ordering Principle, $F$ has
a smallest element $n_0$.  By assumption 1, $n_0 > 1$.  Hence $n_0 - 1 \in {\bf N}$,
and $1, 2, \ldots, n_0 - 1 \in {\bf N}\ \backslash\ F$, so $p(1), \ldots, p(n_0-1)$
are all true.  Then assumption 2 shows that $p(1) \wedge \cdots \wedge p(n_0-1)$
implies $p(n_0)$ is also true.  But this is a contradiction, since 
$n_0 \in F$.  Therefore $F$ must be empty, and $p(n)$ is true for all 
$n \in {\bf N}$.

\bigskip
\noindent
10.18 a)  Finding a common denominator, we have
$$\eqalign{
{n \choose r} + {n \choose r-1} &= {n!\over r!(n-r)!} + {n!\over (r-1)! (n-r+1)!}\cr
&= {n!((n-r+1)+r)\over r!(n-r+1)!}\cr
&= {n!(n+1)\over r!(n-r+1)!}\cr
&= {(n+1)!\over r!(n-r+1)!}\cr
&= {n+1\choose r}\cr}$$

\bigskip
b)  We must prove that
$$(a+b)^n = \sum_{i=0} {n\choose i} a^{n-i} b^i = 
{n\choose 0} a^n + {n\choose 1}a^{n-1}b + \cdots + {n\choose n}b^n$$ 
This proof will be by induction on $n$.  The base case $n=1$
is true since 
$$(a+b)^1 = a + b = {1\choose 0}a + {1 \choose 1} b$$
Now we assume as our induction hypothesis that 
$$(a+b)^k = {k \choose 0} a^k + {k\choose 1} a^{k-1} b + \cdots + {k \choose k} b^k.$$
Now we consider $(a+b)^{k+1}$ and use the induction hypothesis:
$$\eqalign{
(a+b)^{k+1} &= (a+b)(a+b)^k\cr
&=(a+b)\left({k \choose 0} a^k + {k\choose 1} a^{k-1} b + \cdots + {k \choose k} b^k\right)\cr
&={k \choose 0} a^{k+1} + {k\choose 1} a^k b + {k \choose 2} a^{k-1}b^2 + \cdots + {k \choose k} a b^k \cr
&\qquad\qquad\qquad\ \ {k \choose 0} a^k b + {k\choose 1} a^{k-1} b^2 + \cdots + {k \choose k-1} a b^k + {k \choose k} b^{k+1}\cr
}$$
We collect like terms and use part a.
Then since ${k\choose 0} = {k+1\choose 0} = {k\choose k} = {k+1\choose k+1} = 1$,
$$ = {k+1 \choose 0} a^{k+1} + {k+1\choose 1} a^k b + {k+1 \choose 2} a^{k-1}b^2 + \cdots + {k+1 \choose k+1} b^{k+1}$$
\bye
