\documentstyle[12pt,twoside,macpsfig,amstex]{article}
\input{macros-course}
%	\addtolength{\topmargin}{-.35in}
%	\setlength{\textheight}{9in}

\begin{document}

\psol{2}{February 19, 1998 (soln to prob 6 revised 2/27)}

\bigskip

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem Prove: For all $x, n \in \naturals : x+1|x^{2n+1}+1$.

\bigskip
Proof by induction on $n$ with
\[P(n) ::\equiv \forall x \in \naturals: x+1|x^{2n+1}+1.\]
{\em Base Case:} $n=0$.  Then $2n+1=1$ and $P(0)$ is true since
$x+1|x^1+1$.

{\em Inductive Step:} Assume $P(n)$, so $x^{2n+1}+1 = p(x+1)$ for some
integer $p$.  We need to show that $x+1|x^{2(n+1)+1}+1$.
\begin{eqnarray*}
x^{2(n+1)+1}+1&=&x^2x^{2n+1}+1\\
&=&x^2(x^{2n+1}+1)-x^2+1\\
&=&x^2p(x+1)-(x-1)(x+1)\\
&=&(x^2p-(x - 1))(x+1).
\end{eqnarray*}
So $x+1$ is indeed a factor of $x^{2(n+1)+1}+1$. \qed


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 2

\problem Prove that 
\[1 \cdot 1! + 2 \cdot 2! + ... + n \cdot n! = (n+1)! - 1,\]
for all $n \in \naturals$.

\bigskip
Proof by induction on $n$.

{\em Base Case:} $n = 0$. True since $\mbox{L.H.S.} = 0 = \mbox{R.H.S}$.

{\em Inductive Step:} Assuming the inductive hypothesis, we have
\begin{eqnarray*}
1\cdot 1!+2\cdot 2!+...+n\cdot n!+(n+1)\cdot (n+1)!&=&(n+1)!-1+(n+1)\cdot (n+1)!\\                                                &=&(n+1)!(1+n+1)-1\\
                                                   &=&(n+2)!-1
\end{eqnarray*}
as desired.

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 3
\problem
For $n \in \naturals$, define numbers $u_n$ by the equations:
\[u_0 = 2, u_1=3, u_{n+2} = 3u_{n+1}-2u_{n}.\]

Guess a general formula for $u_n$ and use mathematical induction to prove
your answer.


\bigskip

We claim, $u_n=2^n+1$ for all $n\in\naturals$.  We can prove it by strong
induction on $n$.

{\em Base Cases:} $n=0,1$. Then $u_0=2=2^0+1$ and $u_1 = 3 = 2^1+1$ as required.

{\em Inductive Step:} We may assume $n\geq 1$ and $u_k=2^k+1$ for all
$k\leq n$.  We shall show $u_{n+1}=2^{n+1}+1$.  Since $n-1 \geq 0$, the
value of $u_{n+1}$ is determined by the recurrence formula, namely,
\begin{eqnarray*}
u_{n+1}&=&3u_n-2u_{n-1}\\
&=&3(2^n+1)-2(2^{n-1}+1)\\
&=&3\cdot2^n-2\cdot2^{n-1}+1\\
&=&3\cdot2^n-2^n+1\\
&=&2\cdot2^n+1\\
&=&2^{n+1}+1
\end{eqnarray*} \qed


%Problem 4
\problem
A set of lines in the plane is said to be in {\em general position} when
no two of the lines are parallel, and no three intersect at a common
point.  Let $R_n$ be the number of regions into which $n$ lines in general
position divide the plane.  For example, $R_0 = 1, R_1 = 2, R_2 = 4$.
Explain, informally but clearly, why $R_{n+1} = R_n + (n+1)$.  Find a
simple formula for $R_n$ and prove your result by induction.


\bigskip
A set of $n$ lines in a general position divides the plane into $R_n$
regions.  When the $(n+1)^{st}$ line is added to the plane such that the
resulting set of lines is in a general position, the new line has to
intersect the previous $n$ lines, splitting in two each region above a
point of intersection, and also splitting in two the region below the
lowest point of intersection.  This splits $n+1$ regions into $2(n+1)$
regions, with a net increase of $n+1$ regions.  Therefore
$R_{n+1}=R_n+(n+1)$.

A general formula for $R_n$ is $\frac{n(n+1)}{2}+1$, as we prove by
induction.

{\em Base Case:} $n=0$.  There is one region, namely the whole plane, and
so thew number of regions equals $R_0$.

{\em Inductive Step:} Assuming $R_n=\frac{n(n+1)}{2}+1$, we need to show
that $R_{n+1}=\frac{(n+1)(n+2)}{2}+1$.

