\documentclass[12pt,twoside]{article}
\usepackage{graphics}
\input{macros-course}
\begin{document}

\psol{2}{September 25, 1998}

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

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

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

\bigskip

\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 Use induction to prove that the following equation holds for
all $n \geq 1$.

\begin{eqnarray*}
\frac{1}{2^1} + \frac{1}{2^2} + \frac{1}{2^3} + \ldots \frac{1}{2^n}
	& = & 1 - \frac{1}{2^n}
\end{eqnarray*}

\bigskip

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

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

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Use induction on $n$ to prove that the following inequality
holds for all integers $n \geq 1$ and for all non-negative real
numbers $x_1, \ldots, x_n$.

\begin{eqnarray*}
(x_1 + x_2 + \ldots + x_n)^2 \geq x_1^2 + x_2^2 + \ldots + x_n^2
\end{eqnarray*}

\bigskip

\begin{proof}
The proof is by induction on $n$.  Let $P(n)$ be the proposition that
the above inequality holds for all non-negative real numbers $x_1,
\ldots, x_n$.  In the base case, $P(1)$ is true because both sides of
the inequality are equal to $x_1^2$, and so the $\leq$ relation is
satisfied.  In the inductive step, for $n \geq 1$ assume $P(n)$ in
order to prove $P(n+1)$ as shown below.

\begin{eqnarray*}
(x_1 + x_2 + \ldots + x_n + x_{n+1})^2
	& = &	(x_1 + x_2 + \ldots + x_n)^2
		+ 2 (x_1 + x_2 + \ldots + x_n) x_{n+1}
		+ x_{n+1}^2 \\
	& \geq &	(x_1 + x_2 + \ldots + x_n)^2 + x_{n+1}^2 \\
	& \geq &	x_1^2 + x_2^2 + \ldots + x_n^2 + x_{n+1}^2
\end{eqnarray*}

The first step is algebra.  In the second step, a term is dropped;
this gives an inequality, because the dropped term must be
non-negative on account of all the $x_i$ being non-negative.  The
third step uses the induction hypothesis.  This shows that $P(n)$
implies $P(n+1)$, and the claim is proved by induction.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Use induction to prove that for all $n \geq 2$, the quantity
$n (n^2 - 1) (n^2 - 4)$ is either divisible by 5 or by 7.  For
example, $6 (6^2 - 1) (6^2 - 4) = 6720 = 7 \cdot 960$.

\medskip

\bigskip

An induction proof with the hypothesis that the expression is
divisible by 5 or by 7 will not go through; this assumption is not
strong enough to complete the inductive step.  In fact, the expression
is always divisible by 5, but is only sometimes divisible by 7.
Therefore, the right idea is to strengthen the induction hypothesis to
assert that the expression is always divisble by 5.

\begin{proof}
We will prove the stronger statement that $n (n^2 - 1) (n^2 - 4)$ is
always divisible by 5.  The proof uses the fact that this expression
can be rewritten by factoring $n^2 - 1$ and $n^2 - 4$ as follows:

\begin{eqnarray*}
n (n^2 - 1) (n^2 - 4) & = &(n - 2) (n - 1) n (n + 1) (n + 2).
\end{eqnarray*}

The proof now proceeds by induction.  Let $P(n)$ be the propositon
that $(n - 2) (n - 1) n (n + 1) (n + 2)$ is divisible by 5.  In the
base case, $P(5)$ is true because $5 (5^2 - 1) (5^2 - 4) = 2520 = 5
\cdot 504$.  In the inductive step, for $n \geq 2$ assume $P(n)$
to prove $P(n+1)$; that is, we want to prove that $(n - 1) n (n + 1)
(n + 2) (n + 3)$ is divisible by 5.  We can rewrite this expression as
follows.

\begin{eqnarray*}
(n - 1) n (n + 1) (n + 2) (n + 3)
	& = &	(n - 2) (n - 1) n (n + 1) (n + 2) + \\
	& \mbox{} &	5 (n - 1) n (n + 1) (n + 2)
\end{eqnarray*}

The top term on the right is divisible by 5 by the induction
hypothesis, and the botton term on the right is divisible by 5 because
the leading coefficient is 5.  Therefore, the right side and the left
side of the equation are both divisible by 5.  This shows that $P(n)$
implies $P(n+1)$, and the claim is proved by induction.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\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.

\bigskip

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\problem The 6.042 mascot, Theory Pig, made a startling discovery while
playing with his prized collection of unit squares over the weekend.
Here is what happened.

