\documentclass[11pt,twoside]{article}   
\usepackage{latex-macros/course}

\renewcommand{\reading}{
\href{
http://theory.lcs.mit.edu/classes/6.042/spring02/handouts/lectures/ln2.pdf}
{Week 2 Notes}, Rosen \S 3.2-3.}
\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}

%\hidesolutions
%\showsolutions

\begin{document}
\problemset{2}  

%PROOF from Spring94
%%FALSE PROOF ARITHMETIC, revised ARM 9/3/01

\begin{problem}
\begin{problemparts}
\problempart Rosen, \S 3.2, Exercise 8.
Prove by induction that
\begin{equation}\label{sum3}
1^3 + 2^3 + \ldots + n^3 = \left(\frac{n(n+1)}{2}\right)^2,
\end{equation}
for all $n \in \naturals$.

\solution{

\begin{proof} (by Induction).  The induction hypothesis is $P(n) \eqdef 
\text{ equation~(\ref{sum3})}$.

\textbf{Base Case}: ($n = 1$).  The LHS of~(\ref{sum3}) in this case is
$1^3$ and the RHS is $((1 \cdot 2)/2)^2$.  Since both these quantities
equal 1, equation~(\ref{sum3}) holds, and $P(1)$ is proved.  (Remark:
using the convention that an \emph{empty sum} equals 0, the base case
$n=0$ would be even easier to prove.)

\textbf{Inductive Step}: Let $n$ be any natural number, $\geq 1$, and
assume $P(n)$ in order to prove $P(n+1)$.

So by assumption, we have
\[
1^3 + 2^3 + \ldots + n^3 = \left(\frac{n(n+1)}{2}\right)^2.
\]
Adding $(n+1)^3$ to both sides of this equation, gives
\begin{eqnarray*}
1^3 + 2^3 + \ldots + n^3 + (n+1)^3 
&= & \left(\frac{n(n+1)}{2}\right)^2 + (n+1)^3\\
&= &\frac{n^2(n+1)^2 + 4(n+1)(n+1)^2}{4}\\
&= &\frac{(n^2+4n+4)(n+1)^2}{4}\\
&= &\left(\frac{(n+1)((n+1)+1)}{2}\right)^2.
\end{eqnarray*}
So we have proved $P(n+1)$.
\end{proof}

{\bf Common errors }

A common error is to assume the hypothesis and then to prove it by
reducing both sides of the equation to something that is obviously equal.
This is not a good proof technique.

\begin{eqnarray*}
1^3 + 2^3 + \ldots + n^3 + (n+1)^3  &=& \left(\frac{(n+1)(n+2)}{2}\right)^2 \\
\left(\frac{n(n+1)}{2}\right)^2 + (n+1)^3  &=& \left(\frac{(n+1)(n+2)}{2}\right)
^2 \\      
\frac{n^2(n^2+2n+1)}{4} + n^3 + 3n^2+ 3n +1 &=& \frac{(n^2+3n+2)^2}{4} \\
\frac{(n^4 +2n^3 +n^2) + (4n^3 + 12n^2 + 12n + 4)}{4} &=& 
   \frac { n^4 +3n^3 + 2n^2 + 3n^3 +9n^2 +6n +2n^2 + 6n +4}{4} \\
\frac{n^4 + 6n^3 +13n^2 +12n + 4}{4} &=& 
   \frac{n^4 + 6n^3 +13n^2 +12n + 4}{4} 
\end {eqnarray*}

A technique which is similar but which is not at all correct is to start
with the equation you wanted to prove and then perform the same operations
on both sides of the equation until they're equal.  A simple example is:
\begin{eqnarray*}
n^2+3n+1 &= &n^2+3n+1\\
3n+1 &= & 3n+1\\
1 &= & 1\\
\end{eqnarray*}
This is OK for a quick check, but does not quite work as a proof, since it
is possible to get equality at the end even if the starting sides of the
equation were not equal. For example
\begin{eqnarray*}
n^2+3n+1 &= &2n^2+5n+8\\
0 \cdot (n^2+3n+1) &= & 0 \cdot (2n^2+5n+8)\\
0 & = & 0
\end{eqnarray*}

Remember that in an ideal direct proof, each step should follow from
the previous one, until the final step which is what we want to prove.
}

\problempart Rosen, \S 3.2, Exercise 18.  
\begin{equation}\label{1n2}
\forall\ n>1,\quad 1+\frac{1}{4}+\cdots+\frac{1}{n^2}  <  2-\frac{1}{n}.
\end{equation}

