\documentstyle[6.045-ps,epsfile,12pt]{article}

\name{Marc Horowitz}
\psnum{1}
\duedate{Friday, February 15}
\section{Bronwyn Eliot, Thursday 1pm}
\handoutnum{2}

\begin{document}
\problem{1}{Induction}

Prove: \[1^3 + 2^3 + \cdots + n^3 = (1+2+\cdots+n)^2\]

Base case: \begin{eqnarray*}
1^3 & = & (1)^2 \\
1 & = & 1
\end{eqnarray*}

Assume: $n=k$
\[1^3 + 2^3 + \cdots + k^3 = (1+2+\cdots+k)^2\]
Prove: $n=k+1$
\begin{eqnarray*}
1^3 + 2^3 + \cdots + k^3 + (k+1)^3 & = & [1+2+\cdots+k+(k+1)]^2 \\
(1+2+\cdots+k)^2 + (k+1)^3 & = &
	\left[\frac{k(k+1)}{2}+(k+1)\right]^2 \\
\left[\frac{k(k+1)}{2}\right]^2 + (k+1)^3 & = &
	\left[\frac{(k+1)(k+2)}{2}\right]^2 \\
(k+1)^2\left[\frac{k^2}{4}+(k+1)\right] & = &
	(k+1)^2\left(\frac{k+2}{2}\right)^2 \\
(k+1)^2\left(\frac{k^2+4k+4}{4}\right) & = &
	(k+1)^2\left(\frac{k^2+4k+4}{4}\right)
\end{eqnarray*}

\newpage
\problem{2}{Graphs}
\part{a}{Counting}
In a graph with $|E|$ edges, each edge meets two vertices, so
\[2|E| = \sum_{v\in V}\delta(v)\]

\part{b}{Pigeonhole Principle}
For both cases, assume $v$ = number of vertices.

{\bf Case 1:} If there exists a vertex with degree $v-1$, then that
vertex has an edge connecting to each other vertex in the graph.
Therefore, no vertex can have degree zero.  Pigeonhole the vertices
according to their degrees.  There are $v$ vertices, and each has
degree $1 \leq \delta \leq v-1$.  Since there are more vertices than
possible degrees, there must be at least two vertices with the same
degree.

{\bf Case 2:} If there does not exist a vertex with degree $v-1$, then
pigeonhole the the vertices according to their degrees.  There are $v$
vertices, and each has degree $0 \leq \delta \leq v-2$.  Again, since
there are more vertices than possible degrees, there must be at least
two vertices with the same degree.

\newpage
\problem{3}{Regular Expressions}
\begin{itemize}
\item[(a)] (0,1)\{(0,1)(0,1)\}*
\item[(b)] (0,1)*(1(00)*)
\item[(c)] 1*0*
\end{itemize}

\newpage
\problem{4}{Constructing DFA's}
\epsfile{ps1.ps}

\newpage
\problem{5}{Relations}
\part{a}{}
Prove: $R+$ is transitive

According to rule (ii) for constructing $R+$, if (a,b) and (b,c) are
in $R+$, then (a,c) must be.  Therefore, $R+$ is transitive.

\part{b}{}
Prove: $R+$ is the smallest transitive relation containing $R$.

Proof by contradiction.

Assume there exists a transitive $Q$ which is a proper subset of $R+$,
and also contains $R$.  Since $Q$ is a proper subset, there must be an
element (a,b) which is in $R+$, but not in $Q$.  This element is also
not in $R$.  Now, since (a,b) was not in $R$, it must have been in one
of the $R_i, i\geq 2$.  In order to be in $R_i$, (a,c) and (c,b) (for
some c) must have been in $R_{i-1}$.  Now, there are two cases to
consider.  In the first case, (a,c) and (c,b) are in $Q$, and this
leads to a contradiction, since (a,b) is not in $Q$, and we assumed
$Q$ was transitive.  In the second case, one of (a,c) or (c,b) is not
in $Q$, so (a,b) is not necessary.  However, the missing pair is the
transitive relation for some two pairs in $R_{i-2}$.  Now, either case
one applies, and we have a contradiction, or case two applies.  We can
continue this process until we reach a contradiction in the first
case, or until $i=1$ which leads to a contradiction, since we know
that $R \subset Q$.

\end{document}
