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

\addtolength{\textheight}{.05in}

\begin{document}

\psol{3}{February 27, 1997}


\begin{problems}

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

{\sc Base Cases ($n=0,1$): } If $n=0$ then $f_0=0$ which is less then 
or equal to $2^0=1$.
If $n=1$ then $f_1=1\leq 2^1 = 2$.

{\sc Inductive Hypothesis ($n\geq 1$):} Assume that $f_m\leq 2^m$ for all 
$m\leq n$. 
 
{\sc Inductive Step: } We use the inductive hypothesis to 
prove that $f_{n+1}\leq 2^{n+1}$.
Using the recursive definition of fibonacci number we get
$f_{n+1} = f_n + f_{n-1}$ which by inductive hypothesis is 
less then or equal to $2^n+2^{n-1} < 2^n + 2^n = 2^{n+1}$.


\iffalse

\problem What quantities of money can be formed from just dimes and
quarters?  
% 
% The answer is $10$ and all multiples of five greater then 
% or equal to $20$.
% 
% To make the statement of the problem clearer we introduce some 
% notation.
% Let $P(n)$ be the predicate ``$(n=10)\vee (5|n \wedge n\geq 20)''$,
% and let $Q(n)$ be the predicate ``we can make $n$ cents using 
% dimes and quarters''.
% 
% We claim that for all $n$, $P(n)\leftrightarrow Q(n)$,
% i.e., we can make $n$ cents if and only if $n$
% is $10$ or a multiple of $5$ not smaller then $20$.
% 
% There are two ways we can prove this claim by inductions:
% we can directly prove by (strong) induction on $n$ that 
% $\forall n.P(n)\leftrightarrow Q(n)$,
% or we can first prove that $\forall n. P(n) \rightarrow Q(n)$
% and then prove that $\forall n. Q(n) \rightarrow P(n)$
% 
% We will illustrate both approaches.
% 
% \begin{problemparts}
% 
% \problempart First we prove by strong induction that 
% $\forall n.P(n)\leftrightarrow Q(n)$.
% 
% {\sc Base Cases:} As  base cases we take all $n<25$.
% Clearly, if $n<25$ then  $P(n)$ is true iff $n=10$ or $n=20$.
% Now notice that since $n<25$ we cannot use quarters and the only 
% quantities we can make using dimes are 
% $10$ and $20$ cents using $1$ or $2$ dimes respectively.
% Therefore if $n<25$, $Q(n)$ is true iff $n=10$ or $n=20$.
% So, for all $n<25$ we have $P(n)\leftrightarrow Q(n)$.
% 
% {\sc Inductive Step:} Let $n\geq 25$ and assume that for 
% all $m<n$ we have $P(m)\leftrightarrow Q(m)$.
% We will prove that $P(n)\leftrightarrow Q(n)$.
% 
% First assume that $Q(n)$ is true, i.e.,
% we can make $n$ cents using dimes and quarters.
% We will prove that also $P(n)$ is true.
% We distinguish two cases:
% \begin{itemize}
%  \item If we used only quarters then $n=25h$ for some $h\geq 1$,
%   and therefore $n$ is a multiple of $5$ and $P(n)$ is true. 
%  \item Otherwise we used a dime. If we can make $n$ cents 
%   using quarters and at least one dime, we can also make $n-10$ cents
%   using one less dime. This proves that $Q(n-10)$ is true.
%   By induction hypothesis this implies also $P(n-10)$ is true
%   and therefore $n-10$ is a multiple of $5$.
%   If $5|(n-10)$ then $5|n$. Since $n\geq 25$
%   we have $P(n)$.
% \end{itemize}
% 
% Now assume that $P(n)$. We will prove $Q(n)$.
% We know that $n$ is a multiple of $5$ and $n\geq 25$.
% Therefore $n=20+5k$ for some $k\geq 0$.
% If $k$ is even, we can make $n$ cents using 
% $2+k/2$ dimes.
% If $k$ is odd we can make $n$ cents using
% one quarter and $(k-1)/2$ dimes.
% In both cases we have $Q(n)$.
% 
% This concludes the proof by strong induction.

