\documentstyle[12pt,twoside,amstex]{article}
\input{macros-course}

\addtolength{\textheight}{.05in}
\begin{document}

\pset{2}{February 10, 1998}%
{In lecture, Thursday, February 19}

(2/11: Problems 5 and 7 corrected.)

\reading 
Sections 3.2--3 of Rosen.  Finish reading {\em The Nuts and Bolts of Proofs\/}. 

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 1: variant of F97

\problem

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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 2: taken from Fall 96

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

%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.

%adapted from Rosen 3.3, prob 50
%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.

%Problem 5 (adapted from unused problem in F97, pset2)
%DELETED: Example 8 of Rosen, section 3.2, shows that every set of $n$
%elements contains $2^n$ subsets.

\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
%revised ``is a'' into ``corresponds to''
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\}$.
%SENTENCE ADDED:
So $\mbox{Even}(n+1) =
\mbox{Even}(n) + \mbox{Odd}(n)$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 6 part a) variant of F94 

\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

\ppart %SEE THE SOLUTION FOR A REFINED VERSION OF THIS PROBLEM:
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$.

Proof by 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 hypothesis: 
Now assuming the claim holds for $n$, we must prove it holds for $n+1$.

So suppose $p|x_1x_2\ldots x_{n+1}$.  If $p|x_1\ldots x_n$, then by the
inductive hypothesis we know that $p|x_i$ for some $1\leq i\leq n$, and we
have the desired $i$.  Otherwise, $p|x_{n+1}$, so $i = n+1$ will do. \qed

\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
%TYPO FIXED: changed \leftrightarrow to \implies:
$F \wedge G  \mbox{ and } F \implies 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$.



\iffalse
%Problem 8
\problem
The well-matched strings of left and right parentheses, {\em WMP}'s
for short, are defined inductively as follows:
\begin{itemize}

\item The string of length two consisting of a left parenthesis followed
by a right parenthesis, namely, {\tt ()}, is a WMP.

\item If $W$ and $\mbox{\tt (}Z\mbox{\tt )}$ are WMP's, where $Z$ is a
finite string of zero or more parentheses, then $\mbox{\tt
(}ZW\mbox{\tt )}$ is a WMP.

\end{itemize}

The {\em count} of a string of one or more parentheses is defined as
follows:
\begin{itemize}
\item $\mbox{count}(\mbox{\tt)}) = -1$,
\item $\mbox{count}(\mbox{\tt(}) = 1$,
\item of $s$ is a string of parentheses and $p$ is a single parenthesis,
then  $\mbox{count}(sp) = \mbox{count}(s) + \mbox{count}(p)$.
\end{itemize}

A string, $Z$, of parentheses is a {\em well-counting} string of
parentheses, a {\em WCP} for short,
iff $\mbox{count}(Z) = 0$ and $\mbox{count}(X)> 0$ for any proper prefix,
$X$, of $Z$.  ($X$ is a prefix of $Z$ means that $Z = XY$ for some string
$Y$.  $X$ is a {\em proper} prefix if it is a prefix of $Z$ and its length
is positive and strictly less than the length of $Z$.)
\fi



\end{problems}
\end{document}
% Local Variables: 
% mode: latex
% TeX-master: t
% End: 
% LocalWords:  Carrol
