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

\setlength{\unitlength}{0.1in}

\setlength{\oddsidemargin}{-0.50in}
\setlength{\evensidemargin}{-0.50in}
\setlength{\topmargin}{-0.50in}
\setlength{\headheight}{0.0in}
\setlength{\headsep}{0.0in}
\setlength{\topskip}{0.0in}
\setlength{\textheight}{9.4in}
\setlength{\textwidth}{7.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}}}

\newcommand{\ep}{\varepsilon}
\usepackage{mathtools}
\DeclarePairedDelimiter{\ceil}{\lceil}{\rceil}

\newcommand{\prob}[2]{\noindent {\bf\large #1. (#2 points)}\   }

\begin{document}

%\pagestyle{empty}

\noindent
\parbox{2in}{\bf Math 2510} 
\hfill {\Large \bf Test \#2} \hfill
\parbox{2in}{\bf \hfill April $15^{\mathrm{th}}$, 2015}

\vspace{0.2in}

\noindent {\large\bf Name:} \underline{\hskip 1 truein {\Large\sc\color{red} Answer Key}\hskip 1 truein}\hfill \hfill {\bf Be sure to show your work!}

\vspace{0.2in}

\prob{1}{30} Converging Questions
\begin{enumerate}[(a)]

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

	Let $\ep > 0$. Set $N = \mathrm{max} \left\{ \ceil*{\dfrac{1}{\ep}}, 6 \right\}$. Notice that for $n \ge N$ we have $n \geq 6$ so $|n-6|=n-6 < n$.
	For all $n \geq N$,

	\begin{align*}
	\left| \frac{2n^3+n}{n^3+3} - 2 \right| \le \left| \frac{2n^3+n}{n^3+3} - 2\frac{n^3 + 3}{n^3 + 3} \right| \le \left| \frac{n - 6}{n^3 + 3} \right| = \frac{n-6}{n^3+3} < \frac{n}{n^3+3} < \frac{n}{n^3} = \frac{1}{n^2} \le \frac{1}{n} \le \frac{1}{N} \leq \frac{1}{1/\ep} = \ep
	\end{align*}

	Hence, by the definition of convergence, we have that $\displaystyle{ \left\langle \frac{2n^3+n}{n^3+3} \right\rangle }$ converges to $2$. \qed

   \item Prove that $\displaystyle{ \left\langle \frac{(-1)^n n}{n^2+1} \right\rangle }$ converges.

	Let $\ep > 0$. Set $N = \ceil*{\dfrac{1}{\ep}}$. Notice that for $n \ge N$ we have

	\begin{align*}
	\left| \frac{(-1)^n n}{n^2+1} - 0 \right| = \left| \frac{(-1)^n n}{n^2+1} \right| = \frac{n}{n^2+1} < \frac{n}{n^2} = \frac{1}{n} \le \frac{1}{N} \leq \frac{1}{1/\ep} = \ep
	\end{align*}

	Hence, by the definition of convergence, we have that $\displaystyle{ \left\langle \frac{(-1)^n n}{n^2+1} \right\rangle }$ converges to $0$. \qed


   \item Prove that $\displaystyle{ \left\langle \frac{n^4}{n-1} \right\rangle_{n=2}^\infty }$ diverges.

	Suppose by way of contradiction that $\displaystyle{ \left\langle \frac{n^4}{n-1} \right\rangle_{n=2}^\infty }$ is bounded by say $M$. Then for every $n \geq 2$, we have 
	$$\frac{n^4}{n-1} \le M.$$
	Notice that $n^4/(n-1)>0$ so that $M>0$. Consider $n = \ceil*{M} + 1$ (since $\ceil*{M} \geq 1$ because $M>0$, $n \geq 2$). We have
	$$\frac{n^4}{n-1} = \frac{(\ceil*{M} + 1)^4}{(\ceil*{M} + 1) - 1} = \frac{(\ceil*{M} + 1)^4}{\ceil*{M}} > \frac{M^4}{M} = M^3 > M,$$
	a contradiction. So we must have that $\displaystyle{ \left\langle \frac{n^4}{n-1} \right\rangle_{n=2}^\infty }$ is unbounded. As such, it can not be convergent. \qed

   \item Let $a_n \rightarrow L$ (for some $L \in \mathbb{R}$) and $b_n \rightarrow 0$. Show that $a_nb_n \rightarrow 0$.

   As $a_n \rightarrow L$, we must have that $a_n$ is bounded by some number say $M$, so that for all $n$, $|a_n| \le M$. Now, as $b_n \rightarrow 0$, we must have that for any $\ep > 0$, there exists some $N$ such that for all $n \ge N$, we have $|b_n - 0| = |b_n| < \ep$. In particular, for $(\ep/M) > 0$, there must exist some $N$, call it $N_0$, such that for all $n \ge N_0$, $|b_n| < (\ep/M)$. Note then that for all $n \ge N_0$ we have
   $$|a_nb_n - 0| = |a_nb_n| = |a_n||b_n| \le M|b_n| < M\frac{\ep}{M} = \ep.$$
   Hence, by the definition of convergence, we have that $a_nb_n \rightarrow 0$. \qed

\end{enumerate}

\newpage

\prob{2}{20} Some set stuff.
\begin{enumerate}[(a)]

   \item Let $A,B,C$ be sets. Show $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$.

	To show two sets are equal, we must show containment both ways.

	\medskip

	Let $x \in A \cap (B \cup C)$. Then $x \in A$ and $x \in B \cup C$. So, $x \in B$ or $x\in C$. Hence, we must have that $x \in A$ and $x \in B$ or $x \in A$ and $x \in C$. That is, $x \in A \cap B$ or $x \in A \cap C$; regardless, $x \in (A \cap B) \cup (A \cap C)$. We have $A \cap (B \cup C) \subseteq (A \cap B) \cup (A \cap C)$.

	Let $x \in (A \cap B) \cup (A \cap C)$. So $x \in A \cap B$ or $x \in A \cap C$. Thus $x$ must be an element of $A$ and must either be an element of $B$ or $C$. So, $x \in A$ and $x \in B \cup C$ and thence, $x \in A \cap (B \cup C)$. We have $A \cap (B \cup C) \supseteq (A \cap B) \cup (A \cap C)$.

	\medskip
	
	Quick proof: $x \in A \cap (B \cup C)$ $\Longleftrightarrow$ $x \in A$ and $x \in B \cup C$ $\Longleftrightarrow$ $x \in A$ and ($x \in B$ or $x \in C$) $\Longleftrightarrow$ $x \in A$ and $x \in B$ or $x \in A$ and $x \in C$ $\Longleftrightarrow$ $x \in A \cap B$ or $x \in A \cap C$ $\Longleftrightarrow$ $x \in (A \cap B) \cup (A \cap C)$.      
	
	We conclude $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$. \qed

   \item Let $f: X \to Y$ be a function and $T_1,T_2 \subseteq Y$. Show that $f^{-1}(T_1 - T_2) = f^{-1}(T_1)-f^{-1}(T_2)$.

         Keep in mind that $x \in f^{-1}(S)$ if and only if $f(x) \in S$ since $f^{-1}(S)$ is the set of all elements which map to $S$.
         
         \medskip

         $x \in f^{-1}(T_1 - T_2)$ $\Longleftrightarrow$ $f(x) \in T_1 - T_2$ $\Longleftrightarrow$ $f(x) \in T_1$ and $f(x) \not\in T_2$ $\Longleftrightarrow$ $x \in f^{-1}(T_1)$ and $x \not\in f^{-1}(T_2)$ $\Longleftrightarrow$ $x \in f^{-1}(T_1) - f^{-1}(T_2)$.
                  
	\medskip

	We conclude $f^{-1}(T_1 - T_2) = f^{-1}(T_1)-f^{-1}(T_2)$.

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

   Let $y \in f(R_1 \cap R_2)$. Then there exists an $x \in R_1 \cap R_2$ such that $f(x) = y$. So $x \in R_1$ and $x \in R_2$. Hence $f(x) = y \in f(R_1)$ and $f(x) = y \in f(R_2)$. We have $f(x) \in f(R_1) \cap f(R_2)$ and that $f(R_1 \cap R_2) \subseteq f(R_1)\cap f(R_2)$.

   \medskip

   Let $y \in f(R_1) \cap f(R_2)$. Then there exist $x_1 \in R_1$ and $x_2 \in R_2$ such that $f(x_1) = f(x_2) = y$. \fbox{\bf Because $f$ is one-to-one} we may conclude that $x_1 = x_2$. Further, $x_1 \in R_1$ and $x_1 = x_2 \in R_2$ so that $x \in R_1 \cap R_2$. Hence $f(x_1) = y \in f(R_1 \cap R_2)$. We have that $f(R_1 \cap R_2) \supseteq f(R_1)\cap f(R_2)$.

   \medskip

   We conclude $f(R_1 \cap R_2)=f(R_1)\cap f(R_2)$. \qed

\end{enumerate}

\medskip

\prob{3}{25} 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)=x^3+1$ 
   
   \medskip
   
	\fbox{BOTH.}
	
	{\bf One-to-one:} Suppose $f(x_1) = f(x_2)$ then $x_1^3 + 1 = x_2^3 + 1$. From this we see $x_1^3 = x_2^3$, and because the cube root of a number is unique we have that $x_1 = x_2$.

	\medskip

	{\bf Onto:} We show that any element in the codomain can be mapped to. Let $y \in \mathbb{R}.$ Then $\sqrt[3]{y - 1} \in \mathbb{R}$ as well and we have 
	$\mbox{\;}$ \qquad \qquad $f(\sqrt[3]{y - 1}) = (\sqrt[3]{y - 1})^3 + 1 = y -1 + 1 = y.$ \qed

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

   \medskip

   \fbox{NEITHER.}

	{\bf Not one-to-one:} Consider $f(2)$ and $f(-2)$. We have $f(2) = f(-2) = 4$ but $2 \ne -2$.

	\medskip

	{\bf Not onto:} Suppose that $f(x)=-1$. Then $x^2=-1$ and so $x=\sqrt{-1} \not\in \mathbb{Z}$. Therefore, $-1$ isn't in the range of $f$. \qed

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

\medskip

	\fbox{ONLY ONTO.}

	{\bf Not one-to-one:} Note that $f(7) =  (7-1)/2 = 3$ and $f(6) = 6/2 = 3$ but $6 \ne 7.$ \qed

	\medskip

	{\bf Onto:} Consider an arbitrary integer $y$. Then $2y \in \mathbb{Z}$ is even and so $f(2y) = 2y/2 = y$ (using the formula for {\it even} inputs). \qed

\medskip

   \item Show that composing two one-to-one functions yields a one-to-one function and that composing two onto functions yields and onto function.  Specifically, let $f: X \to Y$ and $g: Y \to Z$. Show that $g \circ f$ is one-to-one if we assume both $f$ and $g$ are one-to-one. Then show $g \circ f$ is onto if we assume both $f$ and $g$ are onto.

\medskip

	{\bf One-to-one:} Suppose $g(f(x_1)) = g(f(x_2))$. Becuase $g$ is one-to-one, we must have that $f(x_1) = f(x_2)$. Because $f$ is one-to-one, $x_1 = x_2$. We conclude $g \circ f$ is one-to-one. \qed

	\medskip

	{\bf Onto:} Consider an arbitrary element in $z \in Z$. Since $g$ is onto there must exist some $y \in Y$ such that $g(y) = z$. As $f$ is onto there exists an $x \in X$ such that $f(x) = y$. Therefore, $g(f(x)) = g(y) = z$. We conclude $g \circ f$ onto. \qed 

\medskip

\end{enumerate}


\prob{4}{25} Equivalent Nonsense.
         
\begin{enumerate}[(a)]

   \item Give the definition of an equivalence relation (with details). Then consider $x \sim y$ only if $x \geq y$. This is a relation on $\mathbb{R}$. Why isn't it an equivalence relation?

   An equivalence relation on a set $X$ is a relation $\sim$ which is reflexive, symmetric and transitive. Recall that a relation is
   \begin{itemize}
   \item {{\it reflexive} if $a \sim a$ for all $a \in X$;}
   \item {{\it symmetric} if $a \sim b$ then $b \sim a$ for all $a,b \in X$;}
   \item {{\it transitive} if $a \sim b$ and $b \sim c$ then $a \sim c$ for all $a,b,c \in X$;}
   \end{itemize}

   \medskip

   The relation in question here is not an equivalence relation becauses it is \fbox{\bf not symmetric}. For example: $2 \geq 1$ but $1 \not\geq 2$. (On the other hand, it is reflexive: $x \geq x$ and transitive: $x \geq y$ and $y \geq z$ implies $x \geq z$.)

   \medskip

   \item List the equivalence classes of the relation ``mod $5$'' (on $\mathbb{Z}$).

$$   \begin{array}{rclcc}
   [0] & = & \{k \mid \exists j \in \mathbb{Z} \mbox{ such that } k = 5j\}      & = & \{ \dots,-10,-5,0,5,10,\dots \}\\
{}[1] & = & \{k \mid \exists j \in \mathbb{Z} \mbox{ such that } k = 5j+1\} & = & \{ \dots,-9,-4,1,6,11,\dots \}\\
{}[2] & = & \{k \mid \exists j \in \mathbb{Z} \mbox{ such that } k = 5j+2\} & = & \{ \dots,-8,-3,2,7,12,\dots \}\\
{}[3] & = & \{k \mid \exists j \in \mathbb{Z} \mbox{ such that } k = 5j+3\} & = & \{ \dots,-7,-2,3,8,13,\dots \}\\
{}[4] & = & \{k \mid \exists j \in \mathbb{Z} \mbox{ such that } k = 5j+4\} & = & \{ \dots,-6,-1,4,9,14,\dots \}\\
   \end{array} $$

   \item Prove that the function $f:\mathbb{Z}_6 \rightarrow \mathbb{Z}_{22}$ defined by $f([n])=[11n]$ is well-defined. Then show that $g:\mathbb{Z}_6 \to \mathbb{Z}_{10}$ ``defined'' by $g([n])=[11n]$ is not well-defined.
             [$\mathbb{Z}_m$ are the equivalence classes of integers mod $m$.]

\medskip

   Consider $[x],[y] \in \mathbb{Z}_6$. Then $x = y + 6k$ for some $k \in \mathbb{Z}$. This implies that $11x = 11y + 66k$ so $11x = 11y + 22(3k)$. Therefore, $f([x])=[11x]=[11y]=f([y])$ in $\mathbb{Z}_{22}$. Hence, $f$ is well defined.

   \medskip

   Note $[1] =  [7]$ in $\mathbb{Z}_6$ and that $g([1]) = [11] = [1]$ in $\mathbb{Z}_{10}$ and $g([7]) = [77] = [7]$ in $\mathbb{Z}_{10}$. However, $g([1]) = [1] \ne [7] = g([7])$ in $\mathbb{Z}_{10}$. So $g$ is not well defined (equivalent inputs do {\it not} yield equivalent outputs).

   \item Let $x \in \mathbb{Z}_{>0}$ (a positive integer). We can write $x$ in decimal form: $x=d_\ell \cdots d_1d_0$ ($d_j$ is the $j^\mathrm{th}$ digit). Actually, $x = d_\ell \cdot 10^\ell + \cdots + d_2 \cdot 10^2 + d_1 \cdot 10 + d_0$ (where $d_j \in \{0,\dots,9\}$).
   
   Explain why $x$ is divisible by $3$ if and only if $d_\ell+\cdots+d_0$ (the sum of its digits) is divisible by $3$. [{\it Hint:} mod 3]
   
  	Recall that $x$ is divisible by $3$ if and only if $x \equiv 0$ (mod 3). So consider $x = d_\ell \cdot 10^\ell + \cdots + d_2 \cdot 10^2 + d_1 \cdot 10 + d_0$ (where $d_j \in \{0,\dots,9\}$). Then
	
  	\begin{align*}
  	x & \equiv  d_\ell \cdot 10^\ell + \cdots + d_2 \cdot 10^2 + d_1 \cdot 10 + d_0 \mbox{ (mod 3)}\\
  	& \equiv d_\ell \cdot 1^\ell + \cdots + d_2 \cdot 1^2 + d_1 \cdot 1 + d_0 \mbox{ (mod 3)}\\
  	& \equiv d_\ell+ \cdots + d_2+ d_1 + d_0 \mbox{ (mod 3)}\\
  	\end{align*}
	
	Since $10 \equiv 1 \mbox{ (mod 3)}$, we could replace each $10^j$ with $1^j=1$ in the above calculation.
	Therefore, $x \equiv 0 \mbox{ (mod 3)}$ if and only if $d_\ell+ \cdots + d_2+ d_1 + d_0 \equiv 0 \mbox{ (mod 3)}$.
	This means that $x$ is divisible by 3 if and only if $d_\ell+\cdots+d_1+d_0$ is divisible by 3.
	 \qed

\end{enumerate}

\end{document}