\problem What quantities of money can be formed from just dimes and
quarters?  

The answer is $10$ and all multiples of five greater then 
or equal to $20$.

We can prove this by strong induction on $n$ where $n=5k$ for $k=2$ and $k \geq 4$.

\begin{problemparts}

\problempart 

{\sc Base Cases:} As  base cases we take all $n \leq 25$.
Clearly, if $n \leq 25$ then  we  can make $10$ from one dime,
$20$ from two dimes, and $25$ from one quarter.

{\sc Inductive Step:} Let $n\geq 25$ and assume that for 
all $25<m<n$ we can make $m$ cents out of dimes and quarters.
Show that we can make $n$ cents out of dimes and quarters.

If $n > 25$ then we know that $n-10 > 15$ and by the base cases and 
the inductive hypothesis, we know that we can make $n-10$ cents using only
dimes or quarters.  we can therefore make $n$ cents by adding
a dime, so we can make $n$ cents out of dimes and quarters.

This completes the inductive step, so we know we can make $n$ cents
out of dimes and quarters where $n=10$ or $n \geq 20$ and $n$ is a multiple 
of 5.


Now, we need to show that we cannot make any other amounts using only
dimes or quarters.  Take first the case of $5$ cents:  We clearly cannot
make $5$ cents because dimes and quarters are both larger than $5$ cents.
We also cannot make $15$ cents, by inspection.

We cannot make amounts that are not divisible by $5$ because any 
combination of dimes, $d$, and quarters, $q$, will give us 
$c=10d+25q =5(2d+5q)$, which is clearly a multiple of $5$ when 
d and q are natural numbers.


\problempart Prove the same thing by well-ordering

Let's now prove the same thing using well-ordering. 

To make the statement of the problem clearer we introduce some 
notation.
Let $P(n)$ be the predicate ``$(n=10)\vee (5|n \wedge n\geq 20)''$,
and let $Q(n)$ be the predicate ``we can make $n$ cents using 
dimes and quarters''.

We claim that for all $n$, $P(n)\leftrightarrow Q(n)$,
i.e., we can make $n$ cents if and only if $n$
is $10$ or a multiple of $5$ not smaller then $20$.

This time we will prove 
$\forall n. P(n) \rightarrow Q(n)$
and $\forall n. Q(n) \rightarrow P(n)$ separately.

We first prove that $\forall n. P(n) \rightarrow Q(n)$.
Let $S$ be the set of all $n$ such that 
$P(n)$ and $\neg Q(n)$. 
We will show that $S$ is empty.
Assume for contradiction that $S$ is not empty.
By the well-ordering axiom, $S$ has a minimum element $m$.
Since $P(m)$ is true, $m$ is a multiple of $5$,
but we cannot make $m$ cents using dimes and quarters.
Notice that $m$ must be greater then or equal to $30$
because $10,20$ and $25$ cents can be made using 
respectively $1,2$ dimes or a quarter.
Let $n=m-10$.
We cannot make $n$ cents using dimes and quarters 
because otherwise we could also make $m=n+10$ cents
using one more dime. So, $Q(n)$ is false.
Moreover, $m\geq 30$ and therefore $n\geq 20$.
Since $n$ is a multiple of $5$,
$P(n)$ is true and $n$ is in the set $S$ contradicting 
the fact that $m$ was the minimum element.

We now prove that $\forall n. Q(n) \rightarrow P(n)$.
Let $T$ be the set of all $n$ such that 
$Q(n)$ and $\neg P(n)$. 
We will show that $T$ is empty.
Assume for contradiction that $T$ is not empty.
By the well-ordering axiom, $T$ has a minimum element $m$.
We have $Q(m)$, so we can make $m$ cents using dimes and quarters.
We distinguish two cases:
\begin{itemize}
\item if we used at least one dime to make $m$, 
 then we can also make $n=m-10$ cents using one less dime, 
 i.e., $Q(n)$.
 Moreover, $\neg P(n)$ because otherwise 
 also $m=n+10$ satisfies $\neq P(m)$ (if we add $10$ to a multiple of 
 $5$ it will still be a multiple of $5$).
 So, $n\in T$ contradicting that $m$ is minimum.
