\documentstyle[12pt,twoside]{article}
\input{macros-course}

%	\addtolength{\topmargin}{-.35in}
%	\setlength{\textheight}{9in}

\begin{document}

\pset{4}{March 2, 1995}{In recitation, March 10}

\bigskip


\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

Discover and proof a formula for $\big(\begin{array}{cc}
					1 & 1\\
					0 & 1
\end{array}\big)^n$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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*} 

Explain what goes wrong (if anything) if we set $u_0=v_o=1$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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 $f$ is 1-1 iff
$f(C\cap D)=f(C)\cap f(D)$ for every $C,D\subseteq A$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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 a chain which is as long as possible.
\ppart
Give an antichain which is as long as possible.
\ppart
Prove that the above antichain is the largest.
\eparts
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem
Give an explicit bijection between $[0,\infty)$ and $N\times[0,\infty)$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem
Let $G_1=(V,E_1)$ and $G_2=(V,E_2)$ be two trees on the same set of vertices.
Define the graph $G=(V,E)$ where $E=E_1\cup E_2$.
\bparts
\ppart
Prove that $G$ is 4-colorable.
\ppart
200zGive an example to show that the result cannot be improved. That is, show
that there are 2 trees whose union is not 3-colorable.
\eparts
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem
The {\em complement} of a graph $G=(V,E)$ is the graph $G^c=(V,E^c)$. That is,
$G^c$ contains exactly those edges which are not in $G$. Prove that if $G$ is
not connected then $G^c$ is.
\end{problems}

\end{document}
