\documentclass[12pt]{article}
\usepackage{fullpage}
\usepackage{times}
\usepackage{amsmath,amsfonts,amssymb}

\newtheorem{theorem}{Claim}
\newcommand{\prf}{{\sl Proof}: }
\newcommand{\qed}{$\Box$}

\begin{document}

\par\noindent{\bf CS81 HW\#1 Spring 2012}
\par\noindent{\em Out: 01/18/2012. Due: 01/25/2012 (before class)} \\

\par\noindent
Determine for each claim below if there is a mistake in the proof; if so, point it out explicitly.
In the case where the claim itself is correct but the proof is wrong (incorrect or incomplete), 
provide a correct proof.

\begin{theorem}
Every student taking CS81 will receive the same grade.
\end{theorem}
\prf
We prove this by induction on the number $N$ of students taking CS81.

The base case is $N=1$ which is trivially true.
Assume that the claim holds for $N=k$, where $k \ge 1$. 
Consider the case where $N=k+1$. All but the $(k+1)$-th student receive the same grade
by the inductive hypothesis. Similarly, all but the first student receive the same grade.
Thus, all $k+1$ students receive the same grade. So, the claim for $k+1$ holds.

This shows that all students taking CS81 receive the same grade.
\qed

\begin{theorem}
Two equals three.
\end{theorem}
\prf
Consider the identity $2 = \frac{6}{5-2}$. 
By recursively applying the identity to $2$ on the right-hand side, we obtain
\begin{equation} \label{eqn:two}
	2 = \frac{6}{5-\frac{6}{5-\frac{6}{5-\ldots}}}.
\end{equation}
By the same token, consider the identity $3 = \frac{6}{5-3}$. 
By recursively applying the identity to $3$ on the right-hand side, we obtain
\begin{equation} \label{eqn:three}
	3 = \frac{6}{5-\frac{6}{5-\frac{6}{5-\ldots}}}.
\end{equation}
Since the right-hand sides of (\ref{eqn:two}) and (\ref{eqn:three}) are equal, 
this proves that $2$ equals $3$.
\qed


\begin{theorem}
$\sqrt{3}$ is irrational.
\end{theorem}
\prf
Suppose that $\sqrt{3}$ is rational, that is, $\sqrt{3} = a/b$, for two integers $a$ and $b$.
Thus, $a^{2} = 3b^{2}$. By arguments similar to the proof that $\sqrt{2}$ is irrational, we
arrive at a contradiction. This shows that $\sqrt{3}$ is irrational.
\qed


\begin{theorem}
Any tree with at least two vertices has a vertex of degree one.
Recall that a tree is a connected graph with no cycles. 
\end{theorem}
\prf
By induction on the number of vertices $N$ of the tree. 

The base case for $N=2$ vertices is obvious.
Suppose the claim holds for any tree with $N=k$ vertices, where $k \ge 2$.
Let $T$ be a tree with $N=k+1$ vertices. Pick a collection of $k$ vertices from $T$.
By the inductive hypothesis, this collection contains a vertex of degree one.
This proves the claim.
\qed

\end{document}

