\problem Use induction to prove that the following equation holds for all
$n \geq 2$.

\begin{equation*}
\left(1 - \frac{1}{2}\right)
\left(1 - \frac{1}{3}\right)
\cdots
\left(1 - \frac{1}{n}\right)  =  \frac{1}{n}
\end{equation*}

\solnospace{\begin{proof}
The proof is by induction on $n$.  Let $P(n)$ be the proposition that
the above equation holds.  In the base case, $P(2)$ is true because
$(1 - \frac{1}{2}) = \frac{1}{2}$.  In the inductive step, for $n \geq
2$ assume $P(n)$ to prove $P(n+1)$ as follows.

\begin{eqnarray*}
\left(1 - \frac{1}{2}\right) \left(1 - \frac{1}{3}\right)
\cdots
\left(1 - \frac{1}{n}\right) \left(1 - \frac{1}{n+1}\right)
        & = &   \frac{1}{n} \left(1 - \frac{1}{n+1}\right) \\
        & = &   \frac{1}{n} \cdot \frac{n}{n+1} \\
        & = &   \frac{1}{n+1}
\end{eqnarray*}

The first step uses the induction hypothesis, and the second and third
steps are simplifications.  This shows that $P(n)$ implies $P(n+1)$,
and the claim is proved by induction.
\end{proof}
}

\problem
% Ordinary induction, tiling
Velleman 6.2, problem 6.

\solnospace{
The proof is by induction.

Let P(n) be the proposition that any equilateral triangle, that is cut into 
$4^n$ congruent equilateral triangles with one corner removed, can be tiled 
using tiles composed of three of the smaller congruent triangles.

\textbf{Base case} $n=1$:  With one corner removed, a single tile can be
used to cover the remaining area.
%\mbox{\epsfbox{figures/ps2P5BaseCase.ps}}

\textbf{Inductive step}: Consider a triangle, $T$, cut into $4^{n+1}$
congruent equilateral triangles.  We can think of this triangle as being
cut into four smaller equilateral triangles, which are each then cut into
$4^n$ equilateral triangles.  Remove the top corner of $T$.  We know that
we can tile the triangle that contains the removed corner by the inductive
hypothesis.  Note that the remaining area contains three triangles, who
have corners that meet in the same place; namely, the bottom of T,
directly below the removed corner.  If we consider each of these triangles
with the touching corners removed, then the inductive hypothesis says that
we can tile each one separately.  To complete the tiling, simply use a
single tile to cover the three adjacent removed corners, illustrated in
Figure~\ref{triangle}.

\begin{figure}[ht]
\centering
\includegraphics[width=4in]{figures/ps2P5inductive}
\caption{The original triangle $T$.  Dark lines indicate borders of the four
smaller triangles; light lines indicate borders of the $4^n$ triangles
that the smaller triangles are cut into.  The black triangle is the removed
corner; the gray triangles indicate the corners that are removed from the
smaller triangles in order to apply the inductive hypothesis, which are
then covered by a single tile.}\label{triangle}
\end{figure}
}

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

\bparts
\ppart 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}

\solspace{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$.}

\ppart 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}

\solnospace{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.}

\eparts

\problem The 6.042 course information sheet states:

\begin{quotation}\noindent
Tutorials will be devoted to solving interesting problems, with students
working in teams of three or four.
\end{quotation}

Using strong induction, prove that if a recitation contains at least 6
students, then the class can be divided into teams, each consisting of
either 3 or 4 students.

\solnospace{\begin{proof}
The proof is by strong induction.  Let $P(n)$ be the proposition that
a recitation with $n$ students can be divided into teams of 3 or 4.
In the base cases, $P(6)$ is true because there could be two teams of
3, $P(7)$ is true because there could be a team of 3 and a team of 4,
and $P(8)$ is true because there could be two teams of 4.  In the
inductive step, for $n \geq 8$, assume $P(6), \ldots, P(n)$ to prove
$P(n+1)$.  If a recitation has $n+1$ students, then three students can
form a team of 3, and the remaining $n-2$ students can be divided into
teams of 3 or 4 by induction.  This shows that $P(6), \ldots, P(n)$
imply $P(n+1)$, and the claim is proved by induction.
\end{proof}}


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

