\documentclass[11pt]{article}
\usepackage{latexsym,amsmath,amssymb}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{0in}
\setlength{\textheight}{8.0in}
\begin{document}
\centerline{Mathematics 243, section 3 -- Algebraic Structures}
\centerline{Solutions for Problem Set 4}
\centerline{{\bf due:} October 5, 2012}
\vskip 10pt
\noindent
{\it `A' Section}
\bigskip
\begin{enumerate}
\item[1.]  Consider the following relations defined on the set $\mathbb{Z}$.
In each case, say whether the relation is reflexive, symmetric, transitive.
Justify your answers.
\begin{enumerate}
\item[a.] $xRy$ if and only if $(-1)^x = (-1)^y$
\item[] {\it Solution:}  We see
$$(-1)^x = \begin{cases} +1 & \text{ if } x \text{ is even}\\
                  -1 & \text{ if } x \text{ is odd}
           \end{cases} $$
Hence $xRx$ is true for all $x$, so $R$ is reflexive.  Similarly, 
if $xRy$ then $x,y$ are both even or both odd.  So $yRx$ follows, and
$R$ is symmetric.  Finally $R$ is transitive since $xRy$ and 
$yRz$ imply $x,y,z$ are either all even or all odd.  
\item[b.] $xRy$ if and only if $x\cdot y \ge 0$
\item[] {\it Solution:}  $xRx$ is true for all $x\in \mathbb{Z}$, since
$x^2 \ge 0$. So $R$ is reflexive.  Similarly, $R$ is symmetric since
multiplication in $\mathbb{Z}$ is commutative, so $xy = yx$ and if $xy \ge 0$, 
$yx \ge 0$ too.  $R$ is {\it not transitive}
since for instance $(1)R(0)$ is true and $(0)R(-1)$ is true, but $(1)R(-1)$ is not true.
\item[c.] $xRy$ if and only if $|x - y| \le 2$
\item[] {\it Solution:}  This is similar to b in the sense that this
relation is reflexive since $|x - x| = 0 \le 2$ for all $x$, and 
symmetric since $|x - y| = |y - x|$ for all $x,y\in \mathbb{Z}$.  But it
is not transitive, since for example $(-2)R(0)$ is true since $|(-2) - 0| = 2\le 2$
and $(0)R(2)$ is true since $|0 - 2| = 2 \le 2$, but $(-2)R(2)$ is not true since
$|-2 - 2| = 4$.  
\item[d.] $xRy$ if and only if $x$ has the same number of base 10
digits as $y$, ignoring signs of $x,y$.    
\item[] {\it Solution:}  This is reflexive -- every $x$ has the same number
of base 10 digits as itself.  Similarly, it is symmetric since if $x$ has the 
same number of digits as $y$, then $y$ has the same number of digits as $x$.
It is also transitive, since if $x$ and $y$ have the same number of digits
and $y$ and $z$ have the same number of digits, then so do $x$ and $z$.
\item[e.] $xRy$ if and only if the sum of the base 10 digits of 
$x$ is the same as the sum of the base 10 digits of $y$, ignoring
signs of $x,y$.  
\item[] {\it Solution:}  This is reflexive, symmetric, and transitive 
as in part d (just replace ``number of digits'' by ``sum of digits'' everywhere).  
\end{enumerate}
\item[2.]   Which of the relations in question 1 are equivalence 
relations?  For those that are, say exactly which integers make
up the equivalence class $[11]$ using correct set notation.  
\item[] {\it Solution:}  From the answers to question 1, the relation in a
is an equivalence relation and 
$$[11] = \{m \in \mathbb{Z} \mid m \text{\ is odd}\}$$
The relation in d is also an equivalence relation.  The equivalence class
of $[11]$ consists of all positive or negative integers that have the exactly two 
digits in their base 10 forms:
$$[11] = \{\pm 10, \pm 11, \pm 12, \ldots, \pm 99\}.$$
Finally, the relation in part e is also an equivalence relation.  The class
of 11 consists of all numbers whose digits add up to 2:
$$[11] = \{\pm 2, \pm 20, \pm 200, \ldots, \pm 11, \pm 101, \pm 110, \ldots\}$$
(Note: there can be any number of $0$ digits in these.)
\item[3.]  Let $R$ be the relation on $\mathbb{Z}$ defined by
$xRy$ if and only if $4x - 15y$ is a multiple of $11$.  Show
that $R$ is an equivalence relation and describe all of the 
equivalence classes for $R$.  
\item[] {\it Solution:}  For all integers $x$, $xRx$ is true since $4x - 15x = 11\cdot (-x)$
is a multiple of $11$. Hence $R$ is reflexive.
If $xRy$, then $4x - 15y = 11k$ for some integer $k$.  But then 
$4y - 15x = -(4x - 15y) - 11x - 11y = 11(-k-x-y)$ is a multiple of 11, so $yRx$ follows.
Hence $R$ is symmetric.  Finally, if $xRy$ and $yRz$ then $4x - 15y = 11k$ and $4y - 15z = 11\ell$
for some integers $k, \ell$.  But then $4x - 15y + 4y - 15z = 11(k + \ell)$, so 
$4x - 15z = 11(k + \ell + y)$ is also a multiple of 11.  It follows that 
$xRz$ is true, so $R$ is transitive.  This shows that $R$ is an equivalence relation.

The equivalence class of any $x \in \mathbb{Z}$ is the set
$$[x] = \{y \mid xRy\} = \{y \mid 4x - 15y = 11k, \text{ for some integer } k\}$$
It can be seen that there are only 11 different classes: 
\begin{align*}
[0] &= \{\ldots, -22, -11, 0, 11, 22, \ldots\}\\
[1] &= \{\ldots, -21, -10, 1, 12, 23, \ldots\}\\
    &\vdots\\
[10] &= \{\ldots, -12, -1, 10, 21, 32, \ldots\}
\end{align*}
\item[4.]  Decide whether each of the following statements
is true.  For those that are true, give a short proof using 
the postulates for $\mathbb{Z}$ given in \S 2.1 of the text.
For those that are false, give a counterexample.
\begin{enumerate}
\item[a.]  If $xy = xz$ for integers $x,y,z$, then $y = z$.
\item[] {\it Solution:}  This is false:  let $x = 0$, $y = 1$, $z = 2$.  
\item[b.]  If $x < y$, then $x^2 < y^2$.
\item[] {\it Solution:}  This is also false:  Let $x = -3$ and $y = 2$.
Then $x < y$, but $x^2 > y^2$.  
\item[c.]  If $z - x < z - y$, then $y < x$.
\item[] {\it Solution:}  This is true.  If $z - y > z - x$, then 
$(z - y) - (z - x) \in \mathbb{Z}^+$.  But that says $x - y \in \mathbb{Z}^+$, so
by the definition of the order relation $x > y$.     
\end{enumerate}
\end{enumerate}
\vskip 10pt
\noindent
{\it `B' Section}
\vskip 10pt
\begin{enumerate}
\item[1.]  In class we showed that the distinct equivalence
classes of an equivalence relation $R$ on a set $A$ give 
a partition of $A$.  Conversely, suppose 
$$A = \bigcup_{\lambda \in {\cal L}} A_\lambda$$
is a partition of $A$.  Show that the relation $R$ on 
$A$ defined by $aRa'$ if and only if $a,a'$ are both
elements of the same subset $A_\lambda$ is an equivalence
relation.
\item[] {\it Solution:}  Let $a \in A$.  Then $a$ is contained
in only one of the $A_\lambda$, since they form partition.  That
implies $aRa$ is true, and $R$ is reflexive.  Next, suppose $xRy$.
That means that $x$ and $y$ are in the same set in the partition, so it 
follows that $y$ and $x$ are also in the same set.  Hence $yRx$ is also 
true and $R$ is symmetric.  Finally, if $xRy$ and $yRz$ are both true
then $x,y,z$ are all in the same set in the partition so $xRz$ is also
true.  This shows $R$ is transitive too, hence an equivalence relation.
\item[2.]  In both parts of this problem, you will be
working in $\mathbb{Z}$, using the postulates from \S 2.1
\begin{enumerate}
\item[a.]  Show that if $x\cdot y = 0$, then $x = 0$ or 
$y = 0$.  (Hint:  Argue by contraposition.  By the trichotomy postulate 4, if $x \ne 0$,
then $x \in \mathbb{Z}^+$ or $-x \in \mathbb{Z}^+$, and 
the same is true for $y$.)  
\item[] {\it Solution:}  We want to show that if $x \ne 0$ and $y \ne 0$, then 
$xy \ne 0$.  By postulate 4 in the book's numbering, if $x \ne 0$, then
$x \in \mathbb{Z}^+$ or $-x \in \mathbb{Z}^+$.  Similarly, $y \in \mathbb{Z}^+$
or $-y \in \mathbb{Z}^+$.  There are four possible combinations of statements
that can be true here.  If $x\in \mathbb{Z}^+$ and $y \in \mathbb{Z}^+$, then 
$xy \in \mathbb{Z}^+$ by postulate 4b.  If $-x\in \mathbb{Z}^+$ and $y \in \mathbb{Z}^+$, 
then $(-x)y \in \mathbb{Z}^+$ by postulate 4b.  But $(-x)y = -(xy) \in \mathbb{Z}^+$ by Theorem 2.2,
and then $xy \ne 0$.  Similarly, $x\in \mathbb{Z}^+$ and $-y \in \mathbb{Z}^+$, 
then $x(-y) \in \mathbb{Z}^+$ by postulate 4b.  But $x(-y) = (-y)x = -(yx) \in \mathbb{Z}^+$ by Theorem 2.2,
and then $yx = xy \ne 0$.  Finally, $-x\in \mathbb{Z}^+$ and $-y \in \mathbb{Z}^+$, 
then $(-x)(-y) \in \mathbb{Z}^+$ by postulate 4b.  But $(-x)(-y) = xy \in \mathbb{Z}^+$ by Exercise 5 in this section of the book (proof follows same idea as the proof $(-1)(-1) = 1$ done in class)
and then $xy \ne 0$.
\item[b.]  From part a, deduce the cancellation law in 
$\mathbb{Z}$:  If $x\cdot y = x\cdot z$ and $x \ne 0$, then
$y = z$.
\item[] {\it Solution:}  If $x\cdot y = x\cdot z$, then $x\cdot (y - z) = 0$.
We are assuming $x \ne 0$, so part a implies $y - z = 0$, and hence $y = z$.   
\end{enumerate}
\item[3.]  Prove by mathematical induction:
\begin{enumerate}
\item[a.]  For all $n \in \mathbb{Z}^+$, 
$$1^2 + 2^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6}.$$
\item[] {\it Solution:}  The base case here is $n = 1$.  The formula is true in that case
because $1^2 = 1 = \frac{1\cdot 2 \cdot 3}{6}$.  Now assume the formula is true for $k \in \mathbb{Z}$, 
and consider the case $n = k+1$.  We have, using the induction hypothesis and some algebra:
\begin{align*}
1^2 + 2^2 + \cdots + (k+1)^2 &= (1^2 + 2^2 + \cdots + k^2) + (k+1)^2 \\
&= \frac{k(k+1)(2k+1)}{6} + (k+1)^2\\
&= \frac{(k+1)(2k^2 + k + 6(k+1))}{6}\\
&= \frac{(k+1)(2k^2 + 7k + 6)}{6}\\
&= \frac{(k+1)(k+2)(2k + 3)}{6},
\end{align*}
which is what we wanted to show since 
$$\frac{(k+1)(k+2)(2k + 3)}{6} = \frac{(k+1)((k+1) + 1)(2(k+1) + 1)}{6}.$$
\item[b.]  For all $n \in \mathbb{Z}^+$,
$$\frac{1}{1\cdot 2} + \frac{1}{2\cdot 3} + \cdots + \frac{1}{n(n+1)} = \frac{n}{n + 1}$$
\item[] {\it Solution:}  The base case here is $n = 1$.  The formula is true in that case
because $\frac{1}{1\cdot 2} = \frac{1}{2} = \frac{1}{1 + 1}$.  
Now assume the formula is true for $k \in \mathbb{Z}$, 
and consider the case $n = k+1$.  We have, using the induction hypothesis and some algebra:
\begin{align*}
\frac{1}{1\cdot 2} + \frac{1}{2\cdot 3} + \cdots + \frac{1}{(k+1)(k+2)} 
&= \left(\frac{1}{1\cdot 2} + \frac{1}{2\cdot 3} + \cdots + \frac{1}{k(k+1)}\right) + \frac{1}{(k+1)(k+2)} \\
&= \frac{k}{k+1} + \frac{1}{(k+1)(k+2)}\\
&= \frac{k(k+2) + 1}{(k+1)(k+2)}\\
&= \frac{k^2 + 2k + 1}{(k+1)(k+2)}\\
&= \frac{(k+1)^2}{(k+1)(k+2)}\\
&= \frac{k+1}{k+2},
\end{align*}
which is what we wanted to show since 
$$\frac{k+1}{k+2} = \frac{k+1}{(k+1) + 1}.$$
\item[c.]  For all $n \ge 2$, $n^3 > 1 + 2n$.
\item[] {\it Solution:}  The base case is $n = 2$, and the inequality is true
in that case since $8 > 5$.  Now assume $k^3 > 1 + 2k$ and consider $(k+1)^3 = k^3 + 3k^2 + 3k + 1$
By the induction hypothesis, we see $(k+1)^3 > 1 + 2k + 3k^2 + 3k + 1 > 1 + 2(k + 1)$, 
since $3k^2 + 3k + 1 > 3k + 1 > 2$ for all $k \ge 2$.  
\item[d.]  If $|A| = n$, then $|{\mathcal P}(A)| = 2^n$.  (Hint:  For the induction 
step, let $A = \{a_1,\ldots,a_k,a_{k+1}\}$.  Every subset of $A$ is of one of
two types -- the ones containing $a_{k+1}$ and the ones not containing $a_{k+1}$.
Count the number of subsets of each type by using the induction hypothesis.)
\item[] {\it Solution:}  When $n = 0$, $A = \emptyset$ has exactly 1 subset, namely
$\emptyset$.  Therefore $|{\mathcal P}(A)| = 1 = 2^0$.  So the base
case is established.  Now assume that $|{\mathcal P}(A)| = 2^k$ whenever 
$|A| = k$ and consider $A = \{a_1,\ldots,a_k,a_{k+1}\}$.  Following the hint,
note that 
$${\mathcal P}(A) = S_1 \cup S_2$$
where $S_1 = \{T \subseteq A \mid a_{k+1} \in T\}$ and 
$S_2 = \{T \subseteq A \mid a_{k+1} \notin T\}$.  By their definitions, $S_1 \cap S_2 = \emptyset$, so 
$$|{\mathcal P}(A)| = |S_1| + |S_2|.$$
The subsets in $S_2$ are in one-to-one correspondence with the subsets of $\{a_1,\ldots,a_k\}$.
Hence $|S_2| = 2^k$ by the induction hypothesis.  Every subset $T$ in $S_1$ contains $a_{k+1}$,
so it can be written as $T = T' \cup \{a_{k+1}\}$, where $T'$ is a subset of $\{a_1,\ldots,a_k\}$.
Distinct $T'$'s give distinct $T$'s so there are exactly as many elements of $S_1$ as subsets
of $\{a_1,\ldots,a_k\}$.  By the induction hypothesis again, that number is $2^k$.  Hence
$$|{\mathcal P}(A)| = |S_1| + |S_2| = 2^k + 2^k = 2\cdot 2^k = 2^{k+1}.$$
Therefore $|{\mathcal P}(A)| = 2^n$ for all $n \ge 1$ by induction.  
\end{enumerate}
\item[4.]  The binomial coefficients are the numbers 
$$\binom{n}{\ell} = \frac{n!}{\ell!(n-\ell)!}$$
(where $0! = 1$ by convention).  
\begin{enumerate}
\item[a.]  Show using the definition that for all $\ell$ with $1 \le \ell \le n$, 
$$\binom{n}{\ell} + \binom{n}{\ell-1} = \binom{n+1}{\ell}$$
\item[] {\it Solution:}  We have 
$$\binom{n}{\ell} + \binom{n}{\ell-1} = \frac{n!}{\ell!(n-\ell)!} + \frac{n!}{(\ell-1)!(n - \ell + 1)!}$$
The common denominator for these two fractions is $\ell!(n - \ell + 1)!$, so adding we
have
$$\frac{n!}{\ell!(n-\ell)!} + \frac{n!}{(\ell-1)!(n - \ell + 1)!} = 
\frac{n!(n - \ell + 1 + \ell)}{\ell!(n + 1 - \ell)!}
= \frac{(n+1)!}{\ell!(n+1-\ell)!} = \binom{n+1}{\ell}.$$ 
\item[b.]  (The Binomial Theorem)  Show by induction that for all $n\ge 1$.  
$$(a + b)^n = \sum_{\ell=0}^n \binom{n}{\ell} a^\ell b^{n-\ell}$$
(that is, the numbers $\binom{n}{k}$ are exactly the coefficients of the various
terms $a^k b^{n-k}$ appearing in the expansion of $(a + b)^n$).  
\item[] {\it Solution:}  The base case $n = 1$ follows since $\binom{1}{0} = 1 = \binom{1}{1}$,
and $(a+b)^1 = a + b = \binom{1}{0} b + \binom{1}{1} a$.