\item if we didn't use any dime to make $m$,
 then $m=25h$ and $P(m)$ which contradicts $m\in T$.
\end{itemize}
\end{problemparts}

{\bf: THIS IS AN ALTERNATIVE SOLUTION TO PROBLEM 3.} 

What quantities of money can be formed from just dimes and
quarters?  

\fi

First of all notice that if we can make $n$ cents using dimes 
and quarters then $n=10a+25b = 5(2a+5b)$ for some $a$ and $b$,
and therefore $n$ must be a multiple of $5$.
We can make $10$ cents using one dime, and we cannot make 
neither $5$ nor $15$ cents.
We claim that we can make any other quantities $n$ 
such that $n\geq 20$ and $5|n$.
In other words, we can make $20+5k$ cents for all $k\geq 0$.
We will prove this statement first by strong induction 
and then by well-ordering.

\begin{problemparts}
 \problempart
  We prove that we can make $20+5k$ cents 
  using dimes and quarters by strong induction on $k$.
  
  {\sc Base cases ($k=0,1$)} We can make $20$ and $25$ cents
  using two dimes and using one quarter respectively.

  {\sc Inductive Step ($k\geq 2$):}
  Assume we can make $20+5h$ cents for all $h<k$.
  In particular we can make $20+5(k-2)$ cents using 
  dimes and quarters. 
  Using one more dime, we can also make 
  $20+5(k-2) + 10=20+5k$ cents, 
  completing the induction proof.

 \problempart
  We prove that we can make $20+5k$ cents 
  using dimes and quarters by well-ordering.
  Let $S$ be the set of all $k$ such that 
  we cannot make $20+5k$ cents using dimes and quarters
  and assume for contradiction that $S$ is not empty.
  By well-ordering, $S$ has a minimum element $m$.
  $m$ cannot be $0$ or $1$ because we can make 
  $20$ and $25$ cents. Therefore, $m\geq 2$
  and $m-2\geq 0$.
  We claim that $m-2$ is in $S$.
  To prove this, notice that if we could make $20+5(m-2) = 20+5m -10$
  cents using dimes and quarters, then we could make also 
  $20+5m$ cents using one more dime.
  But, this is impossible because $m\in S$.
  So, $m-2\in S$ and $m$ is not the minimum.
\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.

Blue numbers are $3$ and all numbers greater 
then or equal to $5$.

\problempart Prove you answer to the previous part.

By inspection we notice that $3$ is blue, and $0,1,2$ and $4$ are not blue.
It remains to be proven that all numbers $n\geq 5$ are blue.
The proof is by induction on $n$.

{\sc Base Case ($n=5,6,7$): } $5=5$, $6=3+3$ and $7=7$.

{\sc Inductive Step ($n\geq 8$): } Assume that all numbers between $5$
and $n$ (excluded) are blue. We want to prove that $n$ is blue.
Notice that $n-3$ is blue by hypothesis.
and therefore it can be written as a sum of odd primes $p_1+p_2+\cdots+p_k$.
It follows that $n = (n-3)+3 = p_1+p_2+\cdots+p_k+3$ is 
also blue.
 
\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.

The number $6$ is divisible by $1,2,3,6$
and $1+2+3=6$. So, $6$ is perfect.
Similarly $28$ is divisible by $1,2,4,7,14,28$ and 
$1+2+4+7+14 = 28$.
So, $28$ is perfect.

\problempart Prove that $n = 2^{p-1}(2^p-1)$ is perfect when $2^p-1$ is
prime.

First of all notice that $2$ and $2^p-1$ are two 
distinct primes. Therefore the set of divisors of $n=2^{p-1}(2^p-1)$
is 
\[\{2^i(2^p-1)^j \mid 0\leq i \leq p-1, 0\leq j\leq 1\}.\]
If we add up all these numbers we get:
\[\left(\sum_{i=0}^{p-1} 2^i\right)\cdot\left(1 + (2^p-1)\right) 
 = (2^p-1)\cdot 2^p = 2n.\]