\solution{
\begin{proof}
(by Induction).  The induction hypothesis is $P(n) \eqdef\text{ the
inequality~(\ref{1n2})}$.

\textbf{Base Case}: ($n = 2$).  The LHS of~(\ref{1n2}) in this case is
$1 + 1/4$ and the RHS is $2 - 1/2$.  Since LHS $= 5/4 < 6/4 = 3/2 =$ RHS, 
inequality~(\ref{1n2}) holds, and $P(2)$ is proved.

\textbf{Inductive Step}: Let $n$ be any natural number greater than $1$, and
assume $P(n)$ in order to prove $P(n+1)$.

So by assumption, we have
\[
1+\frac{1}{4}+\cdots+\frac{1}{n^2}  <  2-\frac{1}{n}.
\]
Adding $1/(n+1)^2$ to both sides of this inequality yields
\begin{eqnarray*}
1+\frac{1}{4}+\cdots+\frac{1}{n^2}+\frac{1}{(n+1)^2}& < & 2-\frac{1}{n}
             +\frac{1}{(n+1)^2}\\
& = & 2 - \left(\frac{1}{n} - \frac{1}{(n+1)^2}\right)\\
& = & 2 - \left(\frac{n^2 + 2n + 1-n}{n(n+1)^2}\right)\\
& = & 2 - \frac{n^2 + n}{n(n+1)^2}-\frac{1}{n(n+1)^2}\\
& = & 2 - \frac{1}{n+1} - \frac{1}{n(n+1)^2}\\
& < & 2 - \frac{1}{n+1}.
\end{eqnarray*}
So we have proved $P(n+1)$.
\end{proof}}
\end{problemparts}
\end{problem}

\begin{problem}
  %%False proof that $\forall a \neq 0\ a^n = 1$.
Rosen \S 3.2, Exercise 48.

Find the flaw in the following "proof" that $a^n = 1$ for all nonnegative integers $n$, whenever $a$ is a nonzero real number.

\begin{proof}
(by induction)

\textbf{Base Case:} $a^0 =1$ is true by definition of $a^0$.

\textbf{Inductive Step:} Assume that $a^k = 1$ for all nonnegative integers $k$ with $k \leq n$. Then note that
\[
a^{n+1} = \frac{a^n \cdot a^n}{a^{n-1}} = \frac{1 \cdot 1}{1} = 1.
\]
\end{proof}
\solution{
The flaw comes in the inductive step, where we implicitly assume
$n\geq 1$ in order to talk about $a^{n-1}$ in the denominator
(otherwise the exponent is not a nonnegative integer, so we cannot
apply the inductive hypothesis).  We checked the base case only for
$n=0$, so we are not justified in assuming that $n\geq 1$ when we try
to prove the statement for $n+1$ in the inductive step.  Indeed, the
proposition first breaks precisely at $n=1$.

}
\end{problem}

\begin{problem} %source: spring00 ps2

% multi base cases, strong induction
One plan considered by the 6.042 staff, involved requiring students to
work in subgroups of either exactly 4 or exactly 7 students.  We abandoned
this plan when we realized that groups of 9 and 10 cannot be split up in
this way.

\begin{problemparts} 

\problempart \label{k} What is the smallest number, $k$, such that all
tutorials of $k$ or more students can be split into teams of 4 and 7?
Prove that $k-1$ students \emph{cannot} be split in this way.

\solution{The smallest number $k$ such that all tutorials of $k$ or more
students \emph{can} be split into teams of 4 and 7 is $18$.

A tutorial of size $17$ \emph{cannot} be split into teams of 4 and 7.  In
particular, a tutorial of size $17$ can contain at most 2 groups of 7.
Consider the various possible splits of the tutorial:
\begin{enumerate}
\item no groups of 7:
the only other group size is 4.  We cannot split the tutorial of 17,
since it is not divisible by 4; 
\item one group of 7: again, the remaining
number, 10, of students is not divisible by 4; 
\item two groups of 7: the
remaining 3 students are not a group of 4 or 7.
\item three or more groups of 7: clearly, this accounts for
  $21>17$ students and is inadmissible.
\end{enumerate}
}


\problempart Now complete the proof of your answer to part~(\textbf{a}).
Namely, prove (by induction) that all tutorials of $k$ or more students
\emph{can} be split into teams of size 4 and 7.