Now assume the theorem has been proved for $n = k$ and consider the case $n = k+1$.
We have by the induction hypothesis,
\begin{align*}
(a + b)^{k+1} &= (a + b)^k (a + b)\\
              &= \left(\sum_{\ell = 0}^k \binom{k}{\ell} a^\ell b^{k-\ell}\right) (a + b).
\end{align*}
Expand the product on the last line using the distributive law
and collect like terms.  The coefficients of $a^{k+1}$
and $b^{k+1}$ are both equal to 1 by inspection.  These match the formula to be proved since
$\binom{k+1}{k+1} = \binom{k+1}{0} = 1$.  Now assume $1 \le \ell \le k$.  The $a^\ell b^{k + 1 - \ell}$
term comes from 
$$b\cdot \left(a^\ell b^{k - \ell} \text{ term in first factor }\right) + a\cdot
\left( a^{\ell-1} b^{k - (\ell - 1)} \text{ term in first factor }\right).$$
From above (by the induction hypothesis), the coefficient of this term is
$$\binom{k}{\ell} + \binom{k}{\ell - 1} = \binom{k+1}{\ell},$$
where the right side comes by applying part a of this question.
Therefore 
$$(a + b)^{k+1}
= \sum_{\ell = 0}^{k+1} \binom{k+1}{\ell} a^\ell b^{k+1-\ell},$$
and the result follows by induction. 
\end{enumerate}
\end{enumerate}
\end{document}
