\documentclass{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{enumerate}
\usepackage{ifthen}
\usepackage{graphicx}

\setlength{\unitlength}{0.1in}

\setlength{\oddsidemargin}{0.0in}
\setlength{\evensidemargin}{0.0in}
\setlength{\topmargin}{0.0in}
\setlength{\headheight}{0.0in}
\setlength{\headsep}{0.0in}
\setlength{\topskip}{0.0in}
\setlength{\textheight}{8.9in}
\setlength{\textwidth}{6.5in}

\newcommand{\comp}{ \,{\scriptstyle \stackrel{\circ}{}}\, } 
\newcommand{\nullset}{\mathrm{O}\!\!\!\!\big/\,}
\newcommand{\divides}{\,\Big|\,}
\newcommand{\myspace}{\mbox{\parbox[c][0.35in]{0.35in}{\hfill}}}
\newcommand{\varspace}[2]{\mbox{\parbox[c][#1]{#2}{\hfill}}}

\begin{document}

\pagestyle{empty}

\noindent
\parbox{2in}{\bf Math 2510} 
\hfill {\Large \bf Test \#2} \hfill
\parbox{2in}{\bf \hfill April $2^{\mathrm{nd}}$, 2010}

\vspace{0.3in}

\noindent {\large\bf Name:} \underline{\sc Answer Key}\\
Don't merely state answers, prove your statements. {\bf Be sure to show your work!}

\noindent {\bf \large 1. (28 points)} Converging Questions
\begin{enumerate}[(a)]

   \item Prove that $\displaystyle{ \left\langle \frac{3n^2}{n^2+2n+3} \right\rangle }$ converges.

\vspace{0.1in}

To come up with a proof first we'll need to do some ``scratch work''. Using a little Calculus I insight, we see that this sequence's limit is 3. Thus we'll need $\displaystyle{\left|\frac{3n^2}{n^2+2n+3} - 3 \right| < \epsilon}$. So we
should find {\it overestimates} of the fraction until we have something
simple enough to set equal to $\epsilon$ and solve for $n$. 

\vspace{-0.2in}

\[ \left|\frac{3n^2}{n^2+2n+3} - 3 \right| = 
   \left|\frac{3n^2-3(n^2+2n+3)}{n^2+2n+3} \right| = 
   \left|\frac{-6n-9}{n^2+2n+3}\right| = \frac{6n+9}{n^2+2n+3} \leq
   \frac{6n+9n}{n^2+2n+3} < \frac{15n}{n^2} = \frac{15}{n} \]

\vspace{-0.1in}

The ``$\leq$'' following because increasing the numerator increases the fraction. Likewise, the ``$<$'' holds because decreasing the denominator
increases the fraction.
   
Now we have a simple estimate for our fraction: $\displaystyle{\frac{15}{n}}$. 
So $15/n=\epsilon$ $\Longrightarrow$ $15/\epsilon = n$. Now we're ready to 
write our proof.

\vspace{0.05in}

\noindent Proof:\\
Suppose $\epsilon > 0$. Let $\displaystyle{N = \left\lceil \frac{15}{\epsilon} \right\rceil}$ [``$\lceil x \rceil$'' is the ceiling function which rounds $x$ up to the next integer]. 

Suppose $n \geq N$, we have that $\displaystyle{n \geq \left\lceil  \frac{15}{\epsilon} \right\rceil \geq \frac{15}{\epsilon}}$. Therefore, $\displaystyle{ \frac{15}{\epsilon} \leq n}$ and so
$\displaystyle{ \frac{15}{n} \leq \epsilon }$. 

\[ \left|\frac{3n^2}{n^2+2n+3} - 3 \right| = 
   \left|\frac{3n^2-3(n^2+2n+3)}{n^2+2n+3} \right| = 
   \left|\frac{-6n-9}{n^2+2n+3}\right| = \frac{6n+9}{n^2+2n+3} \leq
   \frac{6n+9n}{n^2+2n+3} < \frac{15n}{n^2} = \frac{15}{n} \]

Therefore, $\displaystyle{ \left|\frac{3n^2}{n^2+2n+3} - 3 \right| < \frac{15}{n} \leq \epsilon }$ for all $n \geq N$. So our sequence converges to 3.

\vspace{0.1in}

   \item Show that $\displaystyle{ \left\langle \frac{\sin(n)}{n^4+1} \right\rangle }$ converges.\\ {\it Hint:} Ignore $\sin(n)$, then prove $\sin(n)$ is bounded and use a theorem.

\vspace{0.1in}

{\it Note:} The hint isn't that helpful. I originally intended everyone to 
notice that $-1 \leq \sin(n) \leq 1$ and thus $|\sin(n)|\leq 1$ so that 
$\sin(n)$ is bounded and then prove that $1/(n^4+1)$ converges to 0. Once these facts are established, we simply quote the theorem that says ``a bounded sequence $\times$ a sequence which converges to zero is a sequence which converges to zero''. However, it's no harder to prove that $\sin(n)/(n^4+1)$ converges to 0 than proving $1/(n^4+1)$ converges to 0. So we'll just proceed directly.

Same as before, we need to do some scratchwork first.

\vspace{-0.2in}

\[ \left| \frac{\sin(n)}{n^4+1} - 0 \right| = \frac{|\sin(n)|}{n^4+1} \leq \frac{1}{n^4+1} < \frac{1}{n^4} \]

\vspace{-0.1in}

So if $1/n^4 = \epsilon$, then $n^4 = 1/\epsilon$ and thus $n = \sqrt[4]{1/\epsilon}$. Now we're ready to write our proof.

\vspace{0.05in}

\noindent Proof:\\
Suppose $\epsilon > 0$. 
Let $\displaystyle{N = \left\lceil \sqrt[4]{\frac{1}{\epsilon}} \right\rceil}$ [``$\lceil x \rceil$'' is the ceiling function which rounds $x$ up to the next integer]. 

Suppose $n \geq N$. $\displaystyle{n \geq \left\lceil\sqrt[4]{\frac{1}{\epsilon}}\right\rceil \geq 
\sqrt[4]{\frac{1}{\epsilon}}}$ $\Rightarrow$ $\displaystyle{n^4 \geq \frac{1}{\epsilon}}$ $\Rightarrow$ $\displaystyle{\frac{1}{n^4} \leq \epsilon}$
$\Rightarrow$ $\displaystyle{ \left| \frac{\sin(n)}{n^4+1} - 0 \right| = \frac{|\sin(n)|}{n^4+1} \leq \frac{1}{n^4+1} < \frac{1}{n^4} }$.

Note that the ``$\leq$'' holds because the numerator ``$|\sin(n)|$'' is never larger than 1 because $-1 \leq \sin(n) \leq 1$. The ``$<$'' holds because $n^4+1 > n^4$ and decreasing a denominator increases a fraction.

Therefore, $\displaystyle{ \left| \frac{\sin(n)}{n^4+1} - 0 \right| < \frac{1}{n^4} \leq \epsilon }$ for all $n \geq N$. So our sequence converges to 0.

\vspace{0.1in}


   \item Prove that $\displaystyle{ \left\langle \frac{n^2+1}{n} \right\rangle }$ diverges.

\vspace{0.1in}

Notice that $\displaystyle{\frac{n^2+1}{n} \approx \frac{n^2}{n} = n}$ which
is unbounded. So it's safe to guess that our sequence is unbounded and we know that unbounded sequences diverge. Let's prove this.

Suppose $\displaystyle{ \left\langle \frac{n^2+1}{n} \right\rangle }$ is bounded. Then there exists some $B$ such that $\displaystyle{\left| \frac{n^2+1}{n} \right| \leq B}$ for all $n$. However, consider $n = B$. Then
$\displaystyle{\left| \frac{B^2+1}{B} \right| = \frac{B^2+1}{B} > \frac{B^2}{B} = B}$. Contradiction! Therefore, the sequence is unbounded. 

One of our theorems states that all convergent sequences are bounded. Therefore, any unbounded sequence cannot be convergent. Therefore, our sequence must diverge since it is not bounded.

\vspace{0.1in}

   \item Let $a_n \rightarrow A$ and $b_n \rightarrow B$. Show that $a_n+b_n \rightarrow A+B$.

\vspace{0.1in}

Let $\epsilon > 0$. Then since $a_n \to A$ there exists some $N_a$ such that
$|a_n-A|<\epsilon/2$ for all $n \geq N_a$. Likewise, there exists some $N_b$
such that $|b_n-B|<\epsilon/2$ for all $n \geq N_b$. Let $N = \mathrm{max}\{N_a, N_b\}$. Suppose $n \geq N$. Then  $|(a_n+b_n)-(A+B)|=$ $|(a_n-A)+(b_n-B)| \leq$
$|a_n-A|+|b_n-B| <$ $\epsilon/2 + \epsilon/2 = \epsilon$ since $n \geq N \geq N_a$ and $n \geq N \geq N_b$. Therefore, $(a_n+b_n) \to (A+B)$.

\vspace{0.1in}

\end{enumerate}

\noindent {\bf \large 2. (20 points)} Some set stuff.
\begin{enumerate}[(a)]

   \item Let $A,B,C,D$ be sets. Suppose that $A \cup B \subseteq C \cup D$, $A \cap B = \phi$, and $C \subseteq A$.
             Prove that $B \subseteq D$. 

\vspace{0.1in}

Our goal is to show that $B \subseteq D$, so we should begin with an element of $B$ and then try to show it is an element of $D$.

Suppose $x \in B$ $\Rightarrow$ $x \in A \cup B$ $\Rightarrow$ $x \in C \cup D$
since $A \cup B \subseteq C \cup D$. Thus either $x \in C$ or $x \in D$. We need to rule out the former option. Suppose $x \in C$. Then $x \in A$ since $C \subseteq A$. But this would mean that $x \in B$ and $x \in A$ so that $x \in A \cap B$. Contradiction! This is impossible since $A \cap B = \phi$. Therefore,
$x \not\in C$, so $x \in D$. So all the elements of $B$ are also elements of $D$. Therefore, $B \subseteq D$.

\vspace{0.1in}

   \item Let $f:X \rightarrow Y$ and let $T \subseteq Y$.  Prove that if $f$ is onto, then $f(f^{-1}(T))=T$. Point out which ``half'' of your
             proof does {\bf not} need the ``onto'' hypothesis.

\vspace{0.1in}

To show set equality we need to show containment in both directions. All elements in $f(f^{-1}(T))$ are in $T$ and vice-versa. 

\begin{itemize}
\item Suppose $y \in f(f^{-1})(T)$. This implies
that there exists some $x \in f^{-1}(T)$ such that $f(x)=y$. But $x \in f^{-1}(T)$ means that $f(x) \in T$. Therefore, $y=f(x) \in T$ and so
$f(f^{-1}(T)) \subseteq T$.
\item Suppose $y \in T$. We need $y$ to be in the 
image of $f$. At this point we must use our ``onto'' assumption. Since $f$ is
onto, there exists some $x \in X$ such that $f(x)=y$. But notice that
$f(x)=y \in T$. Therefore, $x \in f^{-1}(T)$. So we have shown that $y = f(x) \in f(f^{-1}(T))$. Thus $T \subseteq f(f^{-1}(T))$. 
\end{itemize}

Finally, containment both ways implies equality.

{\it Note:} The onto assumption is necessary. Consider the map $f : \{a\} \to \{ 1,2 \}$ such that $f(a)=1$. Then $f^{-1}(\{2\}) = \phi$ (nothing maps to 2), so
$f(f^{-1}(\{2\}) = f(\phi) = \phi \not= \{2\}$.

\vspace{0.1in}

\end{enumerate}

\noindent {\bf \large 3. (28 points)} For each of the following functions, decide if $f$ is 1-1, onto, both, or neither. {\bf Prove your answers!}
\begin{enumerate}[(a)]

   \item Let $f:\mathbb{R} \rightarrow \mathbb{R}$ be defined by $f(x)=5x+2$ 

\vspace{0.1in}

\begin{description}
\item[Injective] Suppose $f(x)=f(y)$. Then $5x+2=5y+2$ so that $5x=5y$ and thus
$x=y$. Hence, $f$ is one-to-one.
\item[Surjective] Suppose $y \in \mathbb{R}$. [Scratch work: $5x+2=y$ $\Rightarrow$ $5x=y-2$ $\Rightarrow$ $x = (y-2)/5$] Consider $x=(y-2)/5 \in \mathbb{R}$. Then $f(x) = f((y-2)/5) = 5[(y-2)/5]+2 = (y-2)+2=y$. Therefore,
$f$ is onto.
\end{description}

$f$ is both one-to-one and onto. Thus $f$ is a bijection.

\vspace{0.1in}

   \item Let $f:\mathbb{Z} \rightarrow \mathbb{Z}$ be defined by $f(x)=5x+2$ 

\vspace{0.1in}

\begin{description}
\item[Injective] Same as in part (a).
\item[Not Surjective] Using our previous scratch work we can see that the equation $5x+2=y$ can't always be solved for $x \in \mathbb{Z}$. In particular, it doesn't work when $y=0$. 

Suppose $f(x)=0$. Then $5x+2=0$ so $5x=-2$ and thus $x=-2/5 \not\in \mathbb{Z}$.
Therefore, $f(x) \not=0$ for all $x \in \mathbb{Z}$. Thus $0$ is not in the range of $\mathbb{Z}$ and so $f$ is not onto.
\end{description}

$f$ is one-to-one, but not onto.

\vspace{0.1in}

   \item Let $f:\mathbb{Z} \rightarrow \mathbb{Z}$ be defined by $\displaystyle{ f(x) = \left\{ \begin{array}{cl} 2x & x \mathrm{\;is\;even} \\
             x+1 & x \mathrm{\;is\;odd} \end{array} \right. }$ 

\vspace{0.1in}

Let's make a table of values of $f$ to get a feel for how the function works.

\begin{tabular}{|rrrrrr|} \hline
{\Large\strut}    $x=$ & $-2$ & $-1$ & 0 & 1 & 2 \\ \hline
{\Large\strut} $f(x)=$ & $-4$ &    0 & 0 & 2 & 4 \\ \hline
\end{tabular}

\begin{description}
\item[Not Injective] Our table shows that $f$ is not one-to-one.
In particular, $f(-1)=0=f(0)$ but $-1 \not= 0$. 
\item[Not Surjective] The table also leads us to believe the function isn't onto. In fact, no negative numbers get hit. 

Suppose $f(x)=1$. Then if $x$ is even we have that $f(x)=2x=1$ so $x=1/2$. Contradiction! ($1/2$ isn't an integer.) Thus $x$ must be odd, so $f(x)=x+1=1$ which implies that $x=0$. Contradiction! ($0$ is even.) Therefore, there is no $x$ such that $f(x)=1$ and so $1$ is not in the range of $f$. Therefore, $f$ is not onto. 
\end{description}

$f$ is neither one-to-one nor onto.

\vspace{0.1in}

   \item Let $g:X \rightarrow Y$ and $f: Y \rightarrow Z$. Assume that $f \circ g: X \rightarrow Z$ is a bijection. If $f$ {\bf must be} 1-1, prove it. 
   If $f$ might not be 1-1, give a counter-example. If $f$ {\bf must be} onto, prove it. If $f$ might not be onto, give a counter-example. [A counter-example should specify {\bf both} $f$ and $g$ and be accompanied by a proof that it is in fact a counter-example.]

\vspace{0.1in}

\begin{description}
\item[Not Injective] Consider $f:\{1,2\} \to \{1\}$ where $f(1)=f(2)=1$
and $g:\{1\} \to \{1,2\}$ where $g(1)=1$. Then $f \circ g : \{1\} \to \{1\}$ is defined by $(f \circ g)(1) = f(g(1))=f(1)=1$. Notice that $f\circ g$ is the identity function on the set $\{1\}$. $f \circ g$ is clearly bijective.

Notice that $f$ is onto, but not one-to-one since $f(1)=1=f(2)$.
$f$ may fail to be injective.
\item[Surjective] Suppose $z \in Z$. Now $f \circ g$ is bijective.
Thus $f \circ g$ is onto. So there exists some $x \in X$ such that $(f \circ g)(x)=f(g(x))=z$. Taking $y=g(x) \in Y$ we have $f(y)=z$. Thus $z$ is in the image of $f$ and so it is onto.
\end{description}

$f$ must be onto, but can fail to be one-to-one.

\vspace{0.1in}

\end{enumerate}

\noindent {\bf \large 4. (28 points)} Equivalent Nonsense.\\
         Recall that for integers $a$ and $b$, $a \cong b \;(\mathrm{mod\;} 4)$ if and only if there exists some $k \in \mathbb{Z}$ 
         such that $a=b+4k$.
         
\begin{enumerate}[(a)]

   \item Prove that $a \cong b \;(\mathrm{mod\;}4)$ is an equivalence relation on $\mathbb{Z}$.

\vspace{0.1in}

\begin{description}
\item[Reflexive] Suppose $a \in \mathbb{Z}$. Then $a=a+4(0)$. Thus $a \cong a \;(\mathrm{mod\;}4)$.
\item[Symmetric] Suppose $a,b \in \mathbb{Z}$ and $a \cong b \;(\mathrm{mod\;}4)$. Then there exists some $k \in \mathbb{Z}$ such that $a=b+4k$. So $a-4k=b$ and thus $b = a + 4(-k)$ (of course $-k \in \mathbb{Z}$ since $k \in \mathbb{Z}$). Therefore, $b \cong a \;(\mathrm{mod\;}4)$.
\item[Transitive] Suppose $a,b,c \in \mathbb{Z}$, $a \cong b \;(\mathrm{mod\;}4)$, and $b \cong c \;(\mathrm{mod\;}4)$. Then there exits $k,\ell \in \mathbb{Z}$ such that $a = b+4k$ and $b=c+4\ell$. Thus
$a = b+4k = (c+4\ell)+4k = c+4(k+\ell)$ (of course $k+\ell \in \mathbb{Z}$). Therefore, $a \cong c \;(\mathrm{mod\;})$. 
\end{description}


\vspace{0.1in}

   \item List the equivalence classes of this equivalence relation.
   
\vspace{0.1in}

\begin{itemize}
\item $[0] = \{\dots,-8,-4,0,4,8,\dots\} = \{ 4k \,|\, k \in \mathbb{Z} \}$
\item $[1] = \{\dots,-7,-3,1,5,9,\dots\} = \{ 4k+1 \,|\, k \in \mathbb{Z} \}$
\item $[2] = \{\dots,-6,-2,2,6,10,\dots\} = \{ 4k+2 \,|\, k \in \mathbb{Z} \}$
\item $[3] = \{\dots,-5,-1,3,7,11,\dots\} = \{ 4k+3 \,|\, k \in \mathbb{Z} \}$
\end{itemize}

\vspace{0.1in}

   \item Prove that the function $f:\mathbb{Z}_4 \rightarrow \mathbb{Z}_{10}$ defined by $f([n])=[5n]$ is well-defined.
             [$\mathbb{Z}_m$ are the equivalence classes of integers mod $m$.]

\vspace{0.1in}

Well defined means that equivalent inputs give equivalent outputs. Suppose
$[m]=[n] \in \mathbb{Z}_4$ (equal inputs). Then since $[m]=[n]$, $m \cong n \;(\mathrm{mod\;}4)$, so there exists some $k \in \mathbb{Z}$ such that $m=n+4k$ $\Longrightarrow$ $5m=5n+20k$ $\Longrightarrow$ $5m = 5n + 10(2k)$. Therefore, $5m \cong 5n \;(\mathrm{mod\;}10)$ and so $f([m])=[5m]=[5n]=f([n])$ (equal outputs). Therefore, $f$ is well-defined.

{\it Note:} If out map had been $f([n])=[6n]$, this argument would fail. In fact, $[0]=[4]$ in $\mathbb{Z}_4$, but $f([0])=[0]$ is not equal to $f([4]) = [24]=[4]$ in $\mathbb{Z}_{10}$.

\vspace{0.1in}

   \item Let $n \in \mathbb{Z}$ be a sum of squares. [That is there exist integers $a$ and $b$ such that $n=a^2+b^2$.] 
             Prove that $n \not\cong 3 \;(\mathrm{mod\;}4)$.

\vspace{0.1in}

Recall that addition and multiplication modulo 4 are well-defined. So we can swap out any integer with another integer as long as they are equal mod 4.

Suppose $n=a^2+b^2$ for some $a,b \in \mathbb{Z}$. Then $a,b \cong$ 
0, 1, 2, or 3 (mod 4). Note that $0^2,1^2,2^2,3^2 = 0,1,4,9 \cong 0,1,0,1 \;(\mathrm{mod\;}4)$. Thus $a^2+b^2 \cong 0^2+0^2, 0^2+1^2, 1^2+0^2, \mathrm{\;or\;} 1^2+1^2 \cong 0,1,\mathrm{\;or\;}2\;(\mathrm{mod\;}4)$. Therefore, it is impossible for $n$ to be equivalent to 3 modulo 4 if $n$ is the sum of squares.

\end{enumerate}

\end{document}
