\documentstyle[12pt,amssymb]{article}
\input{/a/class/6.042/spring95/macros-course}

\addtolength{\topmargin}{-.2in}
\setlength{\textheight}{9in}

% \setcounter{page}{0}
\begin{document}
\qsol{1}{March 21, 1995}

\begin{problems}
\problem

Discover and prove a formula for $ \left( \begin{array}{cc}
					1 & 1\\
					0 & 1
				\end{array} \right) ^n$.


Conjecture: $\left( \begin{array}{cc}
					1 & 1\\
					0 & 1
				   \end{array} \right) ^n = \left(\begin{array}{cc}
                    1 & n\\
                    0 & 1
                   \end{array} \right) $.

\begin{proof}
By induction on $n$.
\begin{description}
\item[Base Case:]\ That the conjecture is true for $n = 1$ is obvious.
\item[Inductive Step:] Assume that the conjecture is true for $n = k,
  k \geq 1$, i.e. assume that
\[
\left( \begin{array}{cc}
1 & 1\\
0 & 1
\end{array} \right)^k = \left( \begin{array}{cc}
1 & k\\
0 & 1
\end{array} \right)
\]
Now:

\begin{eqnarray*}
\left( \begin{array}{cc} 1 & 1\\ 0 & 1 \end{array} \right)^{k+1} & = & 
\left( \begin{array}{cc} 1 & k\\ 0 & 1 \end{array} \right) * 
\left( \begin{array}{cc} 1 & 1 \\ 0 & 1 \end{array}
\right) \\
 & = & \left( \begin{array}{cc} 1 & k+1\\0 & 1 \end{array} \right)
\end{eqnarray*}
And this implies that the conjecture is true for $n = k+1$.  Thus, by
induction, the conjecture is true for all $n \geq 1$.
\end{description}
\end{proof}

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

\problem  

Prove that the following two sequences are equal:

\begin{eqnarray*}
u_0 & = & 2 \\
u_{n+1} & = & u_n^2-u_n+1
\end{eqnarray*} 

\begin{eqnarray*}
v_0 & = & 2 \\
v_{n+1} & = & 1+v_0v_1\cdots v_n
\end{eqnarray*} 

\begin{proof}
By strong induction on $n$.
\begin{description}

\item[Base cases:]\ When $n = 0, u_n = v_n,$ by definition. When $n =
  1$ then we have $u_n = v_n = 3$.

\item[Inductive Step:]\ Assume that the sequences agree up
to the $k$th member, i.e. assume that $u_n = v_n, \forall n, 0 \leq n \leq k$ where $k \geq 1$. Now:

\begin{eqnarray*}
u_{k+1} & = & u_k^2 - u_k + 1 \\
& = & v_k^2 - v_k + 1  \mbox{\ \ \ (by the inductive hypothesis)} \\
& = & v_k(v_k - 1) + 1 \\
& = & v_k(v_0 \ldots v_{k-1}) + 1 \mbox{\ \ \ (by the defininition for
$v_k$ and the fact that $k \geq 1$)} \\
& = & v_0 \ldots v_k + 1  \\
& = & v_{k+1} 
\end{eqnarray*}


This implies that the sequences agree up to the $k+1$st element.
Thus, by induction, $u_n = v_n, \forall n \geq 0$, i.e.  the sequences
are equal.

