\documentclass[twoside,12pt]{article}
\usepackage{light}

\showsolutions
%\hidesolutions

\begin{document}

\problemset{2}{September 14, 2004}{Monday, September 20 at 9 PM}

\newcommand{\beqn}{\begin{eqnarray*}}
\newcommand{\eeqn}{\end{eqnarray*}}

%\insolutions{\stamp}

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

\begin{problem}[10 points]
Use induction to prove that the following inequality holds for all
integers $n \geq 1$.
%
\[
\frac{1 \cdot 3 \cdot 5 \cdots (2n - 1)}{2 \cdot 4 \cdot 6 \cdots (2n)}
    \geq \frac{1}{2n}
\]

\solution{
\begin{proof}
We use induction.  Let $P(n)$ be the proposition that:
%
\[
\frac{1 \cdot 3 \cdot 5 \cdots (2n - 1)}{2 \cdot 4 \cdot 6 \cdots (2n)}
    \geq \frac{1}{2n}
\]

\noindent \textit{Base case:} First, we prove $P(1)$.  In this case, both
side of the inequality are equal to $1/2$, and the inequality $1/2
\geq 1/2$ holds.

\noindent \textit{Inductive step:} For each $n \geq 1$, we must show
that $P(n)$ implies $P(n+1)$.  So assume that $P(n)$ is true, where $n
\geq 1$.  Then we can reason as follows:
%
\begin{align*}
\frac{1 \cdot 3 \cdot 5 \cdots (2n - 1) (2n + 1)}
     {2 \cdot 4 \cdot 6 \cdots (2n) \cdot (2n + 2)}
    & \geq \frac{1}{2n} \cdot \frac{2n+1}{2n+2} \\
    & > \frac{1}{2n+2}
\end{align*}
%
The first step uses the induction hypothesis, $P(n)$, and the second
uses the fact that $(2n+1) / (2n) > 1$ for all $n \geq 1$.  Therefore,
the proposition $P(n)$ is true for all $n \geq 1$ by the principle of
induction, which proves the claim.
\end{proof}
}
\end{problem}

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

\begin{problem}[10 points]
Use induction to prove that for all $\theta \in \mathbb{R}$ and all $n
\geq 0$:
%
\[
(\cos \theta + i \sin \theta)^n = \cos(n \theta) + i (\sin n \theta)
\]
%
(Hint: You'll need a couple standard trigonometric identities.  These
can be found in most calculus books.  You need not cite a source.)
\end{problem}

\solution{
\begin{proof}
We use induction.  Let $P(n)$ be the proposition that:
%
\[
(\cos \theta + i \sin \theta)^n = \cos(n \theta) + i (\sin n \theta)
\]

\noindent \textit{Base case:} $P(0)$ is true, because both sides of
the equation are equal to 1.

\noindent \textit{Inductive step:} We must show that $P(n)$ implies
$P(n+1)$ for all $n \geq 0$.  So assume that $P(n)$ is true, where $n
\geq 0$.  We can reason as follows:
%
\begin{align*}
(\cos \theta + i \sin \theta)^{n+1}
    & = (\cos \theta + i \sin \theta)^n \cdot (\cos \theta + i \sin \theta) \\
    & = \bigl(\cos(n \theta) + i (\sin n \theta)\bigr) \cdot (\cos \theta + i \sin \theta) \\
    & = (\cos(n \theta) \cos \theta - \sin n \theta \sin \theta) +
        i (\sin n \theta \cos \theta + \cos n \theta \sin \theta) \\
    & = \cos((n+1)\theta) + i \sin((n+1)\theta)
\end{align*}
%
The first step is algebra.  Then we use the assumption $P(n)$ and
multiply out on the third line.  The last equation follows from the
addition formulas for sine and cosine.  This shows that $P(n)$ implies
$P(n+1)$.

By the principle of induction, $P(n)$ is true for all $n \geq 0$.
\end{proof}
}

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

\begin{problem}[10 points]
Use induction to prove that the following equation holds for all $n
\geq 0$:
%
\[
1^3 + 2^3 + 3^3 + \ldots + n^3 = (1 + 2 + 3 + \ldots + n)^2
\]
\end{problem}