\solnospace{
\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}
}

\iffalse
\solnospace{
\begin{proof}
The proof is by strong induction.  

The inductive hypothesis for proving that the $\sqrt{2}$ is irrational
is given in Velleman (6.4.3): 
\[
P(q) \eqdef \neg \exists p \in \naturals\;  p/q = \sqrt{2}.
\]

\textbf{Base case:} $q=1$.  If $p/1 = \sqrt{2}$ then $\sqrt{2}$ equals an
integer $p$.  Since we know that $\sqrt{2} = 1.414\dots$ is not an
integer, there doesn't exist such a $p \in \naturals$.

\textbf{Induction step:} Suppose that for some $q \ge 1$, there doesn't
exist a $p$ such that $p/q=\sqrt{2}$.  We must show that there does not
exist a $p$ such that $p/(q+1) = \sqrt{2}$.

Now let us consider two cases.

Case 1: $\sqrt{2}$ is irrational.  In this case, we've proven what we
wanted to prove.

Case 2: $\sqrt{2}$ is rational, and can be expressed as $m/n$.  But then
there would exist a $p\prime$ (namely $mn/n - m/n$) that would make
$p\prime/q=\sqrt{2}$, contradicting our inductive hypothesis.

Because we reach this contradiction, we know that there must not exist
a $p$ that makes $p/(q+1) = \sqrt{2}$.
\end{proof}
}\fi


\problem We are given a chocolate bar with $m \times n$ squares of
chocolate, and our task is to divide it into $mn$ individual squares.  We
are only allowed to split one piece of chocolate at a time using a
vertical or a horizontal break.

For example, suppose that the chocolate bar is $2 \times 2$.  The
first split makes two pieces, both $2 \times 1$.  Each of these pieces
requires one more split to form single squares.  This gives a total of
three splits.

\bparts \ppart Use strong induction to conclude the following:
\begin{theorem*}
To divide up a chocolate bar with $m \times n$ squares, we need at
most $m n - 1$ splits.
\end{theorem*}

\solnospace{This theorem does not immediately lend itself to an induction
proof, since there are two variables.  In general, propositions involving
several natural-valued variables can often be proved by using a sort of
nested induction.  However, in this case, we can get by with a
single-variable induction and a trick.

Intuitively, to break up a big chocolate bar, we need one split to
make two pieces, and then we can break up the two pieces recursively.
This suggests a proof using strong induction on the {\em size} of the
chocolate bar, where size is measured in chocolate squares.  Now
instead of a problem involving two variables (the two dimensions), we
have a problem in one variable (the size).  With this simplification,
we can prove the theorem using strong induction.

\begin{proof}
The proof is by strong induction on the size of the chocolate bar.  Let
$P(k)$ be the proposition that a chocolate bar of size $k$ requires at
most $k - 1$ splits.  

\emph{Base case, $k=1$}: $P(1)$ is true because there is only a single
square of chocolate, and $1 - 1 = 0$ splits are required.

\emph{Induction step}: We suppose $k \geq 1$ and any chocolate bar of size
$s$, where $1 \leq s \leq k$, requires at most $s-1$ splits.  We must now
show there is a way to split a chocolate bar of size $k+1$ with at most
$k$ splits.

To do this, first break the chocolate bar of size $k+1$ into two smaller
pieces of size $p$ and $q$ where $p + q = k + 1$.  This is certainly
possible because the size of the bar is at least two.  Now the pieces of
sizes $p$ and $q$ are between one and $k$, so by strong induction,
breaking these two pieces into single squares requires only $p - 1$ and $q
- 1$ splits, respectively.  The total number of splits required to break
the bar of size $k+1$ into single squares is therefore at most $1 + (p -
1) + (q - 1) = p + q - 1 = (k + 1) - 1 = k$.

This shows that $P(k)$ implies $P(k+1)$, and the claim is proved by
strong induction.
\end{proof}
}

\ppart The theorem proves that \emph{at most} $mn - 1$
splits are needed to divide up an $m$ by $n$ chocolate bar.  Could you do
better?