First, Theory Pig put his favorite unit square down on the floor as in
diagram (a) of Figure~\ref{fig:squares}.  He noted that the length of
the periphery of the resulting shape was 4, an even number.  Next, he
put a second unit square down next to the first so that the two
squares shared an edge as in diagram (b).  He noticed that the length
of the periphery of the resulting shape was now 6, which is also an
even number.  (The periphery of each shape in the figure is indicated
by a thicker line.)  Theory Pig continued to place squares so that
each new square shared an edge with at least one previously-placed
square and no squares overlapped.  Eventually, he arrived at the shape
in diagram (c).  He realized that the length of the periphery of this
shape was 36, which is again an even number.

Our plucky porcine pal is perplexed by this peculiar pattern.  Use
induction on the number of squares to prove that periphery length is
always even, no matter how many squares Theory Pig places or how he
arranges them.

\begin{figure}[htbp]
\centerline{\resizebox{!}{2.0in}{\includegraphics{ps2.eps}}}
\caption{Some shapes that Theory Pig created.} \label{fig:squares}
\end{figure}

\bigskip

\begin{proof}
The proof is by induction.  Let $P(n)$ be the proposition that the
periphery length is even after $n$ squares are placed.  In the base
case, $P(1)$ is true because the periphery of a single square has
length 4, which is even.

In the inductive step, assume that the periphery length is even after
$n$ squares are placed to prove that the periphery length is even
after $n+1$ squares are placed.  The $(n+1)$-st square could share 1,
2, 3, or 4 edges with previously-placed squares.

\begin{itemize}

\item If the new square shares 1 edge with a previously placed square,
then this one edge is removed from the periphery, but three edges of
the new square are added to the periphery.  Overall, the periphery
length increases by two and thus remains even.

\item If the new square shares 2 edges with previously placed squares,
then these two edges are removed from the periphery, but two edges of
the new square are added.  The periphery length is unchanged and thus
remains even.

\item If the new square shares 3 edges, then these three edges are removed
from the periphery, but one edge is added.  The periphery length
decreases by two and remains even.

\item If the new square shares 4 edges, then these four edges are removed
from the periphery and none are added.  The periphery length decreases
by four and remains even.

\end{itemize}

In all cases, the length of the periphery remains even.  Therefore,
for all $n \geq 1$, $P(n)$ implies $P(n+1)$ and the claim is proved by
induction.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem The 6.042 course information sheet states:

\begin{quotation}
During the second hour or so [of recitation], the students will work
in groups of three or four, and each group will be assigned a problem
to solve as a team.
\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.

\bigskip

\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 Suppose that the sequence $x_1, x_2, x_3, \ldots$ is defined
as follows.  The first term, $x_1$, is equal to 1.  For $n \geq 1$,
the term $x_{n+1}$ is equal to $x_n$ if $n+1$ is odd and is equal to
$1 + x_{(n+1)/2}$ if $n+1$ is even.  Use strong induction on $n$ to
prove that for all $n \geq 1$, the number of digits in the binary
representation of $n$ is equal to $x_n$.

\bigskip

\begin{proof}
The proof is by strong induction.  Let $P(n)$ be the proposition there
are $x_n$ digits in the binary representation of $n$.  In the base
case, $P(1)$ is true because there is a single digit in the binary
representation of 1.  In the inductive step, for $n \geq 1$, assume
$P(1), \ldots, P(n)$ to prove $P(n+1)$.  There are two cases to
consider.

\begin{enumerate}
\item If $n+1$ is odd, then the binary representation of $n+1$ is the
binary representation of $n$ with the least significant digit changed
from a zero to a one.  By the induction hypothesis, there are $x_n$
digits in the binary representation of $n$.  Therefore, there also are
$x_n = x_{n+1}$ digits in the binary representation of $n+1$.

\item If $n+1$ is even, then the binary representation of $n+1$ is the
binary representation of $(n+1)/2$ with a zero appended.  By the
induction hypothesis, there are $x_{(n+1)/2}$ digits in the binary
representation of $(n+1)/2$.  Therefore, there are $1 + x_{(n+1)/2} =
x_{n+1}$ digits in the binary representation of $n+1$.
\end{enumerate}

This shows that $P(1), \ldots, P(n)$ imply $P(n+1)$, and the claim is
proved by induction.
\end{proof}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Suppose that $x_0 = 0$, $x_1 = \frac{1}{2}$, and the
following equation holds for all $n \geq 1$:

