        \problemdata       % Takes 5 *mandatory* arguments
        {sqrt2-ind}             % latex-friendly label for the prob.
        {induction}  % The topic(s) of the problem content.
        {}               % Source (if known)
        {F01 PS2-5} % Usage (list ones you are aware of).
        {}        % Last revision info (author, date).

\begin{problem}
Reformulate the proof from Problem Set 1, problem 7(a) as a proof
by induction.

\solution{
\begin{proof}
We want to show that
\[
\forall q\in\naturals^+\, \forall p\in\naturals\; \sqrt{2}\neq p/q.
\]
We can rewrite this as 
\[
\forall q\in\naturals^+\, \forall p\in\naturals\; q\sqrt{2}\neq p.
\]
In words: ``no matter what positive integer, $q$, you may pick,
multiplying $\sqrt{2}$ by $q$ does not result in a natural number.''  We
prove this by strong induction.

\textbf{Base case:} For $q=1$, our job is easy: $q\sqrt{2}=\sqrt{2} =
1.414\dots$ is not an integer.

\textbf{Induction step:} Fix any positive integer, $q$, and suppose that
$k\sqrt{2}$ is not a natural number, for all $k\leq q$.  We must show that
$(q+1)\sqrt{2}$ is not a natural number, either.  So assume to the
contrary that that $(q+1)\sqrt{2}$ \emph{is} a natural number.

Consider the number $m \eqdef (q+1)\sqrt{2}-(q+1)$. 

Now $m$ is a positive integer, because both $(q+1)\sqrt{2}$ and $(q+1)$
are natural numbers, and the first is strictly greater than the second
because $\sqrt{2}>1$.

Moreover, $m = (q+1)(\sqrt{2}-1) = (q+1) \cdot 0.414\dots < q+1$, and
since $m$ is an integer, we conclude that $m \le q$.

Finally,
\[
m\sqrt{2} = 
( (q+1)\sqrt{2} - (q+1) )\sqrt{2} =
2(q+1) - (q+1)\sqrt{2}
\]
is a positive integer, because both $2(q+1)$ and, by assumption
$(q+1), \sqrt{2}$ are natural numbers, and the first is strictly
greater than the second because $2 > 1.414\dots =\sqrt{2}$. 

To summarize, $m \in \nats$ and $0< m \le q$, and $m\sqrt{2}$ is a natural
number, contradicating our strong induction hypothesis.  So, we must infer
that our assumption is wrong.  That is, we infer $(q+1)\sqrt{2}$ is not a
natural number, which concludes the inductive step.
\end{proof}
}


\end{problem}