\solnospace{The proof really shows that exactly $s - 1$ splits are
needed.  Observe that in the induction step, no matter how we split the
bar into smaller bars of size $p$ and $q$, exactly $(p - 1) + (q - 1) = s
- 1$ splits are required.}
\eparts

\problem Velleman, Exercise 6.4.6

\solnospace{
a) Prove that $d \divides a$.  This is a proof using the least number
principle.  We have chosen $d$ so that it is the smallest element of
$S$. Using the division algorithm, we can express $a$ in terms of $d$:
$a = dq+r$ where $0 \leq r < d$. Note that if $a=dq+r$ then
$d=(a-r)/q$.  Using the definition of $S$ we know
that there exists integers $s$ and $t$ such that $d=as+bt$.
Substituting in for $d$ we get $(a-r)/q=as+bt$, which, with a little
bit of algebra, gives us $r=a(1-sq)+b(-tq)$.  Since $(1-sq)$ and
$(-tq)$ are integers, $r$ must be in $S$ if it is not 0.  This
contradicts the choice of $d$ as the smallest element of $S$.  This
proves that $r=0$, so $a=dq$ and therefor $d \divides a$.

Prove that $d \divides b$.  This also is a proof using the least number
principle.  Again, we have chosen $d$ so that it is the smallest
element of 
$S$.  Using the division algorithm, we can express $b$ in terms of
$d$: $b = dq+r$ where $0 \leq r < d$.  Note that if $b=dq+r$ then
$d=(b-r)/q$.  Using the definition of $S$ we know
that there exists integers $s$ and $t$ such that $d=as+bt$.
Substituting in for $d$ we get $(b-r)/q=as+bt$, which, with a little
bit of algebra, gives us $r=a(-sq)+b(1-tq)$.  Since $(-sq)$ and
$(1-tq)$ are integers, $r$ must be in $S$ if it is not 0.  This
contradicts the choice of $d$ as the smallest element of $S$.  This
proves that $r=0$, so $b=dq$ and therefor $d \divides b$.

b) If $c$ divides $a$ then there exists some integer $p$ such that
$a=cp$.  Similarly, if $c$ divides $b$ then there exists some integer
$q$ such that $b=cq$.  Since $d \in S$ we know that $d=as+bt$, which,
given $c$ divides both $a$ and $b$, is $d=acs+bct=c(as+bt)$, showing
that $c \divides d$.
}

\problem (* difficult) %From F97 PS2 Problem 10, much revised by ARM

An $n$-player tournament, consists of some set of $n\geq 2$
\emph{players}, and, for every two distinct players, a specification that
one of the players beats the other.  That is, player $p$ beats player $q$
iff $q$ does not beat $p$, for all players $p \neq q$.

A sequence of distinct players $p_1,p_2, \ldots, p_k$, such that player
$p_i$ beats player $p_{i+1}$ for $1 \leq i < k$ is called a {\em ranking}
of these players.  If also player $p_k$ beats player $p_1$, the ranking is
called a $k$-\emph{cycle}.

\bparts

\ppart Prove by induction that in every tournament, either there is a
``champion'' player that beats every other player, or there is a 3-cycle.

\solnospace{The induction hypothesis $P(n)$, is
``In an $n$-player tournament, either there is a player that
beats every other player, or there is a 3-cycle.''

\textbf{Base case} $n=2$: By definition of a 2-player tournament, one of the
players beats the only other player and therefore is the champion.

\textbf{Inductive step}:
Assume that $P(n)$ is true in order to show that $P(n+1)$ is true.

Consider an $n+1$-player tournament.  If there is a champion, we are done.
So we may assume that every player is beaten by some other player.  Now
remove any player, say player $p$, and treat the remaining $n$ players as an
$n$-player tournament.  There are two cases:

1) Every player in the $n$-player tournament is beaten by some other
player in the tournament.

2) There is some champion in the $n$-player tournament who beats every
other player in the $n$-player tournament.

In case (1), we have by induction hypothesis a 3-cycle of players in the
$n$-player tournament.  Since a 3-cycle in the $n$-player tournament will
also be a 3-cycle in the full $n+1$-player tournament, we are OK in this
case.

