\documentclass[11pt,twoside]{article}
\usepackage{latex-macros/course}% !! use the macros 
\usepackage{textcomp} % to get \textcent

%\backwardscompatibility        % !! use for backwards compatibility
%\showsolutions                 % !! use to force solutions & skip query
%\hidesolutions                 % !! use to force no solutions & skip query
\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}

\begin{document} 
\inclassproblems{2F}            % !! start the paper


%STRONG INDUCTION, new

\begin{problem}
What amounts of postage can be made from 6\textcent\ stamps and 10\textcent\
stamps?  Prove it.

\solution{6\textcent, 10\textcent, 12\textcent, and every even number of
cents $\geq 16$\textcent.  Proof sketch: Cases $n= 16, 18, 20$\textcent\
explicitly.  Then for even $n \geq 22$, assemble $n-6$\textcent\ by strong
induction hypothesis and add 6\textcent\ stamp.  Can't get odd postage
because 6 and 10 both even; other cases <16 by exhaustion.}
\end{problem}

%STRONG INDUCTION, F01 ps2

\begin{problem}
Pinpoint, and illustrate with a counterexample, \emph{exactly}
where the following proofs go awry.

\begin{problemparts}
\problempart Claim 1: $\forall x \in \reals\, \forall n\in \naturals\ x^n=1$.

\begin{falseproof}
Proof by strong induction on $n$:

\textbf{Base case} $n= 0$: $x^n = x^0=1$ by definition of ``zeroth power'' of a
real number.

\textbf{Induction step}: By hypothesis, $x^k=1$ for all $k\leq n$.  We
must show that $x^{n+1}=1$.  By the strong inductive hypothesis, with
$k=n$ and $k=1,$ we have $x^n=1$ and $x^1=1$.  So,
\[
x^{n+1}=x^nx^1 = 1\times 1=1.
\]
\end{falseproof}

\solution{The proof of the induction step is not correct when $n=0$.  In
this case, $k=1$ so it is not true that $k \leq n$, and we cannot assume
by strong induction that $x^1 = 1$, which of course it is not when $x\neq
1$.}

\problempart An integer, $m$, \emph{divides} an integer, $n$, in symbols, $m
\divides n$, iff there is an integer $k$ such that $km=n$.

Claim 2: For any positive integers $p, n, x_1, x_2,\ldots, x_n$, if
$p \divides x_1x_2\dots x_n$, then $p \divides x_i$ for some $1\leq i\leq n$.

\begin{falseproof}
Proof by strong induction on $n$.

\textbf{Base case} $n= 1$: When $n=1$, we have $p\divides x_1$, therefore
we can let $i=1$ and conclude $p\divides x_i$.

\textbf{Induction step}: Now assuming the claim holds for all $k\leq n$, we must
prove it for $n+1$.

So suppose $p\divides x_1x_2\ldots x_{n+1}$.  Let $y_n = x_n x_{n+1}$, so
$x_1x_2\ldots x_{n+1} = x_1x_2\ldots x_{n-1}y_n$.  Since the righthand
side of this equality is a product of $n$ terms, we have by induction that
$p$ divides one of them.  If $p\divides x_i$ for some $i < n$, then we have the
desired $i$.  Otherwise $p\divides y_n$.  But since $y_n$ is a product of the two
terms $x_n, x_{n+1}$, we have by strong induction that $p$ divides one of
them.  So in this case $p \divides  x_i$ for $i = n$ or $i = n+1$.
\end{falseproof}

\solution{The statement ``we have by strong induction that $p$ divides
one of them'' is the place where the proof breaks down: it appeals to
strong induction to justify applying the induction hypothesis for $2=k\leq
n$.  But the base case was $n=1$, so we can't assume $2 \leq n$.  Note
that the reasoning above is fine for every $n\geq 2$, so the whole proof
would be fine if we had an argument to prove the claim for $n+1=2$.  But
of course we can't prove it for $n+1=2$ because it isn't true: let $p=6,
x_1 =2, x_2 =3$.  Even though the reasoning is fine for every $n\geq 2$,
the fact that it failed for $n=1$ let us deduce a completely false
result.}
\end{problemparts}
\end{problem}