\begin{eqnarray*}
R_{n+1}&=&R_n+(n+1)\\ 
&=&\frac{n(n+1)}{2}+1+(n+1)\\
&=&(n+1)(\frac{n}{2}+1)+1\\
&=&\frac{(n+1)(n+2)}{2}+1
\end{eqnarray*}

as desired.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 5
\problem  Prove that any finite set
of size $n>0$ has exactly $2^{n-1}$ subsets of even size.  For example,
$\{1,2\}$ has two subsets of even size: $\emptyset$ and $\{1,2\}$.  {\em
Hint}: Let $e$ be an element of a set $S$ of size $n+1$.  An even size
subset of $S$ which does not contain $e$ corresponds to an even size
subset of $S - \{e\}$; an even size subset of $S$ which does contain $e$
corresponds to an odd size subset of $S - \{e\}$.
So $\mbox{Even}(n+1) = \mbox{Even}(n) + \mbox{Odd}(n)$.

\bigskip
(Proof by induction.)  Let $\mbox{Even}(n)$ be the number of even-size
subsets of a set of size $n$.  Then we have to show $\forall n>0 :
\mbox{Even}(n)=2^{n-1}$.  To do this, we let $\mbox{Odd}(n)$ be the number
of odd-size subsets of a set of size $n$, and we prove by induction a
somewhat stronger fact:

{\em Induction hypothesis}: $P(n)::\equiv [\mbox{Even}(n)=2^{n-1} \wedge
\mbox{Odd}(n)=2^{n-1}]$.

{\em Base Case:} $n=1$.  There is one even-size subset, namely the empty
set, and one odd-size subset, namely the whole set.  So
$\mbox{Even}(1)=\mbox{Odd}(1)=1=2^{1-1}$.  So $P(1)$ is true.

{\em Inductive Step:} Let $A$ be a set of size $n+1$.  Let $e$ be an
element of $A$.  The number of even-size subsets in $A$ which do not
contain $e$ is equal to the number of even-size subsets in $A-\{e\}$.
Also, the number of even-size subsets of $A$ which do contain $e$ is equal
to the number of odd-size subsets in $A-\{e\}$.  Since the set $A-\{e\}$
is of size $n$, we have the following recurrence
\[\mbox{Even}(n+1)=\mbox{Even}(n)+ \mbox{Odd}(n).\]

Similarly, the number of odd-size subsets of $A$ which do not contain $e$
is equal to the number of odd-size subsets in $A-\{e\}$, and the number of
odd-size subsets of $A$ which do contain $e$ is equal to the number of
even-size subsets of $A-\{e\}$, so
\[\mbox{Odd}(n+1)=\mbox{Odd}(n)+ \mbox{Even}(n).\]

By induction we have that $\mbox{Even}(n)=2^{n-1}$ and
$\mbox{Odd}(n)=2^{n-1}$.  So
\[\mbox{Even}(n+1)=2^{n-1} +2^{n-1} = 2^n,\]
and
\[\mbox{Odd}(n+1)=2^{n-1} +2^{n-1} = 2^n,\]
which proves $P(n+1)$. \qed



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 6

\problem
Pinpoint, and illustrate with a counterexample, {\em exactly} where the
following proofs go awry.

\bparts
\ppart Claim 1: $(\forall \mbox{real } x) (\forall n\in \naturals) : x^n=1$.

Proof by strong induction on $n$:

(Base case, $ n= 0$) $x^n = x^0=1$ by definition of ``zeroth power'' of a
real number.

(Strong Induction hypothesis) For all $k\leq n: x^k=1$.

We must show that $x^{n+1}=1.$ By the strong inductive hypothesis, with
$k=n$ and $k=1,$ we have $x^n=1$ and $x^1=1$.  So,
\[x^{n+1}=x^nx^1 = 1\times 1=1.\] \qed

\bigskip

The proof of the induction step is not correct when $n=0$.  In this case,
$k=1$ is not $\leq n$, so we cannot assume by strong induction that $x^1 =
1$, which of course it is not when $x\neq 1$.


\ppart Claim 2: For any positive integers $p, n, x_1, x_2,\ldots, x_n$, if
$p|x_1x_2\ldots x_n$, then $p|x_i$ for some $1\leq i\leq n$.

\textbf{(Refined 2/27/98 by ARM)}:

Proof by strong induction on $n$.

(Base case, $n= 1$) When $n=1$, we have $p|x_1$, therefore we can let
$i=1$ and conclude $p|x_i$.

(Induction case) Now assuming the claim holds for all $k\leq n$, we must
prove it for $n+1$.

