%sample.tex
\documentclass[12pt]{article}
\usepackage{homework}
\sethwtitle{HW1 - Math 220 - Fall 2009}%
\sethwauthor{Mark Goadrich}%
\makehwheader%

\begin{document}
\setlength{\parskip}{10pt plus 1pt minus 1pt}

\makehwtitle%

\section{Subset Proof}

\subsection{Use induction on the size of $S$ to show that if $S$ is a 
finite set, then $|2^{S}| = 2^{|S|}$}

We will prove this by induction, with a base case and an induction step.

{\bf Base Case}: $S = \emptyset$.

Proof: When $S$ is the empty set, we know $|S| = 0$. Therefore, 
$2^S = \{\emptyset\}$, and we have proven:

\begin{equation}
|2^{S}| = 1 = 2^{|S|}
\end{equation}

{\bf Induction Step}: Assume $|2^{S}| = 2^{|S|}$ where $|S| = n$.  
Prove that $|2^{S \cup \{a\}}| = 2^{|S \cup \{a\}|}$ where $a \notin S$.

Proof: When we add a new element $a$ to a set $S$, the powerset will be equal 
to $2^{S}$ plus the sets created by adding $a$ as an element to each member 
of $2^{S}$.  This will give us twice as many subsets.  Therefore

\begin{align}
|2^{S \cup \{a\}}| &= 2 \cdot 2^{S} \\
 &= 2^{|S| + 1} \\
 &= 2^{|S \cup \{a\}|}
\end{align}

\end{document}
%end of sample.tex
