\documentclass[12pt]{article}   
\usepackage{latex-macros/course}% !! Use the macros

%\backwardscompatibility        % !! use for backwards compatibility
%\showsolutions                 % !! use to force solutions & skip query
%\hidesolutions                 % !! use to force no solutions & skip
                                % query 

\renewcommand{\reading}{Course notes on induction.}

\begin{document}
\problemset{2}                  % !! Start the problem set with its number

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

\begin{problem}
Use induction to prove that the following inequality holds for all
integers $n \geq 1$.

\begin{eqnarray*}
\frac{1 \cdot 3 \cdot 5 \cdots (2n - 1)}{2 \cdot 4 \cdot 6 \cdots (2n)}
& \geq & \frac{1}{2n}
\end{eqnarray*}

\solution{We use induction.  Let $P(n)$ be the proposition that:

\begin{eqnarray*}
\frac{1 \cdot 3 \cdot 5 \cdots (2n - 1)}{2 \cdot 4 \cdot 6 \cdots (2n)}
& \geq & \frac{1}{2n}
\end{eqnarray*}

First, we prove $P(1)$.  In this case, both side of the inequality are
equal to $1/2$, and so the inequality holds.  Next, for each $n \geq
1$, we must show that $P(n)$ implies $P(n+1)$.  Assume that $P(n)$ is
true.  Then we can reason as follows:

\begin{eqnarray*}
\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}{2(n+1)}
\end{eqnarray*}

\noindent The first step uses the induction hypothesis, $P(n)$.  The
second step uses the fact that $(2n+1) / (2n) > 1$ for all $n \geq 1$.
Therefore, by induction, the proposition $P(n)$ is true for all $n
\geq 1$, and the claim is proved.
}

\end{problem}

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

\begin{problem}
Let $H_n$ denote the {\em $n$-th harmonic sum}, which is defined by:

\begin{eqnarray*}
H_n & = & \sum_{k = 1}^n \frac{1}{k}
\end{eqnarray*}

Harmonic sums come up often.  You'll see them again later in 6.042 and
also in 6.046.

\begin{claim}
For all $m \geq 0$,

\begin{eqnarray*}
H_{2^m} & \geq & 1 + m / 2
\end{eqnarray*}
\end{claim}

\bparts

\ppart The {\em next} problem part will ask you to prove this claim by
induction.  To make this easier, three steps that you may find useful
in your proof are listed below.  Provide a one sentence justification
for each of these steps.

\begin{eqnarray*}
H_{2^{m+1}}
    & = & \sum_{k = 1}^{2^{m+1}} \frac{1}{k} \\
    & = & H_{2^m} + \sum_{k = 2^m + 1}^{2^{m+1}} \frac{1}{k} \\
    & \geq & H_{2^m} + 2^m \cdot \frac{1}{2^{m+1}} \\
\end{eqnarray*}

\solution{The first step uses the definition of $H_{2^{m+1}}$.  The
second step uses the fact that the first $2^m$ terms of the sum are
equal to all $2^m$ terms of $H_{2^m}$.  The third step uses the fact
that a sum is lower bounded by the number of terms times the smallest
term.}

\ppart Prove the claim by induction.  (See?  We {\em told} you this
was going to happen\ldots)

\solution{We prove the claim by induction.  Let $P(m)$ be the
proposition that $H_{2^m} \geq 1 + m / 2$.  First, note that $P(0)$ is
true, because:

\[
H_{2^0} = H_1 = 1 \geq 1 + 0 / 2
\]

Next, we must show that $P(m)$ implies $P(m + 1)$ for all $m \geq 0$.
We assume that $P(m)$ is true and reason as follows:

\begin{eqnarray*}
H_{2^{m+1}}
    & = & \sum_{k = 1}^{2^{m+1}} \frac{1}{k} \\
    & = & H_{2^m} + \sum_{k = 2^m + 1}^{2^{m+1}} \frac{1}{k} \\
    & \geq & H_{2^m} + 2^m \cdot \frac{1}{2^{m+1}} \\
    & \geq & (1 + m / 2) + 1 / 2\\
    & = & 1 + (m + 1) / 2
\end{eqnarray*}

The first step uses the definition of $H_{2^{m+1}}$.  The second step
uses the fact that the first $2^m$ terms of the sum are equal to all
$2^m$ terms of $H_{2^m}$.  The third step uses the fact that a sum is
lower bounded by the number of terms times the smallest term.  The
fourth step uses our assumption $P(m)$ and simplification.  The last
step uses only algebra.  This shows that $P(m + 1)$ is true, and so
$P(m)$ is true for all $m \geq 0$ by induction.}

