\documentstyle[12pt,twoside,amsfonts,amstex,psfig]{article}
\input{macros-course}
\begin{document}

\pset{2}{September 15, 1998}{Start of class on September 22, 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*}

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

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

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

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

\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{\psfig{figure=ps2.eps,height=2.0in}}
\caption{Some shapes that Theory Pig created.} \label{fig:squares}
\end{figure}

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

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

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

\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.
\end{problems}
\end{document}
