\documentstyle[12pt,twoside,amssymb]{article}
\input{macros-course}
%	\addtolength{\topmargin}{-.35in}
%	\setlength{\textheight}{9in}

\begin{document}

\psol{2}{February 24, 1995}

\bigskip

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Problem 1
\problem 
Define the composition $P\circ Q$ of two relations as follows: \\
If $Q \subseteq A\times B$ and $P \subseteq B \times C$ then $P \circ Q =
\{(a,c) : 
%\mbox{ there exists } b \mbox{ such that } (a,b) \in P \mbox{ and
\exists b \mbox{ such that } (a,b) \in Q \mbox{ and } (b,c) \in P\}$.  
Note that $P \circ Q \subseteq A \times C$.  

Let $R \subseteq S \times S$ be a relation.  
Prove or disprove each of the following statements.
\bparts
\ppart If $R$ is transitive, then $R \circ R$ is transitive.

\begin{proof}
Let $(a,b) \in R \circ R$ and $(b,c) \in R \circ R$.  
We want to show that $(a,c)$ is in $R\circ R$, so we need to find
an $x$ such that $(a,x)$ and $(x,c)$ are both in $R$.

Since $(a,b)\in R\circ R$, there exists a $d$ such that 
$(a,d)$ and $(d,b)$ are in $R$. 
Since $R$ is transitive, it follows that $(a,b)\in R$.
Similarly, there exists an $e$ such that $(b,e)$ and $(e,c)$ are in $R$,
and so $(b,c)\in R$.  Taking $x=b$, we are done.
\end{proof}

\ppart If $R$ is transitive, then $R \circ R \subseteq R$.

\begin{proof}
Let $(a,c) \in R \circ R$.  Then there exists $b$ such that $(a,b)$ and
$(b,c)$ are both in $R$.  Since R is transitive $(a,c) \in R$.  Therefore
$R\circ R \subseteq R$.
\end{proof}

\ppart If $R \circ R \subseteq R$, then $R$ is transitive.

\begin{proof}
Let $(a,b), (b,c) \in R$. Then $(a,c) \in R \circ R$.  Since $R \circ R
\subseteq R$, $(a,c) \in R$ and so $R$ is transitive.

\end{proof}
\eparts

% Problem 2
\problem  Prove or disprove the following identities:
\bparts
\ppart $A \times (B \cap C) = (A \times B) \cap (A \times C)$

\begin{proof}
To prove this identity we need to show the following two containments:
\begin{enumerate}
\item \ $A \times (B \cap C) \subseteq (A \times B) \cap (A \times C)$.
Let $(x,y) \in A \times (B \cap C)$.  Then $(x,y) \in A \times B$ since
$x \in A \text{ and } y \in B$. Similarly $(x,y) \in A \times C$.  Thus
$(x,y) \in (A \times B) \cap (A \times C)$.
\item \ $(A \times B) \cap (A \times C) \subseteq A \times (B \cap
C)$.  Let $(x,y) \in (A \times B) \cap (A \times C)$.  Then $x \in A$ and
$y \in B \cap C$.  Therefore $(x,y) \in A \times (B \cap C)$.
\end{enumerate}
\end{proof}

\ppart $(A \cup B) \times (C \cup D) = (A \times C) \cup (B \times
D)$.  This is false.  To prove this it is enough to give an example
where the equality above doesn't hold.  Let $A = \{1\}, B =
\varnothing, C = \varnothing, D = \{1\}$.  Then $(A \cup B) \times (C
\cup D) = \{(1,1)\}$ but both $A \times C$ and $B \times D$ are empty.

\ppart $(A - B) \times (C - D) = (A \times C) - (B \times D)$.  Again this
is false.  A counterexample is: Let $A = \{1,2\}, B = \{2\}, C = D = \{1\}$.
Then $(A - B) \times (C - D) = \varnothing$ since $C - D = \varnothing$.  But
$A \times C = \{(1,2),(2,1)\}$ and $B \times D = \{(2,1)\}$.  Therefore $(A
\times C) - (B \times D) = \{(1,2)\} \neq \varnothing$.

\ppart $(A \bigtriangleup B) \times (C \bigtriangleup D) = (A \times C)
\bigtriangleup (B \times D)$.  A counterexample is: Let $A =
\varnothing, B = \{1\}, C = \{1\}, D = \varnothing$.  Then $A
\bigtriangleup B = \{1\}, C \bigtriangleup D = \{1\}$ and so $(A
\bigtriangleup B) \times (C \bigtriangleup D) =  \{(1,1)\}$.  However both $A
\times C$ and $B \times D$ are empty and so $(A \times C) \bigtriangleup (B
\times D) = \varnothing$.

\eparts

% Problem 3
\problem  
Let $f^{(i)}(x)$ denote the $i$th derivative of $f(x)$.
Prove that if $f(x)$ and $g(x)$ are real-valued functions of one
variable with derivatives of all orders, then
\[
(f(x)g(x))^{(n)} = \sum_{j=0}^{n} {n \choose j}f^{(n-j)}(x)g^{(j)}(x)
\]

\begin{proof}
We will proceed by induction on $n$.
\begin{description}
\item[Base Case:]\ $n = 1$. $(f(x)g(x))^{(1)} = f^{(1)}(x)g^{(0)}(x) +
f^{(0)}(x)g^{(1)}(x) = \sum_{j=0}^1
f^{(n-j)}(x)g^{(j)}(x)$.
\item[Inductive Step:] Assume that:
\[ (f(x)g(x))^{(n)} = \sum_{j=0}^{n} {n \choose j}f^{(n-j)}(x)g^{(j)}(x) \]
Then $(fg)^{(n+1)} = ((fg)^{(n)})'$.  Thus:
\begin{eqnarray*}
(f(x)g(x))^{(n+1)} & = & \sum_{j=0}^{n} {n \choose j} \left[
f^{(n-j+1)}(x)g^{(j)}(x) +
f^{(n-j)}(x)g^{(j+1)}(x)\right] \\
 & = & \sum_{j=0}^n {n \choose j} f^{(n+1-j)}(x)g^{(j)}(x)+ \sum_{k=1}^{n+1} {n
 \choose k-1} f^{(n+1-k)}(x)g^{(k)}(x) \\
 & & \text{ ($k = j+1$ in the second summation)}\\
 & = & \sum_{j=0}^n \left[ {n \choose j} + {n \choose j-1} \right]
 f^{(n+1-j)}(x)g^{(j)}(x) \\
 & = & \sum_{j=0}^{n+1} {n+1 \choose j} f^{(n+1-j)}(x)g^{(j)}(x) \\
 & & \text{ (from PS1.3)}
\end{eqnarray*}
which is the desired identity for $n+1$.
\end{description}
\end{proof}
% Problem 4

\problem 
You are given an unlimited supply of $4$-cent and $7$-cent
stamps.  What is the largest amount of postage  that you cannot make
with these two denominations?  Prove your answer. 

Some preliminary observations:
\begin{enumerate}
\item We can't make $17$ cents.  Why?  It's impossible to do it using $0$, $1$, or $2$ 7-cent stamps.
\item We can make $18$, $19$, $20$, and $21$ cents.
\begin{itemize}
\item\ $18 = 2 \times 7 + 1 \times 4$
\item\ $19 = 1 \times 7 + 3 \times 4$
\item\ $20 = 0 \times 7 + 5 \times 4$
\item\ $21 = 3 \times 7 + 0 \times 4$
\end{itemize}
\end{enumerate}

We now prove that 17 is the largest amount of postage we can't make.

\begin{theorem}
If $n \geq 18$ then we can make $n$ cents with $4$-cent and $7$-cent stamps.
\end{theorem}

\begin{proof}
We go by induction on $n$.
\begin{description}
\item[Base Case:] $n=18$. See Observation 2.
\item[Inductive Step:] Assume that if $18 \leq k < n$ then we can make
$k$ cents with $4$-cent and $7$-cent stamps.  We have two cases:
\begin{enumerate}
\item If $n-4 < 18$, then $n$ is on the list in Observation 2.
\item If $n - 4 \geq 18$, then we use the inductive hypothesis to make $n-4$
cents and then make $n$ cents by using an extra $4$-cent stamp.
\end{enumerate}
\end{description}
\end{proof}

\end{problems}

\end{document}