\solution{
\begin{proof}
We can rewrite the right side using the equation:
%
\[
1 + 2 + 3 + \ldots + n = \frac{n(n+1)}{2}
\]
%
Thus, it is sufficient to prove that:
%
\[
1^3 + 2^3 + 3^3 + \ldots + n^3 = \frac{n^2(n+1)^2}{4}
\]
%
Now we proceed by induction.  Let $P(n)$ be the proposition that:
%
\[
1^3 + 2^3 + 3^3 + \ldots + n^3 = \frac{n^2(n+1)^2}{4}
\]

\noindent \textit{Base case:} $P(0)$ is true, because both sides of
the equation are equal to zero.

\noindent \textit{Inductive step:} Now we assume $P(n)$ in order to
prove $P(n+1)$, where $n \geq 0$.  We can reason as follows:
%
\begin{align*}
1^3 + 2^3 + 3^3 + \ldots + n^3 + (n+1)^3
    & = \frac{n^2(n+1)^2}{4} + (n+1)^3 \\
    & = \frac{(n^2 + 4(n+1))(n+1)^2}{4} \\
    & = \frac{(n+1)^2(n+2)^2}{4}
\end{align*}
%
The first step uses the induction assumption $P(n)$ and the remaining
steps are simplifications.  This shows that $P(n)$ implies $P(n+1)$
for all $n \geq 0$.

Thus, $P(n)$ is true for all $n \geq 0$ by the principle of induction.
\end{proof}
}

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

\begin{problem}[15 points] The inequality below holds for all integers
$n \geq 1$ and nonnegative real numbers $x_1, \ldots, x_n$.
%
\begin{equation}
(x_1 x_2 \ldots x_n)^{1/n} \leq \left(\frac{x_1 + x_2 + \ldots +
    x_n}{n}\right)
\end{equation}
\end{problem}

\bparts

\ppart Prove that the inequality holds for $n = 2$.  (Hint: Use the
fact that $(a - b)^2$ is never negative.)

\solution{
The square of a real number is always nonnegative, so:
%
\[
0 \leq (\sqrt{x_1} - \sqrt{x_2})^2
\]
%
Multiplying out the right side gives:
%
\[
0 \leq x_1 - 2 \sqrt{x_1 x_2} + x_2
\]
Moving the middle term to the left and then dividing both sides by 2
gives:
%
\[
\sqrt{x_1 x_2} \leq \frac{x_1 + x_2}{2}
\]
}

\ppart Use induction to prove that the inequality holds whenever $n$
is a power of 2.  (Hint: Reduce $P(n+1)$ to $P(n)$ by pairing up
variables.)

\solution{
We use induction.  Let $P(k)$ be the proposition that
%
\[
(x_1 x_2 \ldots x_n)^{1/n} \leq \left(\frac{x_1 + x_2 + \ldots + x_n}{n}\right)
\]
%
where $n = 2^k$.

\noindent \textit{Base case:} $P(0)$ is true, because both sides of
the inequality are equal to $x_1$.

\noindent \textit{Inductive step:} Now we assume that $P(k)$ is true
in order to prove $P(k+1)$, where $k \geq 0$.  We can reason as
follows:
%
\begin{align*}
(x_1 x_2 \ldots x_{2n})^{1/2n}
    & = \left(\sqrt{x_1 x_2} \sqrt{x_3 x_4} \ldots \sqrt{x_{2n-1} x_{2n}}\right)^{1/n} \\
    & \leq \frac{\sqrt{x_1 x_2} + \sqrt{x_3 x_4} + \ldots + \sqrt{x_{2n} x_{2n+1}}}{n} \\
    & \leq \frac{\frac{x_1+x_2}{2} + \frac{x_3+x_4}{2} + \ldots + \frac{x_{2n}+x_{2n+1}}{2}}{n} \\
    & = \frac{x_1 + x_2 + \ldots + x_{2n}}{2n}
\end{align*}
%
The first step is algebra.  Then we apply the induction assumption
$P(k)$ and the preceding problem part.  The last step is
simplification.  This proves $P(k+1)$, so we've shown that $P(k)$
implies $P(k+1)$ for all $k \geq 0$.

By the principle of induction, $P(k)$ is true for all $k \geq 0$.}

\eparts

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

\begin{problem}[15 points] Let $S_n$ be the sum of all fractions where the
numerator is 1 and the denominator is the product of a nonempty subset
of the integers $\set{1, 2, \ldots, n}$.  For example:
%
\begin{align*}
S_1 & = \frac{1}{1} \\
S_2 & = \frac{1}{1} + \frac{1}{2} + \frac{1}{1 \cdot 2} \\
S_3 & = \frac{1}{1} + \frac{1}{2} + \frac{1}{3} +
        \frac{1}{1 \cdot 2} + \frac{1}{1 \cdot 3} + \frac{1}{2 \cdot 3} +
        \frac{1}{1 \cdot 2 \cdot 3}
\end{align*}
%
Make a conjecture about the value of $S_n$ and use induction to prove
your conjecture correct.

