\documentclass[12pt]{article}
\usepackage{latexsym,amsmath,amssymb,epic,eepic,pstcol,graphicx}

%\usepackage{my_teach}

%\pagestyle{myheadings}
\markright{MATH 243, section 2, Midterm 1}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{0in}
\setlength{\textheight}{8.5in}

\newcommand{\Blank}{$\underline{\phantom{Please write your name in this
        space}}$} 
\newcommand{\Strut}{$\vphantom{\Big|}$}

\begin{document}

\begin{center}

\textbf{College of the Holy Cross, Fall Semester, 2017} \\
\textbf{MATH 243, Section 2 -- Midterm 1} \\
\textbf{Friday, September 29}
\end{center}

\vskip 10pt 
\noindent.

\begin{enumerate}

\item{} 
\begin{enumerate}
\item[(a)] (15) Construct the truth table for the statement 
$$(({\rm not}\ Q)\ {\rm and}\ (P\ {\rm implies}\ Q))\ {\rm implies}\ ({\rm not}\ P).$$
\item[] {\it Solution:} 
The truth table for  $(({\rm not}\ Q)\ {\rm and}\ (P\ {\rm implies}\ Q))\ {\rm implies}\ ({\rm not}\ P)$
looks like this:
$$\begin{array}{lllllllll}
P & Q & ((&{\rm not}\ Q)\ &{\rm and}\ (P\ &{\rm implies}\ Q))\ &{\rm implies}\ &({\rm not}\ P)\\ \hline
T & T &     &F              &F            &T     &T  &F \\
T & F &     &T              &F             &F    &T  &F \\
F & T &     &F              &F             &T    &T  &T \\
F & F &     &T              &T             &T    &T  &T\\
\end{array}$$
(The next to last column is the truth value of the whole statement.)
\item[(b)] (5)  Suppose you know that $x \in {\bf R}$ implies that 
$x^2 \ge 0$ and someone one hands you a mathematical object $x$ for 
which you can define $x^2$, and for which $x^2$ is a real number
with $x^2 < 0$.  What can you conclude?
\item[] {\it Solution:}  Let $P$ be the statement $x \in {\bf R}$ and let
$Q$ be the statement $x^2 \ge 0$.  By part (a), you can say that ${\rm not} P$
must be true, so $x$ is not a real number.  
\end{enumerate}
\item{} Let 
\begin{align*}
A &= \{x \in \mathbb{Z} : x = 3k + 1, {\rm some}\ k \in \mathbb{Z}\}\\
B &= \{x \in \mathbb{Z} : x = 4k, {\rm some}\ k \in \mathbb{Z}\}\\
C &= \{-9,-8,-7,-6,-5,-4,-3,-2,-1\}.
\end{align*}
\begin{enumerate}
\item[(a)] (7)  What is the set $(A \cup B)\cap C$?
\item[] {\it Solution:}  $(A \cup B) \cap C$ consists of the elements
in $C$ that are also either in $A$ or $B$ or in both.  This gives
$$(A \cup B)\cap C = \{-8,-5,-4,-2\}.$$
\item[(b)] (7)  What is the set $B^c \cap C$?
\item[] {\it Solution:}  The complement of $B$ is the set of integers
that are not multiples of $4$.  The intersection of that set with $C$
is $\{-9,-7,-6,-5,-3,-2,-1\}$.  
\item[(c)] (6)  Prove or disprove:  $4A \subseteq A \cap B$, where 
$4A = \{4x : x \in A\}$.  
\item[] {\it Solution:}  This is true because, for instance, if $x \in 4A$, then
$x = 4\cdot(3k + 1) = 12k + 4$ for some $k \in \mathbb{Z}$.  This says 
$x \in B$ directly since $3k + 1 \in \mathbb{Z}$.  But we also have $x = 12k + 4 = 3\cdot (4k + 1) + 1$, 
so $x \in A$.  Hence $x \in A\cap B$ and this shows $4A \subseteq A\cap B$.  
\end{enumerate}
\item{}  Consider the statement about $x \in \mathbb{Z}$:  If $x^2 \notin 1 + 4\mathbb{Z}$, 
then $x$ is even.   
\begin{enumerate}
\item[(a)] (10)  What is the contrapositive form of this implication? 
\item[] {\it Solution:}  If $x$ is odd, then $x^2 \in 1 + 4\mathbb{Z}$.  (Note:  ``not even''
is the same as odd here!)
\item[(b)] (10)  Prove the contrapositive form.  What does this imply about
the original statement.  
\item[] {\it Solution:}  If $x$ is odd, then $x = 2k + 1$ for some $k \in \mathbb{Z}$.
Hence $x^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 4(k^2 + k) + 1$.  Since $k$ is an integer,
so is $k^2 + k$.  This shows $x^2 \in 1 + 4\mathbb{Z}$.  This also proves the implication
given in the statement of the problem because that is logically equivalent to 
the contrapositive form.
\end{enumerate}
\vskip 10pt
\item{} (20) Let 
\begin{align*}
A &= \{x \in \mathbb{Z} : x = -2 + 5k\ {\rm for\ some}\ k\in \mathbb{Z}\}\\
B &= \{x \in \mathbb{Z} : x = 3 + 5k\ {\rm for\ some}\ k \in \mathbb{Z}\}.
\end{align*}
Is $A = B$?  Prove your assertion.   
\vskip 10pt
\noindent
{\it Solution:}  These sets are equal (as you will start to see if you list
out some of their elements).  Here is a proof of $A = B$:
\vskip 10pt
\noindent
$\subseteq:$ let $x \in A$.  Then $x = -2 + 5k$ for some integer $k$.  We can
rewrite this as $x = (-2 + 5) + 5(k-1) = 3 + 5(k-1)$.  Since $k \in \mathbb{Z}$, 
$k - 1 \in \mathbb{Z}$ as well and this shows $x \in B$.  Hence $A \subseteq B$.
\vskip 10pt
\noindent
$\supseteq:$ Now we show the reverse inclusion.  Let $x \in B$
Then $x = 3 + 5k$ for some $k \in \mathbb{Z}$.  We can rearrange that as
follows $x = 3 - 5 + 5(k+1) = -2 + 5(k+1)$.  Since $k\in \mathbb{Z}$, $k + 1\in \mathbb{Z}$
as well and this shows $x \in A$.  Hence $B \subseteq A$.

