\documentclass[11pt,twoside]{article}
\usepackage{amsmath}
%\usepackage{graphics}
\input{/pub/www/classes/6.042/fall99/inputs/macros-course}

%\newcommand{\solution}[1]{}
\newcommand{\solution}[1]{\bigskip {\bf Solution:}\\ #1\bigskip}
\newcommand{\spac}{\vspace{4mm}}
\newcommand{\hspac}{\vspace{2mm}}

\begin{document}
\psol{2}{September 24, 1999 (typo corrected 9/28)}

%\begin{center}\large DRAFT 6:50pm 9/24\end{center}

\begin{problems}

\problem For each of the functions below, determine whether the function
is injective, whether it is surjective, and whether it is bijective.  No
proofs are required.

\begin{problemparts}
\problempart The function $f : \reals \to \reals$ defined by
$f(x)=x^2$.

\solution{$f(r) = f(-r)$ so not injective.  $f(r) \geq 0$ so not
surjective.}

\problempart The function $f : \reals^+ \to \reals^+$
defined by $f(x)=x^2$.  (Here $\reals^+$ denotes the set of
positive real numbers.)

\solution{A bijection, because every positive real has a unique positive
square root.}

\problempart The function $f : \reals \to \reals$ defined by
$f(x)=x^3$.

\solution{$f$ is an increasing function, namely $x<y$ implies $f(x) <f(y)$
so it is an injection.  It also takes on all real values, that is, it is a
surjection too.  So it is a bijection.}

\problempart The function $f : \reals \to \reals$ defined by
$f(x)=xe^x$.

\solution{$f'(x) = e^x + x e^x = e^x(1 + x)$, so $f$ has a minimum at $x
=1$ which implies it is neither an injection nor a surjection.}

\problempart The function $f : \reals \times \reals \to \reals$ defined
by $f(x,y) = xy$.

\solution{Not an injection since $f(0,y)=f(0,z)$ for all $y,z$.  It is a
surjection, since $r = f(1, r)$ for all $r$.}

\end{problemparts}

\problem Prove that there is a bijection between $\integers$ and
$\naturals$.

\solution{Let $f(0) = 0, f(1) = 2, f(2) = 4, f(3) = 6, \dots$ and
$f(-1) = 1, f(-2) = 3, f(-3) = 5, \dots$.  That is, 
\[f(k) ::= \left\{\begin{array}{ll}
             2k & \mbox{ if } k \geq 0,\\
             -2k - 1 & \mbox{ if } k < 0.
                    \end{array}
           \right.
\]
}

\problem Let $f: B \to C$ and $g: A \to B$ so $f \circ g : A
\to C$.  Given that $f \circ g$ is one-to-one, prove or give a
counterexample:

\begin{problemparts}

\problempart $g$ is an injection.

\solution{It is.
\begin{proof}
Assume for the purpose of contradiction that $g$ is not an one-to-one.
Then there exist elements $a_1, a_2 \in A$, such that $g(a_1) = g(a_2)$.
This implies that $f(g(a_1)) = f(g(a_2))$.  Therefore, $f \circ g$ is not
one-to-one, a contradiction.
\end{proof}}

\problempart $f$ is an injection.

\solution{It need not be.  For example, let $A::=\set{1,2}, C::=
B::=\set{1,2,3}, C ::= A$, and define $g(n) ::= n$, $f(1)::=1$, $f(2) = f(3)
::= 2$.}

\end{problemparts}


\problem  \textbf{Modular Arithmetic}

Do the following problems from the Rosen textbook:

\bparts

\ppart \S 2.3, Exercise 38.

\solution{From $a \equiv b \pmod{m}$ we know that $b = a + s m$ 
for some integer $s$. Now if $d$ is a common divisor of $a$ and $m$, then
it divides the right-hand side of this equation, so it also divides $b$.
We can rewrite the equation as $a = b - s m$, and then by similar reasoning,
we see that every common divisor of $b$ and $m$ is also a divisor of $a$. This
shows that the set of common divisors of $a$ and $m$ is equal to the set of
common divisors of $b$ and $m$, so certainly gcd$(a,m)$ = gcd$(b,m)$.
}

\ppart \S 2.4 Exercise 16.

\solution{The key fact here is that $10 \equiv -1 \pmod{11}$, and so 
$10^k\equiv (-1)^k \pmod{11}$. Thus $10^k$ is congruent to $1$ if $k$ is
even and to $-1$ if $k$ is odd. Let the decimal expansion of the integer $a$
be given by $(a_{n-1}a_{n-2}\ldots a_3a_2a_1a_0)_{10}$. Thus 
$a=10^{n-1}a_{n-1}+10^{n-2}a_{n-2}+\ldots+10 a_1+a_0$. Since 
$10^k\equiv (-1)^k \pmod{11}$, we have $a\equiv \pm a_{n-1} \mp a_{n-2}+
\ldots - a_3 + a_2 - a_1 + a_0 \pmod{11}$, where signs alternate and depend
on the parity of $n$. Therefore $a\equiv 0 \pmod{11}$ if and only if 
$(a_0+a_2+a_4+\ldots)-(a_1+a_3+a_5+\ldots)$, which we obtain by collecting 
the odd and even indexed terms, is congruent to $0 \pmod{11}$.  Since being 
divisible by $11$ is being the same as being congruent to $0 \mod 11$, we
have proved that a positive integer is divisible by $11$ if and only if the 
sum of its decimal digits  in even-numbered positions minus the sum of its 
decimal digits in odd-numbered positions is divisible by $11$.
}

\eparts

\problem \textbf{Induction}

Do the following problems from Rosen :

\bparts

\ppart \S 3.2, Exercise 40.

\solution{We prove this by induction on $k$. The base case $k=0$ is the 
trivial statement that $1\equiv 1 \pmod{m}$. Suppose that the statement
is true for $k$. We must show it for $k+1$. So let $a\equiv b \pmod{m}$. By
the inductive hypothesis we know that $a^k\equiv b^k \pmod{m}$. Then we
apply Theorem 7 from Section 2.3 to conclude that $a\cdot a^k\equiv b\cdot 
b^k \pmod{m}$, which by definition says that $a^{k+1}\equiv b^{k+1} \pmod{m}$,
as desired.
}

\ppart \S 3.3, Exercise 22(c).

\solution{There are several ways to do this.  One that is suggested by
Horner's method is as follows.  We will assume that the variable for these
polynomials is the letter $x$.  All integers are in $S$ (this base case
gives us all the constant polynomials); if $p(x)\in S$ and $n$ is any
integer, then $x p(x)+n$ is in $S$.  Another method constructs the
polynomials term by term.  Its base case is to let $0$ be in $S$; and its
inductive step is to say that if $p(x)\in S$, $c$ is an integer, and $n$
is a nonnegative integer, then $p(x)+c x^n$ is in $S$.
}

\eparts


\problem \textbf{Modular Arithmetic}

Let $p(n)$ be polynomial of positive degree $d$ with integer
coefficients.  That is
\[
p(n) = a_dx^d + a_{d-1}x^{d-1} + \dots + a_1x + a_0 = \sum_{i=0}^d a_ix^i.
\]
where $d>0$, $a_d \neq 0$, and $a_i \in \integers$ for $0 \leq i \leq d$.

\bparts

\ppart

Prove that
\[
\mbox{if } m \equiv n \pmod{k}, \mbox{ then } p(m) \equiv p(n) \pmod{k},
\]
for all $m,n, k \in \integers$, $k > 1$.

\solution{By structural induction on the recursive definition of
polynomial in the previous problem.  The induction hypothesis
\[
P(p) ::= \forall m,n, k \in \integers((k > 1 \wedge m \equiv n \pmod{k})
 \implies  p(m) \equiv p(n) \pmod{k}).
\]

The base case: $p$ is a
constant polynomial.  In this case $p(m) = p(n)$ and so trivially $p(m) \equiv p(n)
\pmod{k}$, proving $P(p)$.

Induction step: suppose $p(x) = xq(x) + i$ for some $i \in \integers$ and
polynomial $q$ such that $P(q)$ holds.  We must prove $P(p)$.

So suppose $k > 1$ and $m \equiv n \pmod{k}$.  Then also $q(m) \equiv q(n)
\pmod{k}$ by induction hypothesis.   So $mq(m) \equiv nq(n) \pmod{k}$, and then
$mq(m) + i \equiv nq(n) + i \pmod{k} $.  But the lefthand side of this last
equation is $p(m)$ and the righthand side is $p(n)$, proving $P(p)$.
}

\ppart

Prove that the range of $p$ must contain an infinite number of nonprimes.

\solution{Since $d>0$ and $a_d \neq 0$, there must be an $n_0 \in
\naturals$ such that $p(n_0) = k > 1$.  So $p(n_0) \equiv 0  \pmod{k}$.
Therefore $p(n) \equiv 0 \pmod{k}$ whenever $n \equiv n_0  \pmod{k}$.  Since
there are larger and larger such $n$, there are larger and larger $\abs{p(n)}$
which are divisible by $k$ and hence are not prime.}

\ppart (Optional, best done with a Scheme program.)
Suppose $p(n) = n^2 - n + 41$.

Find the smallest natural number $n$ such that $p(n)$ is \emph{not} prime.

\solution{$n=41$.  Clearly $p(41)= 41^2 - 41 + 41$ is divisible by 41, so
is not prime.  Successive values $p(0)=41, p(1)=41, p(2)=43, p(3)=47,
\dots, p(40)= 1601$ all turn out to be prime.}

\eparts


\problem \textbf{Induction}\label{ax+by:induct}
Suppose $a,b \in \naturals$ and $a>0$.  Prove by induction on $a$ that for
all $b\leq a$, there are $x,y \in \integers$ such that $ax+by= \gcd
(a,b)$.

\solution{The proof is actually by strong induction.
{\bf Inductive Hypothesis:} 
\[P(a)::= \forall b\le a \exists x,y\in Z(\gcd(a,b)=a x +b y).
\]

\begin{proof}
{\bf Base Case:} $a=1$.  So $b=0$ or $b=1$.  In either case,
$\gcd(a,b)=a$, so letting $x=1$, $y=0$, proves $P(a)$.

{\bf Inductive Step:} We want to prove $P(a+1)$ assuming $P(n)$ holds for
all $n \leq a$.

If $b=0$ or $b=a+1$, then $P(a+1)$ holds as in the base case, so we may
assume $0<b\leq a$.  Since $b>0$, we can find the quotient, $q$, and
remainder, $r$, of $a+1$ divided by $b$, namely, $a+1 =qb + r$ for some
$q,r \in \integers, 0 \leq r < b \leq a$.

Now we know from the discussion in the text of Euclid's GCD algorithm that
$\gcd(b,r)=\gcd(a+1,b)$.  By induction hypothesis, $P(b)$, there are
integers $x',y'$ such that $gcd(b,r)=b x' + r y'$.  Therefore
\begin{eqnarray*}
\gcd(a+1,b) & = & \gcd(b,r)\\
     & = & b x' + r y'\\
& = & b x' + ((a+1)-q b) y'\\
& = & (a+1) y' + b (x' - q y').
\end{eqnarray*}
So letting $x=y'$ and $y = (x' - q y')$ proves $P(a+1)$.
\end{proof}
}

\problem \textbf{Well-ordering Principle}

Let $a,b$ be integers, and assume at least one of $a$ and $b$ is nonzero.
Define a set $L_{a,b} \subseteq \integers$ inductively as follows:
\begin{itemize}
\item $a,b \in L_{a,b}$.
\item If $c,d \in L_{a,b}$, then $c+d \in L_{a,b}$.
\item If $c \in L_{a,b}$, then $cn \in L_{a,b}$ for all $n\in\integers$.
\end{itemize}
Do the following parts without appeal to the result of~\ref{ax+by:induct}.

\bparts

\ppart %(a)

Show by induction on the definition of $L_{a,b}$ that any common
divisor of $a$ and $b$ also divides every member of $L_{a,b}$.

\solution{
\begin{proof}
The induction hypothesis $P(c)$ is ``any common divisor of $a$ and $b$
also divides $c$.''

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

\emph{($c+d$) case}: Assuming $P(c)$ and $P(d)$, we must prove
$P(c+d)$.  So suppose $e$ is a common divisor of $a$ and $b$.  Then $e
\mid c$ by hypothesis $P(c)$ and $e \mid d$ by hypothesis $P(d)$.  That
is, $c = ef$ and $d=eg$ for some $f,g \in \integers$.  Hence $c+d = ef+eg=
e(f+g)$ so $e \mid c+d$, namely $P(c+d)$.

\emph{($cn$) case}: Assuming $P(c)$ and $n \in \integers$, we must
prove $P(cn)$.  So suppose $e$ is a common divisor of $a$ and $b$.  Then
$e \mid c$ by hypothesis.  Hence $e \mid cn$, namely $P(cn)$.
\end{proof}
}

\ppart %(b)

Show that if $c,d \in L_{a,b}$ and $c= dq + r$ for some $q,r \in
\integers$, then $r \in L_{a,b}$.

\solution{Since $d \in L_{a,b}$, we have $d(-q) \in L_{a,b}$ by
the ($nc$) case.  Then since $c \in L_{a,b}$, we have $c + d(-q) = r \in
L_{a,b}$ by ($c+d$) case.}

\ppart %(c)

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

\solution{At least one of the integers $a, -a, b, -b \in L_{a,b}$ must be
positive.  Hence by the well-ordering principle, there is a least positive
integer $g \in L_{a,b}$.

Suppose $c \in L_{a,b}$.  We must show that $g \mid c$.

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

\ppart %(d)

Conclude that $g = \gcd(a,b)$.

\solution{By part (a), any common divisor of $a$ and $b$ divides $g$.
Also, since $a,b \in L_{a,b}$, part (c) implies $g$ is a common divisor of
$a$ and $b$, which implies $g$ is the greatest common divisor.}

\ppart Conclude that $\gcd(a,b) = ax+by$ for some $x,y \in \integers$.

\solution{It's easy to prove by structural induction that every element of
$L_{a,b}$ is equal to $ax + by$ for some $x,y \in \integers$, so $g$ is
of this form.}

\eparts


\problem \textbf{Structural Induction}

Suppose we start with a sequence of fully parenthesized arithmetic or
Scheme expressions, and then erase all the alphanumeric characters other
than parentheses.  The result is a string of parentheses which ``match
up''.

For example, erasing non-parenthesis characters from the expression
\texttt{(if (or x y) u v)} leaves the string \texttt{(())}.  Similarly,
erasing non-parentheses from the sequence of three arithmetic expressions
\[
\texttt{(x * x), (y + (3 * (z - 9))), ((x + y) * (u + w))}
\]
leaves the string
\[
\texttt{()((()))(()())}.
\]
On the other hand, even though the string \texttt{())(()} has an equal
number of left and right parentheses, it cannot be obtained by erasing in
this way---because the two middle parentheses don't match up.  Also, no
string of parentheses which begins with a right parenthesis or ends with a
left parenthesis can match up.

We can give an inductive definition of the set, SMU, of ``Strings which
Match Up'', as follows:

\begin{itemize}
\item The empty string (consisting of no parentheses) is an SMU.

\item If $s$ and $t$ are SMU's, then the string $\texttt{(}s\texttt{)}t$
is an SMU.  That is, the new string starts with a left parenthesis which
is followed by the parenthesis characters in the string $s$, followed by a
right parenthesis, followed by the parenthesis characters in the string
$t$.

\end{itemize}


There is a simple test to determine whether a string of parentheses is an
SMU: starting with zero, read the string from left to right adding one for
each left parenthesis and -1 for each right parenthesis.  A string
\emph{counts well} when the count never goes negative and is back to zero
by the end of the string.  Let CW be the set of strings of parentheses
which Count Well.

\bparts
\ppart Prove that CW contains SMU.

\solution{We prove by induction on the definition of SMU (that is,
structural induction) that every element of SMU counts well, so SMU is
contained in CW.  The induction hypothesis is
\[
P(s) ::\equiv s \in \mbox{CW}.
\]
\begin{proof}

{\bf Base Case}: $P(\mbox{empty string})$ holds since the count of the
empty string ends when it starts at zero.

{\bf Inductive Step:} Assume $P(s)$ and $P(t)$ are true.  We need to show
that $P(\texttt{(}s\texttt{)}t)$ is true.

The count values for $\texttt{(}s\texttt{)}t$ start with 0.  Reading the
initial left parenthesis yields 1 as the next count value.  This 1 serves
as the start of a series of count values exactly equal to the count values
of $s$, with each value incremented by one.  Since $s \in \mbox{CW}$ by
hypothesis, these incremented count values begin with 1, always stay
positive, and end with 1.  The right parenthesis immediately after $s$
reduces the ending count to 0.  This 0 serves as the start of the
remaining count values which are exactly the count values of $t$.  Since
$t \in \mbox{CW}$, these remaining values never go negative and end at 0.
Hence the entire sequence of count values for $\texttt{(}s\texttt{)}t$
starts with 0, never goes negative, and ends with 0, which proves that
$\texttt{(}s\texttt{)}t \in \mbox{CW}$.
\end{proof}}

\ppart Conversely, prove that SMU contains CW.

\solution{We show that every string $r\in \mbox{CW}$ is an SMU by
strong induction on the length of $r$.  The induction hypothesis is
\[Q(n) ::\equiv \forall r \in \mbox{CW}(\mbox{if $r$ is length $n$, then
$r \in \mbox{SMU}$}).\]
\begin{proof}

{\bf Base Case} $n = 0$: In this case there is only one string of length
$n$, namely the empty string, which is in SMU by definition, proving
$Q(0)$.

{\bf Inductive Step:} Assume that $Q(k)$ is true for all $k\leq n$, we
need to prove that $Q(n+1)$ is also true.

So suppose $r$ is a length $n+1$ string that counts well.  We must prove
that $r \in \mbox{SMU}$.

Now since $r$ counts well, it must start with a left parenthesis (or else
the count would immediately go negative).  Likewise, since the count for
$r$ returns to the value 0 by the end, $r$ must end with right
parenthesis.  So there must be a \emph{first} right parenthesis in $r$
after which the count returns to 0.  Let $s$ be the substring of $r$
between the initial left parenthesis and this right parenthesis.  So
\[
r = \texttt{(}s\texttt{)}t
\]
for some string $t$.

Since counts only change by one as each parenthesis character is read, and
the count for $r$ \emph{first} returns to 0 after the right parenthesis
following $s$, the count during $s$ must start and end with 1 and must
stay \emph{positive} in between.  But this implies that a count for $s$
alone, which would start with 0, would also end with 0 and stay
\emph{nonnegative} in between.  That is, $s$ by itself counts well.  Since
the length of $s \in \mbox{CW}$ is less than the length of $r$, we have by
strong induction that $s \in \mbox{SMU}$.

Further, we know the count for $r$ returns to 0 after the right
parenthesis following $s$, and since $r \in \mbox{CW}$, the count ends
with 0 again and stays nonnegative in between.  But this implies that $t$
counts well, and since the length of $t$ is less than the length of $r$,
we have by strong induction that $t \in \mbox{SMU}$.  Now by the second
case in the definition of SMU, we conclude $\texttt{(}s\texttt{)}t$,
namely $r$, is in SMU.
\end{proof}}

\eparts


\end{problems}

\end{document}