%%Example from Spring99, tutorial 2, Least Number Principle

\begin{problem}

Here's a different proof that the square root of 2 is irrational, this one
based on the Least Number Principle.

\begin{proof}
The proof is by contradiction.

Assume that the square root of 2 is rational.  Then $\sqrt{2}$ is equal to
$m / n$ for some positive integers $m$ and $n$.  So $n$ has the property
that
\begin{equation}\label{ns2}
n \text{ and } n\sqrt{2} \text{ are positive integers}.
\end{equation}
Now by the Least Number Principle, there must be a \emph{smallest}
positive integer, $n$, satisfying~(\ref{ns2}).  For this $n$, let $n_0
\eqdef n (\sqrt{2} - 1)$.  But then $n_0$ is smaller than $n$, and $n_0$
and $n_0\sqrt{2}$ are positive integers, a contradiction.
\end{proof}

\begin{problemparts}

\problempart Are you convinced by this proof?  Briefly explain.

In particular, why is $n_0$ an integer?

\solution{Because it equals $n\sqrt{2} - n$
and $n$ and  $n\sqrt{2}$ are integers by hypothesis.}

Why is $n_0$ positive?

\solution{Because $(\sqrt{2} -1) \approx 0.414\dots$ is positive.}

Why is $n_0$ smaller than $n$?

\solution{Because $(\sqrt{2}-1) < 0.415 < 1$.}

Why is $n_0\sqrt{2}$ a positive integer?

\solution{It's an integer because $n_0\sqrt{2} = (n\sqrt{2} - n)\sqrt{2}
= 2n - n\sqrt{2}$, which is again an integer because both terms are
integers.  It's positive because $2n - n\sqrt{2} = (2 - \sqrt{2})n > 0.58
n > 0$.}

\end{problemparts}

We can generalize this proof to prove that $\sqrt{k}$ is irrational for
integers $k$ other than 2.  Simply revise the next to last sentence to
read, ``\dots and let $n_0 \eqdef (\sqrt{k} - \floor{\sqrt{k}})$''.  (For
any real number, $r$, the expression $\floor{r}$ denotes $r$ rounded
\emph{down} to the nearest integer.)

\begin{problemparts}
\problempart Are you convinced by this argument?  Explain.

\solution{You shouldn't be convinced because the conclusion is wrong,
For example, $\sqrt{k}$ is certainly rational if $k=4$.

The proof works for $\sqrt{k}$ as long as $k$ is not a perfect square.
But if $k$ is a perfect square, then the proof breaks down in the next to
last sentence: the number $n_0 (\sqrt{k} - \lfloor \sqrt{k} \rfloor)$ is
not positive in this case, but zero.}
\end{problemparts}

\end{problem}


%from Spring99 tutorial -- cute puzzle on simple induction, maybe skip.

\begin{problem} I recently went to a party with my Significant Other.  There
were at total of $12$ couples at the party.  A lot of handshaking
happened, but of course no one shook hands with more than 22 people,
because no one shook hands with their Significant Other or with
themselves.  At the end, it turned out that no two other people shook
hands with the same number of people.  How many people did I shake hands
with?  Prove it.