\solution{
\begin{proof} (strong induction).  Define $P(n)$ to be the predicate that
a tutorial of size $n$ can be split into groups of size 4 and 7.  Being
``split'' really means that $n = 4x + 7y$ for some natural numbers $x,y$.
So we can give a completely precise definition:
\[
P(n) \eqdef\quad n \geq 18 \implies \exists x, y \in \naturals\ [n = 4x +
7y].
\]
We must show that $P(n)$ holds for all $n \in \naturals$.  By strong
induction, we consider $n \geq 18$ and assume the strong induction
hypothesis
\begin{equation}\label{SIH}
\forall m\ [18 \leq m < n \implies \exists x_m, y_m \in \naturals\ (m =
4x_m + 7y_m) ].
\end{equation}
in order to prove that $P(n)$ holds.

The proof divides into cases

\textbf{Case 0:} ($n < 18$) $P(n)$ holds trivially since the hypothesis $n
\geq 18$ is false.

\textbf{Case 1:} ($n=18$).  $18 = 4 \cdot 1 + 7 \cdot 2$, so $P(18)$ is
proved.

\textbf{Case 2:} ($n=19$).  $19 = 4 \cdot 3 + 7 \cdot 1$, so $P(19)$ is
proved.

\textbf{Case 3:} ($n=20$).  $20 = 4 \cdot 5 + 7 \cdot 0$, so $P(20)$ is
proved.

\textbf{Case 4:} ($n=21$).  $21 = 4 \cdot 0 + 7 \cdot 3$, so $P(21)$ is
proved.

Notice that we proved Cases 0--4, without needing to use the induction
hypothesis~(\ref{SIH}).

\textbf{Case 5:} ($n \geq 22$).  In this case, letting $m \eqdef n - 4$,
we have $18 \leq m < n$, so by induction hypothesis~(\ref{SIH}), we
conclude that there are natural numbers $x_m,y_m$ such that
\[
m = 4x_m + 7y_m.
\]
So
\begin{equation}\label{m}
n = m + 4 = 4(x_m+1) + 7y_m.
\end{equation}
Letting $x \eqdef x_m+1$ and $y \eqdef y_m$ in~(\ref{m}) implies
\[
n = 4x + 7y,
\]
which proves $P(n)$.
\end{proof}}

\end{problemparts}
\end{problem}