(Note that when we used the formula for $v$ we assumed that $k$ is at
least $1$.  In other words $k+1$ is at least $2$.  So we can't use
this step to go from $n = 0$ to $n = 1$.  That's why we had to show
that $u_1 = v_1$ as a base case.  In fact unless $u_0 = v_0 = 0$ or
$u_0 = v_0 = 2$ the sequences aren't the same)

\end{description}
\end{proof}

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

\problem 

For a function $f:A\mapsto B$ and a subset $C\subseteq A$, define
$f(C)=\{b\mid f(a)=b\hbox{  for some }a\in C\}$. Prove that if $f$ is 
a 1-1(an injection), then $f(C\cap D)=f(C)\cap f(D)$ for 
every $C,D\subseteq A$.

\begin{proof}
To prove this theorem we need to show the following two containments:
\begin{enumerate}
\item $f(C \cap D) \subseteq f(C) \cap f(D)$.  This is true for all
functions not just injections.  Let $y \in f(C \cap D)$.  We know there must
exist $x \in C \cap D$ such that $f(x) = y$.  Since $x \in C \cap D$, $x$ is
an element of $C$ and also an element of $D$.  Thus $y \in f(C)$ and $y \in
f(D)$ which implies that $y \in f(C) \cap f(D)$.
\item $f(C) \cap f(D) \subseteq f(C \cap D)$.  To prove this we need $f$ to
be 1-1.  Let $y \in f(C) \cap f(D)$.  We know there exist $x \in C$ and $z
\in D$ such that $f(x) = f(z) = y$.  But since $f$ is 1-1, $x = z$ and so $x
\in C \cap D$.  Thus $y \in f(C \cap D)$.
\end{enumerate}

\end{proof}

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

\problem
 
Define the poset $(\{1,2,3,4,5\}^2,\prec)$ where $(a,b)\prec(c,d)$ 
iff $a\le c$ and $b\le d$.
\bparts
\ppart
Give an antichain which is as long as possible.


The antichain is $\{(5,1),(4,2),(3,3),(2,4),(1,5)\}$.

\ppart
Prove that the above antichain is the largest.

\begin{proof}
  The proof is by contradiction. Say we had a larger antichain.
  Consider the first component of all of the elements of this
  antichain.  They are all integers from $1$ to $5$.  If we had more
  than $5$ elements in the antichain, there must be two elements with
  the same first component (pigeonhole principle).  But then these
  elements are comparable violating the fact we have an antichain.
  Contradiction. Hence we could not have had an antichain with more
  than $5$ elements.

  (An alternate proof would be to show that the poset has a chain
  cover with no more than $5$ elements. Then Dilworth's theorem would
  guarantee us that the largest antichain has at most $5$ elements
  too.)
\end{proof}

\eparts

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

\problem  

The {\em complement} of an undirected graph $G=(V,E)$ is the graph 
$G^c=(V,E^c)$. 
That is, $G^c$ contains exactly those edges that are not in $G$. 
Prove that if $G$ is not connected then $G^c$ is.
\begin{proof}
  Suppose $G=(V,E)$ is not connected.  Then $G$ can be divided into
  nonempty disjoint connected components $G_1, G_2, \ldots G_k$ (where
  $k>1$).  Consider any two vertices $a, b$ in $V$.  Let's show that they
  are connected by a path in $G^c$.
\begin{description}

\item[Case 1]  \ $a$ and $b$ are in different connected components of
$G$.  Then there is no edge in $E$ connecting $a$ and $b$.  Thus $E^c$
contains an edge connecting $a$ and $b$.

\item[Case 2]  \ $a$ and $b$ are in the same connected component of
$G$.  Let $c$ be a vertex in a different connected component.  By case
1, $a$ and $c$ are connected, as are $b$ and $c$.  Thus $a$ and $b$ are
connected through $c$.

\end{description}
Thus $G^c$ contains a path from $a$ to $b$, for any pair of vertices
$a, b$ in $V$.  Thus $G^c$ is connected.

\end{proof}

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

\problem

Give an explicit bijection between $\reals$ and $(0,\infty)$, where 
 $(0,\infty)$ is the set $\{ x \in \reals \mid x > 0 \} $. 

 Here is a function that produces a bijective map.  $f(x) = e^x$.  It
 is 1-1 since $x < y$ implies that $e^x < e^y$.  It's onto since for
 any $z > 0$, $e^{\ln z} = z$.

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


\end{problems}

\end{document}