In case (2), there is some ``champion'', $q$, in the $n$-player
tournament.  Since everybody in the ($n+1$)-player tournament is beaten by
somebody, $q$ must be beaten by a player not in the $n$-player tournament,
that is, $p$ beats $q$.  For the same reason, there is some
player $r$ that beats $p$.  Since $r$ is in the $n$-player tournament, $r$
is beaten by the champion $q$.  So we have found a 3-cycle $p,q,r$.
}

\ppart
A {\em consistent ranking} is a sequence $p_1,p_2, \ldots, p_n$ of all
$n$ players in the tournament such that $p_i$ beats $p_j$ iff $i < j$, for
$1 \leq i,j \leq n$.  Conclude that a tournament has no consistent ranking
iff some subset of three of its players has no consistent ranking.

\solnospace{By definition of tournament, the restriction of the
tournament to any subset of two or more of its players is also a
(sub)tournament.  Also any consistent ranking of a tournament remains
consistent when restricted to a subset of players.  So if some subset of
three players has no consistent ranking, then the whole tournament
can't have a consistent ranking either.

So we have only to prove the converse implication: if every three players
have a consistent ranking, then the tournament as a whole has one.
The proof is by induction on $n$.

{\bf Base case $n=2$:} Every two player tournament obviously has a
consistent ranking.

{\bf Inductive step:} Suppose $n\ge2$ and there is a consistent ranking of
any tournament of $n$ players whose three-player subsets have consistent
rankings.  Now consider any $n+1$ player tournament whose three-player
subsets have consistent rankings.

This tournament cannot have a 3-cycle, because there is no consistent
ranking for the players in the 3-cycle.  Hence, by the previous part, the
tournament has a champion.  The $n$-player tournament obtained by ignoring
the champion also has no 3-cycles, so by induction it has a consistent
ranking.  Then this ranking of $n$-nonchampions followed by the champion
at then end is a consistent ranking of the whole tournament of $n+1$
players.
}
\eparts

\iffalse  Not a bad problem, but kind of dry.

\problem Use induction on $n$ to prove that for all $n \geq 0$, there
are $2 n^2 + 2n + 1$ solutions to the inequality $|x| + |y| \leq n$,
where $x$ and $y$ are integers.

\solnospace{\begin{proof}
The proof is by induction on $n$.  Let $P(n)$ be the proposition that
there are $2 n^2 + 2n + 1$ solutions to the inequality $|x| + |y| \leq
n$, where $x$ and $y$ are integers.  In the base case, $P(0)$ is true
because $2 (0)^2 + 2 (0) + 1 = 1$, and there is one solution to the
equation $|x| + |y| \leq 0$, namely $x = y = 0$.

In the inductive step, assume $P(n)$ to prove $P(n+1)$.  That is, we
want to prove that there are $2 (n+1)^2 + 2 (n + 1) + 1 = 2n^2 + 6n +
5$ solutions to the inequality $|x| + |y| \leq n + 1$.  Every solution
to this inequality is also either a solution to the tighter inequality
$|x| + |y| \leq n$ or else to the equation $|x| + |y| = n + 1$.  Thus,
the number of solutions is equal to the number of solutions to the
tighter inequality plus the number of solutions to the equation.

By induction, there are $2 n^2 + 2n + 1$ solutions to the tighter
inequality.  All that remains is to count solutions to the equation.
The value of $x$ must be in the range $-(n+1), \ldots, n+1$.  If $x$
takes on either of the two values $-(n+1)$ or $n+1$, then there is a
single solution, with $y = 0$.  If $x$ takes on one of the $2n+1$
values in the range $-n, \ldots, n$, then there are two solutions, one
with $y = n + 1 - |x|$ and one with $y = -(n + 1 - |x|)$.  Thus, there
are $2 + 2 \cdot (2n + 1) = 4n + 4$ solutions to the equation and $2
n^2 + 2n + 1$ solutions to the tighter inequality, giving $2 n^2 + 6n
+ 5$ solutions in all, as desired.  Therefore, $P(n)$ implies
$P(n+1)$, and the claim is proved by induction.
\end{proof}
}
\fi