\vskip 10pt
\noindent
Since $A \subseteq B$ and $B \subseteq A$, we have $A = B$.  
\vskip 10pt
\item{} (20) Prove by mathematical induction:  If $a,d$ are any constants and
$n \ge 0$ is a natural number, then
$$a + (a + d) + (a + 2d) + \cdots + (a + nd) =  \frac{n+1}{2}\cdot\left(2a + nd\right).$$ 
\vskip 10pt
\noindent
{\it Solution:}  The base case is $n = 0$, and the formula in that case says
$a = \frac{1}{2}(2a + 0\cdot d) = a$, which is true.  Now assume
$$a + (a + d) + (a + 2d) + \cdots + (a + kd) =  \frac{k+1}{2}\cdot\left(2a + kd\right)$$
And consider the sum with $n=k+1$.  As typically happens in these proofs of 
summation formulas, the sum for $n = k$ consists of the first group of terms.  So
after substituting from the induction hypothesis, we get 
$$\frac{k+1}{2}\cdot\left(2a + kd\right) + (a + (k+1)d).$$
If we separate out the $a$ and the $d$ terms we can see this is
$$((k+1)a + a) + \frac{k(k+1)}{2}\cdot d + (k+1)d = (k+2)a + \frac{(k+1)(k+2)}{2}\cdot d.$$
Hence by factoring out $\frac{(k + 2}{2}$, this can be written in the form 
$$\frac{(k+2)}{2}(2a + (k+1)d),$$
which gives what we wanted to show.

\end{enumerate}


\end{document}