\solution{Calculations show that $S_1 = 1$, $S_2 = 2$, and $S_3 = 3$,
so $S_n = n$ is a reasonable conjecture.

\begin{proof}
We use induction.  Let $P(n)$ be the propositon that $S_n = n$.

\noindent \textit{Base case:} $P(1)$ is true because:
%
\begin{eqnarray*}
S_1
    & = & \frac{1}{1} \\
    & = & 1
\end{eqnarray*}

\noindent \textit{Inductive step:} We must show that $P(n)$ implies
$P(n + 1)$ for all $n \geq 1$.  To that end, assume that $P(n)$ is
true, where $n$ is a positive natural number.  Then we can reason as
follows:
%
\begin{eqnarray*}
S_{n + 1}
    & = & S_n + \frac{1}{n + 1} \cdot S_n + \frac{1}{n + 1} \\
    & = & n + \frac{1}{n + 1} \cdot n + \frac{1}{n + 1} \\
    & = & n + 1
\end{eqnarray*}
%
For the first step, observe that every fraction in $S_{n+1}$ either
does not have $n + 1$ in the denominator (and thus is also in $S_n$),
has $n + 1$ and at least one other number in the denominator (and thus
is counted by the second term), or has only $n + 1$ in the denominator
(and thus is equal to the last term).  The second step uses the
assumption $P(n)$ and the third step is algebra.  This shows that $P(n
+ 1)$ is true.  Thus, $P(n)$ implies $P(n+1)$ for all $n \geq 1$.

By the principle of induction, $P(n)$ is true for all $n \geq 1$.
\end{proof}

An alternative explanation may give more insight into this remarkable
summation formula.  Note that the sum $S_n$ can be obtained by
multiplying out the product below:
%
\[
S_n = \left(1 + \frac{1}{1}\right) \left(1 + \frac{1}{2}\right) \ldots \left(1 + \frac{1}{n}\right) - 1
\]
%
On the other hand, we can evaluate this product directly:
%
\begin{align*}
S_n & = \frac{2}{1} \cdot \frac{3}{2} \cdot \frac{4}{3} \ldots \frac{n+1}{n} - 1 \\
    & = \frac{n+1}{1} - 1 \\
    & = n
\end{align*}
%
On the first line, we rewrite each term.  At the next step, observe
that the 2's cancel, the 3's cancel, and so forth, leaving only an
$n+1$ in the numerator and a 1 in the denominator uncancelled.  The
last step is simplification.}

\end{problem}

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

\begin{problem}[20 points]
Let's consider a variation of the Unstacking game demonstrated in
lecture.  As before, the player is presented with a stack of $n \geq
1$ bricks.  Through a sequence of moves, she must reduce this to $n$
single-brick stacks while scoring as many points as possible.  A move
consists of dividing a single stack of $(a + b)$ bricks (where $a, b >
0$) into two stacks with heights $a$ and $b$.  Suppose that this move
is worth $a + b$ points.  Find the best strategy and use induction to
prove that there is no better strategy.

\solution{Some experimentation suggests that the best strategy is to
remove one block at a time.  This gives a score of:
%
\begin{align*}
n + (n-1) + \ldots + 3 + 2
    & = \frac{n(n+1)}{2} - 1 \\
    & = \frac{(n+2)(n-1)}{2}
\end{align*}
%
Now we must prove that there is no better strategy.

\begin{proof}
We use strong induction.  Let $P(n)$ be the proposition that
unstacking $n$ bricks is worth at most $(n+2)(n-1)/2$ points.

\noindent \textit{Base case:} $P(1)$ is true because the game ends
immediately when there is only 1 brick.  Thus, the player's score is
0, which is the value of $(n+2)(n-1)/2$ when $n = 1$.

\noindent \textit{Inductive step:} Now assume that $P(1), \ldots,
P(n-1)$ are all true in order to prove $P(n)$, where $n \geq 2$.
Suppose the stack of $n$ bricks is split into stacks of height $x$ and
$n - x$, where $0 < x < n$.  The player's best possible score for the
game is then:
%
\[
\underbrace{((n-x) + x)}_{\text{for first move}} +
\underbrace{(x+2)(x-1)/2}_{\text{to unstack $x$ bricks}} +
\underbrace{(n-x+2)(n-x-1)/2}_{\text{to unstack $n - x$ bricks}}
\]
%
Here we are using the assumptions $P(x)$ and $P(n-x)$, which specify
the best possible scores for unstacking $x$ and $n - x$ bricks.  Now
we must choose $x$ to maximize this expression.  The derivative with
respect to $x$ is $2x - n$.  Thus, the expression decreases as $x$
grows from 1 to $n/2$ and then increases symmetrically as $x$ grows
from $n/2$ to $n-1$.  Therefore, the maximum is achieved when $x = 1$
or $x = n - 1$.  In both cases, the expression above is equal to:
%
\[
\frac{(n+2)(n-1)}{2}
\]
%
So we have shown that $P(1)$, \ldots, $P(n-1)$ imply $P(n)$.

Therefore, $P(n)$ is true for all $n \geq 1$ by the strong induction
principle.
\end{proof}

}