Notice that we added up all divisors of $n$ (including itself). 
So, the sum of all divisors of $n$ other then itself is 
$2n-n = n$, proving that $n$ is perfect.

\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$

We prove by structural induction on $w$ that for all $w$ and $v$,
$(vw)^R = w^Rv^R$.

{\sc Base Case:} $w=\lambda$ and 
\[(v\lambda)^R = v^R = \lambda v^R = \lambda^R v^R.\]

{\sc Inductive Step:} We have $w=zx$ for some $x\in \Sigma$.
Using the inductive hypothesis $(vz)^R=z^Rv^R$ and 
the definition of $R$ we get
\begin{eqnarray*}
 (vw)^R &=& (vzx)^R \\
 &=& x(vz)^R \\
 &=& xz^Rv^R \\
 &=& (zx)^R v^R \\
 &=& w^Rv^R.
\end{eqnarray*}


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

The proof is by structural induction on the definition of binary tree.

{\sc Base Case:}
A tree consisting of one node with no children 
has height $h=0$.  So $1\leq 2^{h+1}-1 = 1$. 

{\sc Inductive Steps:} We have three cases 
corresponding to the three cases of the definition:
\begin{itemize}
 \item If the tree $T$ is a node with a left child but no right child,
  let $L$ be the left child binary tree and let $h$ be its height.
  By inductive hypothesis, the tree $L$ has at most 
  $2^{h+1}-1$ nodes. 
  The height of tree $T$ is $h+1$, and the number of nodes in $T$
  is at most $1+2^{h+1}-1 = 2^{h+1} <2^{h+2}-1$.
 \item If the tree $T$ is a node with a right child but no left child,
  it is analogous to the previous case.
 \item If the tree $T$ is a node with both a left and right 
  child $L$ and $R$, then let $h_1$ and $h_2$ be the 
  heights of the trees $L$ and $R$ respectively.
  Let also $h$ be the maximum of $h_1$ and $h_2$.
  By inductive hypothesis the trees $L$ and $R$
  have at most $2^{h_1+1}-1\leq 2^{h+1}-1$
  and $2^{h_2+1}-1 \leq 2^{h+1}-1$ nodes.
  So, the number of nodes in $T$ is at most 
  $1+(2^{h+1}-1)+(2^{h+1}-1) = 2^{h+2}-1 = 2^{h'+1}-1$ nodes, 
  where $h' = h+1$ is the height of $T$.
\end{itemize}

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

The flaw is that we should prove both $n=0$ and $n=1$ 
as bases cases because the inductive step uses the 
previous two values of $n$.
Clearly $a^1=1$ is not true, unless $a=1$,
and therefore the proof is wrong.

\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}$.

The flaw is that the well-ordering principle does not 
hold for the rationals, so we cannot use it to conclude 
that the above set has a minimum.


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

The flaw in the above proof is that the set of numbers that 
can be described in less than eighty characters, 
is not a well-defined set.

\end{problemparts}

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

The number of zeros at the end of $100!$ is the highest 
$n$ such that $10^n|100!$, or equivalently 
$2^n|100!$ and $5^n|100!$.

Let's first find the highest $n$ such that $5^n|100!$.
One every five numbers in $1\cdot 2\cdots 99\cdot 100$
is a multiple of five.
So, there are $100/5=20$ multiple of $5$ between 
$1$ and $100$ (included).
Four of these numbers are in fact multiple of $25=5^2$
(25,50,75 and 100).
So, we must account for four more $5$ factors.
In conclusion the total number of $5$ in the 
prime factorization of $100!$ is $20+4=24$
and $n=24$ is the highest $n$ such that $5^n|100!$.

We note that $2^{24}|100!$ because $100!$
is the product of $100$ numbers half of which 
are even.
 
Therefore $n=24$ is the highest $n$ such that $10^n|100!$.

\end{problems}
        
\end{document}



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