\ppart Show that this implies $H_n \geq 1 + \frac{1}{2} \log_2 n$ when
$n$ is a power of 2.

\solution{This inequality follows from substituting $n = \log_2 m$
into the claim.}

\eparts

\end{problem}

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

\begin{problem}
This term in 6.042, we're constantly trying to divide a class of $n$
students into groups of either 4 or 5 students.  

\bparts

\ppart Let's try to use strong induction prove that a class with $n
\geq 8$ students can be divided into groups of 4 or 5.

\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 4 or 5.

First, we prove that $P(n)$ is true for $n = 8$, 9, or 10 by showing
how to break classes of these sizes into groups of 4 or 5 students:

\begin{eqnarray*}
8 & = & 4 + 4 \\
9 & = & 4 + 5 \\
10 & = & 5 + 5
\end{eqnarray*}

Next, we must show that $P(8), \ldots, P(n)$ imply $P(n + 1)$ for all
$n \geq 10$.  Thus, we assume that $P(8), \ldots, P(n)$ are all true
and show how to divide up a class of $n + 1$ students into groups of 4
or 5.  We first form one group of 4 students.  Then we can divide the
remaining $n - 3$ students into groups of 4 or 5 by the assumption
$P(n - 3)$.  This proves $P(n + 1)$, and so the claim holds by
induction.
\end{proof}

This proof contains a critical logical error.  (In fact, the claim is
false!)  Identify the first sentence in the proof that does not follow
and explain what went wrong.

\solution{The first error is in the sentence:

\begin{quotation}
\noindent Then we can divide the remaining $n - 3$ students into
groups of 4 or 5 by the assumption $P(n - 3)$.
\end{quotation}

If $n = 10$, then $P(n - 3) = P(7)$, which is not among our
assumptions $P(8), \ldots, P(n)$.  In this case, $P(n + 1) = P(11)$ is
actually false.}

\ppart Provide a correct strong induction proof that a class with $n
\geq 12$ students can be divided into groups of 4 or 5.

\solution{The proof is by strong induction.  Let $P(n)$ be the
proposition that a recitation with $n$ students can be divided into
teams of 4 or 5.

First, we prove that $P(n)$ is true for $n = 12$, 13, 14, and 15 by
showing how to break classes of these sizes into groups of 4 or 5
students:

\begin{eqnarray*}
12 & = & 4 + 4 + 4 \\
13 & = & 4 + 4 + 5 \\
14 & = & 4 + 5 + 5 \\
15 & = & 5 + 5 + 5
\end{eqnarray*}

Next, we must show that $P(12), \ldots, P(n)$ imply $P(n + 1)$ for all
$n \geq 15$.  Thus, we assume that $P(12), \ldots, P(n)$ are all true
and show how to divide up a class of $n + 1$ students.  We first form
one group of 4 students.  Then we can divide the remaining $n - 3$
students into groups of 4 or 5 by the assumption $P(n - 3)$.  (Note
that $n \geq 15$ and so $n - 3 \geq 12$; thus, $P(n - 3)$ is among our
assumptions $P(12), \ldots, P(n)$.)  This proves $P(n + 1)$, and so the
claim holds by induction.}

\eparts

\end{problem}

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

\begin{problem}
When you use long division to divide an integer $n$ by a positive
integer $d$, you get a quotient $q$ and a small remainder $r$.  The
theorem below states this formally:

\begin{theorem}[Division Algorithm]
Let $n$ be an integer, and let $d$ be a positive integer.  Then there
exist integers $q$ and $r$ such that

\begin{eqnarray*}
n & = & q \cdot d + r
\end{eqnarray*}

\noindent where $0 \leq r < d$.
\end{theorem}

Really, this is a theorem {\em about} long division, but traditionally
the theorem itself is called the {\em division algorithm}.  The
division algorithm is usually proved using the least-number principle.
Can you devise such a proof?