So suppose $p|x_1x_2\ldots x_{n+1}$.  Let $y_n = x_n x_{n+1}$, so
$x_1x_2\ldots x_{n+1} = x_1x_2\ldots x_{n-1}y_n$.  Since the righthand
side of this equality is a product of $n$ terms, we have by induction that
$p$ divides one of them.  If $p|x_i$ for some $i < n$, then we have the
desired $i$.  Otherwise $p|y_n$.  But since $y_n$ is a product of the two
terms $x_n, x_{n+1}$, we have by strong induction that $p$ divides one of
them.  So in this case $p | x_i$ for some $i = n$ or $i = n+1$. \qed
\bigskip

The statement ``we have by strong induction that $p$ divides one of them''
is the place where the proof breaks down: it appeals to strong induction
to justify applying the induction hypothesis for $2=k\leq n$.  But the
base case was $n=1$, so we can't assume $2 \leq n$.  Note that the
reasoning above is fine for every $n\geq 2$, so the whole proof would be
fine if we had an argument to prove the claim for $n+1=2$.  But of course
we can't prove it for $n+1=2$ because it isn't true: let $p=6, x_1 =2, x_2
=3$.  Even though the reasoning is fine for every $n\geq 2$, the fact that
it failed for $n=1$ let us deduce a patently false result.

\eparts



%Problem 7
\problem Define {\em constant-free one-occurrence} Boolean formulas,
{\em 1BF}'s for short, inductively as follows:
\begin{itemize}
\item a variable is a 1BF.
\item if $F$ is a 1BF, then so is $\neg F,$
\item if $F$ and $G$ are 1BF's with no variables in common, then
$F \wedge G  \mbox{ and } F \rightarrow G$ are 1BF's.
\end{itemize}

A {\em Boolean assignment}, $A$, is a mapping from variables to truth
values.  The {\em complement} of assignment $A$ is the assignment $B$ such
that $B(x) = \neg A(x)$ for all variables $x$ in the domain of $A$.

Prove by induction that for all 1BF's, $F$, there is a Boolean
assignment $A$ for the variables of $F$ such that $F$ is true under
assignment $A$ and false under the complement of $A$.

\bigskip

We prove the theorem by strong induction on the length of the 1BF $F$, with
induction hypothesis $P(n)$:
\[\forall F:  \mbox{length}(F) = n \Rightarrow
[\exists A : (F \mbox{ is true under } A) \wedge (F \mbox{ is false under}
\overline{A})]\]
where $F$ ranges over 1BF's and $A$ ranges over Boolean assignments.  Here
we use the notation $\overline{A}$ for the complement of assignment $A$.

{\em Base Case:} $n=1$.  If $F$ is a 1BF of length 1 it must be a
variable.  Then the desired assignment is any $A$ such that
$A(F)=\mbox{true}$.

{\em Inductive Step:} Now assume $P(k)$ for all $k\leq n$.  To show
$P(n+1)$, let $F$ be a length $n+1$ 1BF for $n\geq 1$.  There are three
cases:

\begin{enumerate}
\item $F=\neg G$, where $G$ is a 1BF with length $\leq n$.  By inductive
hypothesis, there is an assignment $A_0$ such that $G$ is true under $A_0$ and
false under $\overline{A_0}$.  Then the desired assignment $A$ will be
$\overline{A_0}$.

\item $F=G\wedge H$, where $G$ and $H$ are formulas of length $\leq n$.
By inductive hypothesis there is an assignment $A_0$ such that $G$ is true
under $A_0$ and false under $\overline{A_0}$.  Also, there is an
assignment $A_1$ such that $H$ is true under $A_1$ and false under
$\overline{A_1}$.  Now let $A$ be the assignment which agrees with $A_0$
on the variables of $G$ and with $A_1$ on the variables of $H$.  Such an
$A$ exists because $F$ is a 1BF, so no variable occurs in both $G$ and
$H$.  Now under $A$ both $G$ and $H$ are true, and therefore $G\wedge H$
is true.  Likewise, $\overline{A}$ makes $G\wedge H$ false as required.

\item $F=G\rightarrow H$, where $G$ and $H$ are formulas of length $\leq
n$.  As in the previous case, there is an assignment $A_0 (A_1)$ such that
$G (H)$ is true under $A_0 (A_1)$ and false under $\overline{A_0}
(\overline{A_1})$.  So this time we let $A$ be the assignment which
agrees with $\overline{A_0}$ on the variables of $G$ and with $A_1$ on the
variables of $H$.  Now under $A$, $G$ is false and $H$ is true, so
$G\implies H$ is true; under $\overline{A}$, $G$ is true and $H$ is false, so
$G\implies H$ is false, as required.
\end{enumerate}
\qed

\end{problems}
\end{document}