\end{problem}

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

\begin{problem}[20 points]
The following problem is fairly tough until you hear a certain
one-word clue.  Then the solution is easy!  Suppose that we have an $n
\times n$ grid, where certain squares are \textit{infected}.  Here is
an example where $n = 6$ and infected squares are marked $\times$.

\[
\begin{array}{|c|c|c|c|c|c|}
\hline
\times& & & &\times& \\ \hline
 &\times& & & & \\ \hline
& &\times&\times& & \\ \hline
& & & & & \\ \hline
& &\times& & & \\ \hline
& & &\times& &\times \\ \hline
\end{array}
\]

\noindent Now the infection begins to spread in discrete
time steps.  Two squares are considered \textit{adjacent} if they
share an edge; thus, each square is adjacent to 2, 3 or 4 others.  A
square is infected in the next time step if either

\begin{itemize}
\item the square was previously infected, or
\item the square is adjacent to \textit{at least two} already-infected squares.
\end{itemize}

In the example, the infection spreads as shown below.
%
\[
\begin{array}{|c|c|c|c|c|c|}
\hline
\times& & & &\times& \\ \hline
 &\times& & & & \\ \hline
& &\times&\times& & \\ \hline
& & & & & \\ \hline
& &\times& & & \\ \hline
& & &\times& &\times \\ \hline
\end{array}
\Rightarrow
\begin{array}{|c|c|c|c|c|c|}
\hline
\times&\times& & &\times& \\ \hline
\times&\times&\times& & & \\ \hline
&\times&\times&\times& & \\ \hline
& &\times& & & \\ \hline
& &\times&\times& & \\ \hline
& &\times&\times&\times&\times \\ \hline
\end{array}
\Rightarrow
\begin{array}{|c|c|c|c|c|c|}
\hline
\times&\times&\times& &\times& \\ \hline
\times&\times&\times&\times& & \\ \hline
\times&\times&\times&\times& & \\ \hline
&\times&\times&\times& & \\ \hline
& &\times&\times&\times& \\ \hline
& &\times&\times&\times&\times \\ \hline
\end{array}
\]
%
Over the next few time-steps, the entire grid becomes infected.

\begin{theorem*}
An $n \times n$ grid can become completely infected only if at least
$n$ squares are initially infected.
\end{theorem*}

Prove this theorem using induction and some additional reasoning.  If
you are stuck, ask your recitation instructor for the one-word clue!

\solution{
\begin{proof}
Define the \term{perimeter} of an infected region to be the number of
edges with infection on exactly one side.  Let $I$ denote the
perimeter of the initially-infected region.

Now we use induction on the number of time steps to prove that the
perimeter of the infected region never increases.  Let $P(nk)$ be the
proposition that after $k$ time steps, the perimeter of the infected
region is at most $I$.

\noindent \textit{Base case:} $P(0)$ is true by definition; the
perimeter of the infected region is at most $I$ after 0 time steps,
because $I$ is defined to be the perimeter of the initially-infected
region.

\noindent \textit{Inductive step:} Now we must show that $P(k)$ implies
$P(k+1)$ for all $k \geq 0$.  So assume that $P(k)$ is true, where $k \geq
0$; that is, the perimeter of the infected region is at most $I$ after $k$
steps.  The perimeter can only change at step $k + 1$ because some squares
are newly infected.  By the rules above, each newly-infected square is
adjacent to at least two previously-infected squares.  Thus, for each
newly-infected square, at least two edges are removed from the perimenter
of the infected region, and at most two edges are added to the perimeter.
Therefore, the perimeter of the infected region can not increase and is at
most $I$ after $k + 1$ steps as well.  This proves that $P(k)$ implies
$P(k+1)$ for all $k \geq 0$.

By the principle of induction, $P(k)$ is true for all $nk \geq 0$.

If an $n \times n$ grid is completely infected, then the perimeter of
the infected region is $4n$.  Thus, the whole grid can become infected
only if the perimeter is initially at least $4n$.  Since each square
has perimeter 4, at least $n$ squares must be infected initially.
\end{proof}}

\end{problem}

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

\end{document}
