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

\addtolength{\textheight}{.15in}


\begin{document}
\pset{3}{February 20, 1996}{Start of Class, Tuesday, February 25}

{\bf Reading:} Rosen, Sections 2.3 and 3.3


\begin{problems}

\problem Show that the Fibonnacci number $f_n$ satisfy $f_n \leq 2^n$
  using strong induction.

\problem What quantities of money can be formed from just dimes and
quarters?  
\begin{problemparts}
\problempart Prove by strong induction that these and no other
quantities can be formed.  
\problempart Prove the same thing by well ordering
\end{problemparts}

\problem Call a natural number {\em blue} if it can be written as a
sum of one or more (not necessarily distinct) odd primes.
\begin{problemparts}
\problempart Identify all blue numbers
\problempart Prove you answer to the previous part.
\end{problemparts}


\problem Call a number {\em perfect} if it is the sum of all its
divisors other than itself.
\begin{problemparts}
\problempart Prove that 6 and 28 are perfect.
\problempart Prove that $2^{p-1}(2^p-1)$ is perfect when $2^p-1$ is
prime.
\end{problemparts}


\problem Read the recursive definition of strings over an alphabet
$\Sigma$ in Rosen 3.3, example 10.  Define the {\em reversal} of a
  string $w$, written $w^R$, as follows:
\begin{itemize}
\item $\lambda^R = \lambda$
\item if $w=vx$ where $v \in \Sigma^*$ and $x \in \Sigma$, then $w^R \
  xv^R$
\end{itemize}
Prove that $(vw)^R = w^Rv^R$

\newpage

\problem Recall that we defined binary trees in class as either 
\begin{itemize}
\item A {\em node} with no children.
\item A node with a left child that is a binary tree, and no right child.
\item A node with a right child that is a binary tree, and no left child.
\item A node with left and right binary-tree children.
\end{itemize}
Consider the following recursive definition of the {\em height} of a
binary tree:
\begin{itemize}
\item The height of a node with no children is 0
\item The height of a tree on a node with children is one more than the maximum
  of its children's heights.
\end{itemize}
Prove that a tree of height $h$ contains at most $2^{h+1}-1$ nodes.




\problem 
Find the flaws in  the following ``proofs.'' 

\begin{problemparts}

\problempart
CLAIM: $a^n = 1$ for all nonnegative
integers $n$, whenever $a$ is a nonzero real number. 

BASIS STEP: $a^0 = 1$ is true by the definition of $a^0$.

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.
\)

\problempart CLAIM: $\sqrt{2}$ is rational.

PROOF: Well ordering.  Let $S$ be the set of all rational numbers
greater than or equal to $\sqrt{2}$.  This set contains a least
element $r$ by well ordering.  If this element is not $\sqrt{2}$, then
there is another rational element between $\sqrt{2}$ and $r$ (by
denseness of the rationals), implying $r$ is not the smallest, a
contradiction.  Thus we must have $r=\sqrt{2}$.

\problempart CLAIM: every number can be described in a phrase of less
than eighty characters.  

PROOF: Well ordering.  Let $S$ be the set of numbers that
cannot be described in a phrase of less than eighty characters.  If it
is nonempty, it contains a smallest element.  This is ``The smallest
number that cannot be described in less than eighty chracters.''  This
is a description of that number in less than eighty characters, a
contradiction.  Since the assumption that $S$ was nonempty yields a
contradiction, $S$ must be empty and the claim is proved.

\end{problemparts}

\problem {\bf (Optional)} How many zeroes are there at then end of
$100!$?  Prove it.


\end{problems}
        
\end{document}



% Local Variables: 
% mode: latex
% TeX-master: t
% End: 