%%F01 Q1
\begin{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
Figure~\ref{fig:squares}~(a).  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
Figure~\ref{fig:squares}~(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 Figure~\ref{fig:squares}~(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 the length of the
periphery is always even, no matter how many squares Theory Pig places or
how he arranges them.

\begin{figure}[htbp]
\centering
\includegraphics[width=4in]{figures/f98ps2}
\caption{Some shapes that Theory Pig created.} \label{fig:squares}
\end{figure}

%\emph{(TO HARD TO GRADE?)}

\solution{
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)$-th 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{problem}

%Fall 99
%problem set 2, problem 7

\begin{problem}\label{mx+ny}
Let $m$ be a natural number and $n$ be a positive integer.  Prove \emph{by
induction} that there are integers $x,y$ such that $mx+ny= \gcd(m,n)$.
You may use the fact that
\begin{equation}\label{241}
\gcd(m,n) = \gcd(m,r)
\end{equation}
where $r$ is the remainder of $n$ divided by $m$ (\cf Rosen, Lemma 2.4.1).

\begin{quote}
\textbf{IMPORTANT NOTE:} While correct above, the definition of $r$ was a typo in the original problem set. Rosen, Lemma 2.4.1 states $\gcd(m, n) = \gcd(m, n\!\mod m)$ which is different from $\gcd(m,n) = \gcd(n, m\!\mod n)$.  The first statement is true, while the second is \textbf{NOT}.  This only requires a small change in the overall proof form to correct, which is the assumption that $m$ can be less than $n$ without  loss of generality. 
\end{quote}

\solution{
\begin{proof}
Define
\[
P(n) \eqdef\quad n > 0 \implies \forall m \in \naturals\, \exists x,y\in \integers\
[mx+ny= \gcd(m,n)].
\]
We want to prove that $P(n)$ holds for all $n \in \naturals$.  We do this
by strong induction.

Namely, we assume that whenever $k$ is a positive integer \emph{less than}
$n$ we can express $\gcd(k,m)$ as an linear integer combination of $k$ and
$m$, for any natural number, $m$.  Using this, we show how to express $n$
in the same way.

Before we do the official proof, it's worth describing the problem from a
Computer Science view.  We would like to define a pair of recursive
procedures \texttt{findx} and \texttt{findy}, each with two parameters,
such that \texttt{findx} applied to integers $m$ and $n$ will return an
integer, $x$, and likewise \texttt{findy} applied to integers $m$ and $n$
will return an integer, $y$, such that
\begin{equation}\label{eqmn}
mx+ny= \gcd(m,n),
\end{equation}
providing that $m \geq 0$ and $n > 0$.  Evaluation of \texttt{findx} and
\texttt{findy} applied to integers $m$ and $n$ may make direct recursive
calls of both \texttt{findx} and \texttt{findy} applied to integers $m$
and $r$ for $0 < r <n$.  As you read the following proof, see if you can
extract the definitions of these \texttt{findx} and \texttt{findy}
procedures.

Now for the official proof, we consider any $n \in \naturals$ and assume
the strong induction hypothesis
\begin{equation}\label{SIH2}
\forall k\ 0 < k < n \implies \forall m\, \exists
x_k,y_k\in \integers\ [mx_k+ky_k= \gcd(m,k)].
\end{equation}
in order to prove that $P(n)$ holds.

\textbf{Case 0:} ($n=0$).  $P(0)$ holds trivially.

Now we can prove $P(n)$ for $n>0$ by showing how, given any $m \in
\naturals$, to find integers $x,y$ such that equation~(\ref{eqmn}) holds.
This proof divides into cases:

\textbf{Case 1:} ($m = 0$).  Then $\gcd(m,n) = n$ so we can choose $x = 0$
and $y = 1$ to satisfy~(\ref{eqmn}).

\textbf{Case 2:} ($m \divides n$).  Then $\gcd(m,n) = n$ so we can choose $x = 1$
and $y = 0$ to satisfy~(\ref{eqmn}).

\textbf{Case 3:} $m \neq 0$ and $r>0$ where $r$ is the remainder of $n$
divided by $m$.  Assume without loss of generality that $m \leq n$ (we can do this because we have already taken care of the case where $m=0$ and otherwise we can always relabel $m$ to be the smaller of the two).
Now $1 \leq r <m \leq n$, so by the induction
hypothesis~(\ref{SIH2}) applied with $k=r$, we conclude that there are
natural numbers $x_r,y_r$ such that
\begin{equation}\label{xr}
mx_r+ry_r= \gcd(m,r).
\end{equation}

Now $r=m-qn$ where $q$ is the quotient of $m$ divided by $n$, so
substituting into~(\ref{xr}), yields
\[
mx_r+(m-qn)y_r= \gcd(m,r).
\]
Simplifying the lefthand side and using~(\ref{241}), we conclude
\[
m(x_r+y_r)+n(-qy_r)= \gcd(m,n).
\]
So we can choose $x = (x_r+y_r)$ and $y = -qy_r$ to satisfy~(\ref{eqmn}).

Since Cases 1--3 exhaust the possibilities for $m$, we conclude
that~(\ref{eqmn}) holds for all $m$, completing the proof of $P(n)$.
\end{proof}
}

\end{problem}

\begin{problem}
Let $m,n$ be integers, and assume at least one of $m$ and $n$ is nonzero.
Define a set of integers, $L_{m,n}$, recursively as follows:
\begin{itemize}
\item \textbf{base cases}: $m,n,-m,-n \in L_{m,n}$.
\item \textbf{recursive step}: If $k,l \in L_{m,n}$, then $k+l \in L_{m,n}$.
\end{itemize}

Do the following parts without appeal to~Problem~\ref{mx+ny}.

\begin{problemparts}

\problempart \label{Lmx+ny}  Show that
\[
L_{m,n} = \set{mx+ny \suchthat x,y \in \integers}.
\]

\solution{
We need to prove two statements:  firstly, that every number of the
form $mx+ny$ is in $L_{m,n}$; secondly, that every member of $L_{m,n}$
has this form.

\begin{itemize}
\item
To show that $\forall x, y\in \integers, mx+ny\in L_{m,n}$: we do this with two induction
proof steps.  Note that we can only run induction on the \emph{nonnegative}
integers, so we extend our proof slightly.
\begin{itemize}
\item
\textbf{Induction Hypothesis}:  
\begin{equation}\label{indhyp1}
P(x)\eqdef\set{mx, -mx}\subset L_{m,n}
\end{equation}
\textbf{Base case}: $m\cdot 0=m+(-m)\in L_{m,n}$

\textbf{Inductive step}: If $mx$ and $-mx$ are in $L_{m,n}$ then so
are $m(x+1)=mx+m$ and $-m(x+1)=-mx+(-m)$.

So equation~\ref{indhyp1} holds for all nonnegative integers $x$.
\item
\textbf{Induction Hypothesis}:  
\begin{equation}\label{indhyp2}
Q(y)\eqdef\forall x\in\integers,\set{mx+ny, mx-ny}\subset L_{m,n}
\end{equation}
\textbf{Base case}: $mx+n\cdot 0=mx\in L_{m,n}$, from
eqn.~\ref{indhyp1}, this holds for all integers $x$.

\textbf{Inductive step}: If $mx+ny$ and $mx-ny$ are in $L_{m,n}$ then so
are $mx+n(y+1)=mx+ny+n$ and $mx-n(y+1)=mx-ny+(-n)$.

So equation~\ref{indhyp2} holds for all nonnegative integers $y$.
This completes the proof.
\end{itemize}
\item
To show that every member of $L_{m,n}$ has the form $mx+ny$: note that
it's true for the base cases $m, -m, n, -n$ because $m=m\cdot 1+n\cdot
0$, etc.  Now let's look at our recursive step:  suppose true for $k,
l$.  Numerically
\begin{eqnarray*}
k&=&mx_k+ny_k\\
l&=&mx_l+ny_l\\
\Rightarrow k+l&=&mx_k+ny_k+mx_l+ny_l=m(x_k+x_l)+n(y_k+y_l)
\end{eqnarray*}
In other words, the newly added element also has the requisite form.
It follows inductively that all elements of $L_{m,n}$
have the form $mx+ny$ for some integers $x$ and $y$.
\end{itemize}
}

\problempart \label{common}

Prove that any common divisor of $m$ and $n$ also divides every member of
$L_{m,n}$.

\solution{ If $k \in L_{m,n}$, then by part~(\ref{Lmx+ny}), $k = mx+ny$.
Now if $d$ is a common divisor of $m$ and $n$, then it divides $mx$ and
$ny$, and hence divides their sum $mx+ny$.  So $d$ also divides $k$.

\iffalse

\begin{proof} (by Induction)
The induction hypothesis is
\[
P(k) \eqdef\quad k \in L_{m,n} \implies \forall l\ (l \divides m \land l \divides
n) \implies l \divides k.
\]

\textbf{Base case}: $P(m)$ is immediate, since any common divisor of $m$ and
$n$ certainly divides $m$.  Likewise for $P(n)$.

\textbf{Recursive case}: Suppose $k,l \in L_{m,n}$.  Assume $P(k)$ and
$P(l)$, in order to prove $P(k+l)$.

So suppose $j$ is a common divisor of $m$ and $n$.  Then $j \divides k$ by
hypothesis $P(k)$ and $j \divides l$ by hypothesis $P(l)$.  That is, $k = pj$
and $l= qj$ for some $p,q \in \integers$.  Hence $k+l = pj+qj = j(p+q)$.
So we have $j \divides k+l$, and we conclude that $P(k+l)$ holds.
\end{proof}
\fi

}


\problempart

Show that if $k,l \in L_{m,n}$ then the remainder of $k$ divided by $l$ is
in $L_{m,n}$.

\solution{Say $r$ is the remainder of $k$ divided by $l$.  That is, $0
\leq r < l$ and $k = ql+r$ for some $q \in \integers$.

Since $k,l \in L_{m,n}$ we have as in part~(\ref{Lmx+ny}) that $k+ (-q)l
\in L_{m,n}$.  That is, $r \in L_{m,n}$.}

\problempart \label{g}

Show that there is a positive integer $g \in L_{m,n}$ which divides every
member of $L_{m,n}$.  \hint The least positive integer in $L_{m,n}$.

\solution{At least one of the integers $m, -m, n, -n \in L_{m,n}$ must be
positive.  Hence by the Least Number Principle, there is a least positive
integer $g \in L_{m,n}$.

Suppose $k \in L_{m,n}$.  We must show that $g \divides k$.

We prove this by contradiction: if $g$ does not divide $k$, then the
remainder of $k$ divided by $g$ is a positive number smaller than $g$,
which by the previous part is in $L_{m,n}$, contradicting the fact that
$g$ is the smallest such integer.
}

\problempart Conclude that $\gcd(m,n) = mx+ny$ for some $x,y \in \integers$.

\solution{From part~(\ref{g}), we have a positive integer $g \in L_{m,n}$
that divides every element of $L_{m,n}$.  By part~(\ref{Lmx+ny}), $g
=mx+ny$ for some $x,y \in \integers$.  Also, $g$ is a common divisor of
$m,n$, since $m,n \in L_{m,n}$.  But by part~(\ref{common}), any common
divisor of $m$ and $n$ divides $g$.  Hence, $g = \gcd(m,n)$.}


\end{problemparts}

\end{problem}

\end{document}                            