\solution{Let $S$ be the set of all ordered pairs $(q, r)$ such that
$r \geq 0$ which satisfy the equation above. Assume the set is
nonempty (we show this below).  By the least-number principle, we know
some element in this set must have the smallest $r$. For this element
$(q,r)$, we must have $0 \leq r < d$; otherwise, $(q + 1, r - d)$
would be an element as well.

To show the set is $S$ nonempty, consider the following cases. If $n
\geq 0$, $(0,n)$ is an element. If $n < 0$, then $(nd, -n(d-1))$ is an
element.  Note that because $n < 0$ and $d > 1$, the quantity $-n(d-1)
\geq 0$.}

\end{problem}

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

\begin{problem}
\begin{claim}
If a collection of positive integers (not necessarily distinct) has
sum $n \geq 1$, then the collection has product at most $3^{n/3}$.
\end{claim}

For example, the collection 2, 2, 3, 4, 4, 7 has the sum:

\begin{eqnarray*}
2 + 2 + 3 + 4 + 4 + 7 & = & 22
\end{eqnarray*}

On the other hand, the product is:

\begin{eqnarray*}
2 \cdot 2 \cdot 3 \cdot 4 \cdot 4 \cdot 7
    & = & 1344 \\
    & \leq & 3^{22/3} \\
    & \approx & 3154.2
\end{eqnarray*}

\bparts

\ppart Use strong induction to prove that $n \leq 3^{n/3}$ for every
integer $n \geq 0$.

\solution{The proof is by strong induction.  Let $P(n)$ be the
proposition that $n \leq 3^{n/3}$.  First, we show that $P(0)$,
$P(1)$, $P(2)$, $P(3)$, and $P(4)$ are true:

\begin{eqnarray*}
0^3 \leq 3^0 & \rightarrow & 0 \leq 3^{0/3} \\
1^3 \leq 3^1 & \rightarrow & 1 \leq 3^{1/3} \\
2^3 \leq 3^2 & \rightarrow & 2 \leq 3^{2/3} \\
3^3 \leq 3^3 & \rightarrow & 3 \leq 3^{3/3} \\
4^3 \leq 3^4 & \rightarrow & 4 \leq 3^{4/3} \\
\end{eqnarray*}

Each implication follows by taking cube roots.  Next, we show that
$P(0), \ldots, P(n)$ imply $P(n + 1)$ for all $n \geq 4$.  Thus, we
assume that $P(0), \ldots, P(n)$ are all true and reason as follows:

\begin{eqnarray*}
3^{(n + 1)/3}
    & = & 3 \cdot 3^{(n-2)/3} \\
    & \geq & 3 \cdot (n - 2) \\
    & \geq & n + 1 \hspace{1in} \text{(for all $n \geq 7/2$)}
\end{eqnarray*}

The first step is algebra.  The second step uses our assumption $P(n -
2)$.  The third step is a linear inequality that holds for all $n \geq
7/2$.  (This forced us to deal individually with the cases $P(3)$ and
$P(4)$, above.) Therefore, $P(n + 1)$ is true, and so $P(n)$ is true
for all $n \geq 0$ by induction.}

\ppart Prove the claim using induction or strong induction.  (You may
find it easier to use induction on the {\em number of positive
integers in the collection} rather than induction on the sum $n$.)

\solution{We use induction on the size of the collection.  Let $P(k)$
be the proposition that every collection of $k$ positive integers with
sum $n$ has product at most $3^{n/3}$.  First, note that $P(1)$ is
true by the preceding problem part.

Next, we must show that $P(k)$ implies $P(k + 1)$ for all $k \geq 1$.
So assume that $P(k)$ is true, and let $x_1, \ldots, x_{k+1}$ be a
collection of positive integers with sum $n$.  Then we can reason as
follows:

\begin{eqnarray*}
x_1 \cdot x_2 \cdots x_k \cdot x_{k+1}
    & \leq & 3^{(n - x_{k+1}) / 3} \cdot x_{k+1} \\
    & \leq & 3^{(n - x_{k+1}) / 3} \cdot 3^{x_{k+1} / 3} \\
    & = & 3^{n / 3}
\end{eqnarray*}

The first step uses the assumption $P(k)$, the second uses the
preceding problem part, and the last step is algebra.  This shows that
$P(k + 1)$ is true, and so the claim holds by induction.
}

\eparts

\end{problem}

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

\end{document}