\solution{I shake 11 hands.

To see why, we will prove the general result for a set of $n$ couples:
\begin{theorem}\label{shake}
Suppose at a party for exactly $n$ couples, no two other people besides me
shook hands with the same number of people.  Then I must have shaken hands
with $n-1$ people.
\end{theorem}

\begin{proof}
By induction on $n$.  The induction hypothesis, $P(n)$, is
Theorem~\ref{shake}.

\emph{Base case} ($n=1$).  Me and mine are the only couple at the party
(some party \texttt{:-(}).  Since I don't shake hands with my spouse, I
have shaken $0= n-1$ hands.

{Induction case}: Assume $P(n)$ is true for $n\geq 1$ in order to
prove $P(n+1)$.

Consider a party with $n+1$ couples where all the people besides me shake
hands with different numbers of people.

Now there are $2n+1$ people besides me, and the largest number of people
anyone can shake hands with is $2n$.  Since there are only $2n+1$ integers
between 0 and $2n$, and none of the other people shake the same number of
hands, there must be one other person who has shaken $2n$ hands; likewise,
there must be one other person who has shaken 0 hands.  Now the person who
shook $2n$ hands---call this person the \emph{lead shaker}---must have
shaken with everyone in the room except themselves and their spouse.  So
the person who shook 0 hands must be the lead shaker's spouse, and
everyone else, including me, must have shaken the lead shaker's hand.

Now suppose we remove the lead couple, and consider the subparty of the
remaining $n$ couples.  I'm in this subparty since the lead couple were
people other than me.  Consider the number of times other people in this
subparty have shaken hands among themselves, \ie not counting handshakes
with the lead couple.  For each person in the subparty, this number is
exactly one less than before, because we no longer count the shake with
the lead shaker.  So in the subparty, it's still the case that no two
other people shake hands with the same number of people.  This is exactly
the premise of $P(n)$.  So we conclude from $P(n)$ that I must have shaken
$n-1$ hands within the subparty.  Adding the one handshake with the lead
shaker, I must have shaken a total of $n$ hands in the original party with
$n+1$ couples.  So we have proved $P(n+1)$.

\end{proof}

So with $n= 12$ couples, the answer is that I shook $n-1= 11$ hands.}
\end{problem}

\iffalse
%% Original problem, recursively defined set (of arithmetic expressions);
%% modular arithmetic.

\begin{problem}
Define the set of \emph{Arithmetic Expressions} (AExp's) recursively as follows:
\begin{enumerate}

\item base cases:
\begin{enumerate}

\item a \emph{variable} is an AExp.

\item an \emph{integer} is an AExp.

\end{enumerate}
\item if $F,G$ are AExp's, the ($F$ + $G$) is an AExp called a \emph{sum}.

\item if $F,G$ are AExp's, then ($F \cdot G$) is an AExp called a \emph{product}.

\end{enumerate}
For example,
\[
(((3 \cdot x) + y) \cdot ((y\cdot (-5)) + 92)).
\]
Omitting unnecessary parentheses and the multiplication sign ($\cdot$), we
could write this in the easier to read form
\begin{equation}\label{ae1}
(3 x + y)(y(-5) + 92).
\end{equation}

The value of expression~\ref{ae1} depends on the values of $x$ and $y$ in
the obvious way.  For example, if $x=2$ and $y=1$, its value is $7\cdot87
=609$.
\begin{problemparts}

\problempart Prove that for any AExp, $E$, with variables $x_1, x_2,\dots$
and any $n>1$, if $k_1 \equiv l_1 \mod n$, $k_2 \equiv l_2 \mod n$, \dots,
the value of $E$ when the variables equal $k_1,k_2,\dots$ is $\equiv \mod
n$ to the value of $E$ when the variables equal $l_1,l_2,\dots$.

\problempart If an AExp is not constant, then the value of the expression
at some natural number assignment to its variables is not a prime.

\end{problemparts}
\end{problem}
\fi

\iffalse

%F01 Q1  Double induction, uniqueness.  Could be extended to cover
% recursively defined set of pairs and prove existence of function.
% BETTER TO RE-EDIT AS A PSET PROBLEM.

\begin{problem}
Ackermann's function, $f: \naturals \cross \naturals \to \naturals$, satisfies
the following equations:
\begin{align}
f(m,n) &=  2n, &&\text{if $m=0$ or $n \le 1$},\label{Am0}\\ 
f(m,n) &=  f(m-1,f(m,n-1)), &&\text{if $m > 0$ and $n > 1$}.\label{AA}
\end{align}

These equations actually determine Ackermann's function uniquely.  That
is,
\begin{lemma*}
If $g: \naturals \cross \naturals \to \naturals$ also satisfies
the same equations as $f$, namely,
\begin{align}
g(m,n) &=  2n, &&\text{if $m=0$ or $n \le 1$},\label{Bm0}\\ 
g(m,n) &=  g(m-1,g(m,n-1)), &&\text{if $m > 0$ and $n > 1$},\label{BB}
\end{align}
then $f = g$.
\end{lemma*}

In this question, we ask you to fill in or justify various parts of a
proof of this Lemma.   The possible justifications are listed below.
You must choose your answers from this list.

\begin{itemize}
\item one or more of the equations (\emph{indicate exactly which ones}) numbered
(\ref{Am0}), (\ref{AA}), \dots (\ref{AB})
\item $P(0)$
\item $P(m)$
\item $P(m+1)$
\item $Q_m(0)$
\item $Q_m(n)$
\item $Q_0(n)$
\item $Q_m(n+1)$
\end{itemize}

\begin{proof}
We must prove that
\begin{equation}
\forall m\, \forall n\ f(m,n) = g(m,n). \label{a=b}
\end{equation}

The proof is by induction on $m$.  More precisely, the main induction
hypothesis, $P(m)$, is
\[
P(m) \eqdef\ \forall n\ f(m,n) = g(m,n).
\]

\textbf{Base case}: $m=0$.  It follows directly from equation(s)
\brule{4em} \solution{(\ref{Am0}), ~(\ref{Bm0})}

that $f(m,n) = g(m,n)$ for all $n$, confirming that \brule{4em}
\solution{$P(0)$}\\
is true.

\textbf{Induction step}: Suppose $P(m)$ holds for some fixed $m \geq
0$.  We must prove that $P(m+1)$ also holds.

Namely, assuming $\forall n\ f(m,n)=g(m,n)$, we must prove
(\textbf{fill-in}):
\begin{equation}
\forall n\; \brule{2in} \label{m+1}
\end{equation}
\solution{$f(m+1,n)=g(m+1,n)$}

We prove~(\ref{m+1}) by another induction, this time on $n$,
using the induction hypothesis,
\[
Q_m(n) \eqdef\ f(m+1, n) = g(m+1,n).
\]

%%\begin{quotation}
\addtolength{\leftskip}{0.5in}%

\textbf{Base case}: $n=0$.  $Q_m(0)$ follows immediately from equation(s)
\brule{4em}.  \solution{ (\ref{Am0}), ~(\ref{Bm0})}

\textbf{Induction step}: Suppose $Q_m(n)$ holds for some $n \geq 0$.  We
must prove that $Q_m(n+1)$ also holds.

Let $k \eqdef f(m+1, n)$, so
\begin{equation}
f(m+1, n+1) = f(m,k)\label{Ak}
\end{equation}
by \brule{1in} \solution{ (\ref{AA})}.

Then also
\begin{equation}
k = g(m+1, n),\label{kB}
\end{equation}
because \brule{1in} \solution{$Q_m(n)$}\\
holds, and so
\begin{equation}
g(m+1, n+1) = g(m,k)\label{Bk}
\end{equation}
by \brule{1in} \solution{(\ref{BB})}.

But
\begin{equation}
f(m,k) = g(m,k),\label{AB}
\end{equation}
since \brule{1in}\solution{$P(m)$}\\
holds.  Now combining equations \brule{5em}
\solution{(\ref{Ak}), (\ref{Bk}), and~(\ref{AB})},\\
we obtain
\[
f(m+1, n+1) = g(m+1,n+1).
\]
That is, $Q_m(n+1)$ holds.

This completes the proof by induction on $n$ that~(\ref{m+1}) holds.
%%\end{quotation}
\addtolength{\leftskip}{-0.5in}%

So we have also completed the proof by induction on $m$ that $\forall m\;
\brule{3em}$. \solution{$P(m)$}\\

That is, we have proved~(\ref{a=b}), as required.

\end{proof}
\end{problem}
\fi

\end{document}
