\examonly{\newpage}

\problem {\bf [15 pts]\ } Use induction to prove that the following
equation holds for all $n \in \mathbb{N}$.

\beqn
\frac{1 \cdot 3 \cdot 5 \cdots (2n-1)}{2 \cdot 4 \cdot 6 \cdots (2n)}
	& \geq &	\frac{1}{2n}
\eeqn

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

\examonly{\newpage}

\problem {\bf [15 pts]\ } Let $S_n$ be the set $\{1, 2, 3, \ldots,
n\}$.  Use induction to prove that the following equation holds for
all $n \in \mathbb{N}$.

\beqn
\sum_{A \subseteq S_n, A \neq \emptyset} \left(\prod_{a \in A} a
\right)^{-1} & = & n
\eeqn

\noindent In the summation, $A$ ranges over all nonempty subsets of
$S_n$.  For example, for $n = 3$, we have:

\beqn
\frac{1}{1} + \frac{1}{2} + \frac{1}{3} +
\frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \frac{1}{1 \cdot 3} +
\frac{1}{1 \cdot 2 \cdot 3} & = & 3
\eeqn

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

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

\examonly{\newpage}

\problem {\bf [15 pts]\ } Underline the first false statement in the
proof and explain the error in the space below.  In this problem, the
term {\em graph} refers to undirected graphs with no self-loops.
Recall that a {\em Hamiltonian cycle} in a graph is a path that begins
at one vertex, visits every other vertex, and returns to the original
vertex, without ever crossing an edge more than once.

\begin{theorem}
For every graph with at least $n \geq 3$ vertices, if every vertex has
degree at least $(n + 1) / 2$, then the graph contains a Hamiltonian
cycle.
\end{theorem}

\begin{proof}
The proof is by induction on $n$, the number of vertices in the graph.
Let $P(n)$ be the proposition that for every graph with $n$ vertices,
if every vertiex has degree at least $(n + 1) / 2$, then the graph
contains a Hamiltonian cycle.

First, we prove that $P(3)$ is true.  In this case, there is a single
graph meeting the conditions, and it clearly has a Hamiltonian cycle:

\bigskip
\centerline{\resizebox{!}{0.5in}{\includegraphics{quiz2-tri.eps}}}
\bigskip

Next, we must show that for all $n \geq 3$, $P(n)$ implies $P(n+1)$.
Assume $P(n)$ is true and consider an undirected graph $G$ with $n+1$
vertices.  Remove one vertex $u \in V$ and all incident edges to form
a graph $G'$ with $n$ vertices.  By the induction hypothesis, $P(n)$,
this graph has a Hamiltonian cycle $C$ on $n$ vertices.  The same
cycle $C$ must exist in $V$; all that remains is to fit in the
remaining vertex $u$.  Since $u$ has degree at least $(n + 1) / 2$,
the Pigeonhole Principle implies that $u$ must be adjacent to some two
consecutive vertices $v_1$ and $v_2$ in the cycle $C$.  Thus, we can
enlarge the cycle $C$ to form a Hamiltonian cycle in $G$ by removing
the edge $(v_1, v_2)$ and adding the edges $(v_1, u)$ and $(u, v_2)$.

This completes the induction and the claim is proved.
\end{proof}