\documentstyle[11pt]{article}
% frob with the margins
\addtolength{\topmargin}{-1in}
\addtolength{\footskip}{-1in}
\addtolength{\textheight}{2in}
\addtolength{\oddsidemargin}{-.5in}
\addtolength{\evensidemargin}{-.5in}
\addtolength{\textwidth}{1in}
% no page numbers
\pagestyle{empty}
% counter for page numbers
\newcounter{pg}
\setcounter{pg}{2}

% DEFINE THE PROBLEM SET NUMBER
\def\psnum{1}

% DEFINE THE DUE DATE
\def\due{February 15, 1991}

% title command
\newcommand{\mytitle}{{\large\noindent 6.045/18.400 Automata,
Computability, and Complexity \hfill{} Juliet Bourne \\
Problem Set \psnum \hfill{} \due \\}
\vspace{-.6in}
\begin{center} \rule{6in}{.25mm} \end{center}}
% newpage setup command 
\newcommand{\mypage}[1]{\newpage{\large\noindent 6.045/18.400 Automata,
Computability, and Complexity \hfill{} Juliet Bourne \\
Problem Set \psnum \hfill{} \due \\}
\vspace{-.6in}
\begin{center} \rule{6in}{.25mm} \end{center}}
%\newcommand{\mynewpage}{\newpage\noindent
%{\large 6.045/18.400 \hfill{} Juliet Bourne \\
%Problem Set \psnum \hfill{} {\bf Page \thepg} \\}
%\vspace{-.6in}
%\begin{center}
%\rule{6in}{.25mm}
%\end{center}
%\addtocounter{pg}{1}}
% problem command
\newcommand{\prob}[1]{\noindent{\fbox{\large\bf Problem #1}}\vspace{.25in}}
% subproblem command
\newcommand{\subprob}[1]{\vspace{.15in} \noindent{\large\bf #1.}}
% equations commands
\newcommand{\beq}{\vspace*{-.3in}\begin{eqnarray*}}
\newcommand{\eeq}{\end{eqnarray*}}

\begin{document}

\mytitle

\prob{1: Induction}

\noindent Prove that for all positive integers n, 

\beq
1^3 + 2^3 + ... + n^3 & = & (1 + 2 + ... + n)^2
\eeq

\noindent Base step: $n = 1 \,\,\,\, 1^3 = 1^2$

\noindent Induction step: Assume it is true for $n$. Show that it is true
for $n + 1$.

\beq
1^3 + 2^3 + ... + n^3 (n + 1)^3 & = & (1 + 2 + ... + n + (n + 1))^2 \\
(1 + 2 + ... + n)^2 + (n + 1)^3 & = & (1 + 2 + ... + n + (n + 1))^2 \\
(n + 1)^3 & = & (1 + 2 + ... + n + (n + 1))^2 - \\ 
& &  (1 + 2 + ... + n)^2 \\
(1 + 2 + ... + n)^2 & = & (1 + 2 + ... + n) + 2(1 + 2 + ... + n) + \\
& & ... + n(1 + 2 + ... + n) \\
(1 + 2 + ... + n + (n + 1))^2 & = & (1 + 2 + ... + n + (n + 1)) + \\
& & ... + (n + 1)(1 + 2 + ... + n + (n + 1)) \\
(1 + 2 + .. + n + (n + 1))^2 - (1 + 2 + ... + n)^2 & = & (n + 1) + 2(n +
1) + ... + n(n + 1) + \\ 
& & (n + 1)(1 + 2 + ... + n + (n + 1)) \\
(n + 1)^3 & = & (n + 1)(1 + 2 + ... + n + \\ 
& & (1 + 2 + ... + n + (n + 1))) \\
(n + 1)^2 & = & 2(1 + 2 + ... + n) + (n + 1)
\eeq

\noindent Now use induction to prove this last relation. Prove that for
all positive integers m, 

\beq
m^2 & = & 2(1 + 2 + ... + (m -1)) + m
\eeq

\noindent Base step: $m = 1 \,\,\,\, 1^2 = 2(0) + 1 \,\, 1 = 1$

\noindent Induction step: Assume it is true for $m$. Show that it is true
for $m + 1$.

\beq
(m + 1)^2 & = & 2(1 + 2 + ... + (m + 1 - 1)) + m + 1 \\
m^2 + 2m + 1 & = & 2(1 + 2 + ... + (m - 1)) + 2m + m + 1 \\
2m + 1 & = & 2m + 1 
\eeq

\noindent Thus, $m^2 = 2(1 + 2 + ... + (m - 1)) + m$. So, this proves
the previous induction step showing that

\beq
1^3 + 2^3 + ... + n^3 + (n + 1)^3 & = & (1 + 2 + ... + n + (n + 1))^2 
\eeq

\noindent which proves that for all n, 

\beq
1^3 + 2^3 + ... + n^3 & = & (1 + 2 + ... + n)^2 
\eeq

\mypage

\prob{2 (a): Graphs, Counting}

\noindent Prove that for any graph, sum of the degree of the vertices is
twice the number of edges:

\beq
2 \ast |E| = \sum_{v \in V} \delta (v)
\eeq

\noindent where $|E|$, the cardinality of $E$, represents the
number of edges in the set $E$.

\vspace{.15in}
\noindent There are two vertices in each edge. $\delta (v)$ of a vertex
is the number of edges it is in. When computing the sum of the degree of
all of the vertices, twice the number of edges is computed since each
edge will be added twice since there are two vertices in every edge. 

\vspace{.15in}
\noindent Base step: for a graph with one vertex, there is 0 edges and
the vertex has degree 0. Therefore, $2 \ast 0 = 0$.

\vspace{.15in}
\noindent Induction step (for vertices): Assume that it is true for $k$
vertices. Show that it is true for $k + 1$. Since the number of edges
doesn't change, the new vertex doesn't have an edge, and therefore its
degree is zero:

\beq
\sum_{v \in V_k} \delta (v) + \delta (v_{k + 1}) & = & 2 |E| \\
2 |E| + 0 & = & 2 |E|
\eeq

\noindent Induction step (for edges): Assume that it is true for $m$
edges, i.e. $|E| = m$. Show that it is true for $|E| = m + 1$ edges.
Adding an edge causes two vertices in the graph to increase their
degrees each by 1:

\beq
\sum_{v \in V} \delta (v) & = & 2(m + 1) \\
\sum_{v \in V} \delta (v) & = & 2|E| + 2 \\
\sum_{v \in V} \delta (v) - 2 & = & 2|E| \\
\eeq

\noindent Induction step (for edges and vertices): Assume that it is
true for $k$ vertices and $m$ edges. Show that it is true for $k + 1$
vertices and $|E| = m + 1$. When both a node and a vertex are added to a
graph, two vertices have their degrees increased each by 1 (to take into
account the added edge) and the new vertex will have degree zero:

\beq
\sum_{v \in V_k} \delta (v) + \delta (v_{k + 1}) & = & 2 (m + 1) \\ 
\sum_{v \in V_k} \delta (v) + 0 & = & 2|E| + 2 \\
\sum_{v \in V_k} \delta (v) - 2 & = & 2|E| 
\eeq 

\mypage

\prob{2 (b): Graphs, Pigeonhole Principle}

\noindent Prove that any graph which has more than one vertex, has two
vertices with the same degree.

\vspace{.15in}
If there are $m$ vertices, $|V| = m$, then the possible degrees of the
vertices are $D=\{0,1,...,m-1\}$ since a vertex can create an edge
with any other vertex but itself.

If there is a vertex with degree $m - 1$, then every other vertex must
have at least one edge. So, $m - 1$ and 0 cannot both be in $D$. Thus
$\delta (v)$ maps a set ($|V|$) of size $m$ to a set ($|D|$) of size $m
- 1$ or less. The pigeonhole principle says that if $|V| > |D|$, then at
least one degree must be shared by at least two vertices.

\mypage

\prob{3: Regular Expressions}

Show that each of the following subsets of $\{0,1\}^*$ is regular by
providing for each a regular expression.

\subprob{a} The set of all strings of odd length.

$((0,1)^2)^*) (0,1)$

\subprob{b} The set of all string that have at least one 1, and end with
an even number of zeroes.

$(0,1)^*1(0,1)^*(00)^*$

\subprob{C} The set of all strings in which no zero is followed by a 1.

$1^*0^*$

\mypage

\prob{4: Constructing DFAs}

\subprob{a}

\vspace*{1.5in}

\subprob{b}

\vspace*{1.5in}

\subprob{c}

\mypage

\prob{5: Relations}

\subprob{a} Prove that $R^+$ is transitive.

Recall: (ii) If $(a,b)$ and $(b,c)$ are in $R_{i - 1}$, then $(a,c)$ is
in $R_i$. Also, $R^+ = \cup_{i} R_i$.

Thus:

\beq
R_{i-1}, \,\,\,\, R_i &\subset & R^+ \\
(a,b),(b,c) \in R_{i-1} &\Rightarrow & (a,b),(b,c) \in R^+ \\
(a,c) \in R_i & \Rightarrow & (a,c) \in R^+ \\
\eeq

Therefore, $R^+$ meets the constraints for being transitive.

\subprob{b} Prove that $R^+$ is the smallest transitive containing $R$;
that is any proper subset of $R^+$ is not transitive.

Remove a relation $R_k$ from $R^+$ to form a smaller subset $Q$. $Q$
will not be transitive, since $R_{k+1}$ depends on $R_k$.

Alternatively, prove by contradiction. Assume there is a smaller
transitive relation $Q$ containing $R$.

\beq
(i,j) \in R^+ - Q \\
R \subset R^+ - Q \\
(i,j) \in R
\eeq

Therefore, there is no proper subset of $R^+$ that is transitive.

\end{document}