\begin{eqnarray*}
x_{n+1} + x_{n-1} = \sqrt{3} x_{n}
\end{eqnarray*}

Use strong induction to prove that $x_n =
\sin(\frac{n \pi}{6})$ for all $n \geq 0$.

\bigskip

\begin{proof}
The proof will make use of the trignometric identity for a sum of sines,

\begin{eqnarray*}
\sin A + \sin B	& = &	2 \cos\frac{A-B}{2} \sin\frac{A+B}{2}.
\end{eqnarray*}

In particular, the following form of the identity will be needed:

\begin{eqnarray*}
\sin A  	& = &	2 \cos\frac{A-B}{2} \sin\frac{A+B}{2} - \sin B
\end{eqnarray*}

The proof is by strong induction.  Let $P(n)$ be the proposition that
$x_n = \sin \frac{n \pi}{6}$.  In the base cases, $P(0)$ is true
because $x_0 = 0 = \sin 0$, and $P(1)$ is true because $x_1 =
\frac{1}{2} = \sin \frac{\pi}{6}$.  In the inductive step, for $n \geq
1$ assume $P(0), \ldots, P(n)$ to prove $P(n+1)$.  That is, we want to
prove that $x_{n+1} = \sin \frac{(n+1) \pi}{6}$.  The equation stated
in the problem can be rewritten as follows:

\begin{eqnarray*}
x_{n+1}
	& = &	\sqrt{3} x_{n} - x_{n-1} \\
	& = &	\sqrt{3} \sin \frac{n \pi}{6} -
			\sin\frac{(n - 1) \pi}{6} \\
	& = &	\sin \frac{(n+1) \pi}{6}
\end{eqnarray*}

The second equation follows from the induction hypothesis, and the
third equation follows from the sum-of-sines identity with $A =
\frac{(n + 1) \pi}{6}$ and $B = \frac{(n - 1) \pi}{6}$.  Therefore,
$P(0), \ldots, P(n)$ imply $P(n+1)$, and the claim is proved by strong
induction.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem There are two types of creature on planet Xoros 19, A-lings
and B-lings. Furthermore, every creature belongs to a particular
generation.  The creatures in each generation reproduce according to
certain rules and then die off.  The subsequent generation consists
entirely of their offspring.

The creatures of Xoros 19 pair with a mate in order to reproduce.
First, as many A-B pairs as possible are formed.  The remaining
creatures form A-A pairs or B-B pairs, depending on whether there is
an excess of A-lings or of B-lings.  If there are an odd number of
creatures, then one in the majority species dies without reproducing.
The number and type of offspring is determined by the types of the
parents

\begin{itemize}
\item If both parents are A-lings, then they have three A-ling
offspring.

\item If both parents are B-lings, then they have two B-ling offspring
and one A-ling offspring.

\item If there is one parent of each type, then they have one
offspring of each type.
\end{itemize}

There are 200 A-lings and 800 B-lings in the first generation.  Use
induction to prove that the number of A-lings will always be at most
twice the number of B-lings.

\bigskip

An induction proof with the hypothesis that the number of A-lings is
always at most twice the number of B-lings will not go through.  A
stronger induction hypothesis is required.

\medskip

\begin{proof}
We will prove that there are always at least as many B-lings as
A-lings; the claim that the number of A-lings is always at most twice
the number of B-lings is weaker and thus follows.

The proof is by induction on the generation number.  Let $P(n)$ be the
proposition that there are at least as many B-lings as A-lings in
generation $n$.  In the base case, $P(1)$ is true because there are
800 B-lings and only 200 A-lings in the first generation.

In the inductive step, for $n \geq 1$ assume that there are at least
as many B-lings as A-lings in generation $n$ to prove that there are
at least as many B-lings as A-lings in generation $n+1$.  Let $a$ be
the number of A-lings in generation $n$, and let $b$ be the number of
B-lings.  Note that $b \geq a$ by the induction assumption.  Then
there are no A-A pairs formed, there are $a$ A-B pairs formed, and
there are $\lfloor \frac{b - a}{2} \rfloor$ $B-B$ pairs formed.  As a
result, the number of A-lings in generation $n+1$ is $a + \lfloor
\frac{b - a}{2} \rfloor$, and the number of B-lings is $a + 2 \lfloor
\frac{b - a}{2} \rfloor$.  Therefore, there are at least as many
B-lings as A-lings in generation $n+1$.  Thus, for all $n \geq 1$,
$P(n)$ implies $P(n+1)$, and the claim is proved by induction.
\end{proof}

\end{problems}
\end{document}
