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

\begin{document}

\psol{2}{September 24, 1996}

\bigskip

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
{\bf Base Case:} $n = 1$. True since $1 \cdot 1! = 2! - 1$.\\
{\bf 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 

{\bf Base Case:} $n=1$. True since $f_1^2 = f_1f_2 = 1$.\\
{\bf Inductive Step:} Assume it is true for $k\leq n$. Then we have
\begin{eqnarray*}
f_1^2+f_2^2+...+f_n^2+f_{n+1}^2&=&f_nf_{n+1}+f_{n+1}^2\\
&=&f_{n+1}(f_n+f_{n+1})\\ &=&f_{n+1}f_{n+2}\\ 
\end{eqnarray*}
which is true by the inductive hypothesis and definition of 
{\em Fibonacci} numbers.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 

The max or min of one number is itself. max$(a_1,a_2)=a_1 \bigvee a_2$
if $a_1\geq a_2$, and $a_1<a_2$ respectively. Also, min$(a_1,a_2)=a_1
\bigvee a_2$ if $a_2\geq a_1$ and $a_2<a_1$ respectively.  For $n\geq 2$
we define
\[
max(a_1,a_2,...,a_{n+1}) = max(max(a_1,a_2,...,a_n),a_{n+1})
\]
and
\[
min(a_1,a_2,...,a_{n+1}) = min(min(a_1,a_2,...,a_n),a_{n+1})
\]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 

First, we prove the follwing theorem:

\begin{theorem} Let $n$ be a positive integer. Show that a $2^n \times
2^n \times 2^n$ cube, (an {\em $n$-cube}) with one arbitrary cubic
foot removed can be built with basic blocks of size $2\times 2\times
2$ ({\em $1$-cube}) with one of its cubic foot missing.
\end{theorem}
\begin{proof} Let $P(n)$ be the statement that any {\em $n$-cube}
with one arbitrary cubic foot missing can 
be built using {\em $1$-cubes} with one cubic foot removed.
We use mathematical induction to prove $P(n)$
is true for all positive integers $n$.

{\bf Basis Step} $P(1)$ is true since a {\em $1$-cube} with one
missing cubic foot is already provided as basic block by CIA.

{\bf Inductive Step:} Assume that $P(n)$ is true. We show that
$P(n+1)$ is true. Construct $8$ {\em $n$-cubes} in such a way that $7$
of them are missing one cubic foot from one of their $8$ corners, and
the {\em $8$th} one is missing an arbitrary cubic foot. We can do this
by the induction hypothesis. We construct an {\em $(n+1)$-cube} as
follows: Put the $7$ corner-missing {\em $n$-cubes} together so that all of
their missing corners meet in the center. Then fill up the gap with a
basic block.  Now add the {\em $8$th}
{\em $n$-cube} with an arbitrary cubic foot missing to get an
{\em $(n+1)$-cube} with an arbitrary cubic foot removed.
\end{proof}

Now we are in good shape to prove the master theorem.
\begin{theorem}
Prove that an {\em $(n+1)$-cube} with one cubic foot missing from its
center (the {\bf CIA} cube) can be built using {\em $1$-cubes} with one
cubic foot missing.
\end{theorem}
\begin{proof}
The {\bf CIA} cube can be built by following the steps in the proof of
{\bf Theorem $0.1$} except that when building the {\em $8$th} cube, we
choose the arbitrary missing cubic foot to be one of the $8$ possible
{\em $1$-cubes} in the center of the {\em $8$th} {\em $n$-cube}.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
Let $E$ denote the number of edges, and $N$ be the number of nodes in
a {\em $3,4$-tree}. Then: 
\bparts
\ppart $E = N-1$.
\ppart \begin{theorem} In a {\em $3,4$-tree}, $E = N-1$.
\end{theorem}
\begin{proof} By Structural Induction.

{\bf Basis Step:} Let $N=1$. This it is clearly true since there are no
edges in a one-node tree.

{\bf Inductive Step:} Assume this is true for $k\leq n$. We need to
show that it is also true for a tree with $N+1$ nodes. Let's break this
into two cases.

{\em Case 1:} Root of the tree has $3$ childeren, where every such
subtree is a {\em $3,4$-tree} by definition. By the induction
hypothesis, for every such subtree the number of edges is one less
than the number of nodes in the subtree.  Hence, for a tree with $N+1$
nodes, there are total of $N$ nodes and $N-3$ edges in the $3$
subtrees.  The root-node adds one more node and $3$ edges connecting
to the $3$ subtrees, making it a total of $N+1$ nodes and $N$ edges as
desired.

{\em Case 2:} Root of the tree has $4$ childeren, where every such
subtree is a {\em $3,4$-tree} by definition. By the induction
hypothesis, for every such subtree the number of edges is one less
than the number of nodes in the subtree.  Hence, for a tree with $N+1$
nodes, there are total of $N$ nodes and $N-4$ edges in the $4$
subtrees.  The root-node adds one more node and $4$ edges connecting
to the $4$ subtrees, making it a total of $N+1$ nodes and $N$ edges as
desired.
\end{proof}
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 

\bparts
\ppart $Pink = \{x : x \in \naturals,~ \mbox{and}~ x \geq 24\}$.
\ppart \begin{theorem} Every natural number $\geq 24$ can be expressed
as the sum of, not necessarily distint, perfect squares of numbers $\geq 2$.
\end{theorem}
\begin{proof} By Contradiction: Define the set $Blue=\{x: x\in
\naturals, x\geq 24,~ \mbox{and $x\not\in Pink$}\}$.

Then by the well-ordering property, $Blue$ has a smallest element,
$s$. Now let $4pinks=\{24, 25, 26,27\}$. Then $x\in 4pinks
\longrightarrow x\in Pink$, since we can write:
\begin{eqnarray*}
24&=&6\cdot 4\\
25&=&4^2+9\\
26&=&2 \cdot 4+2\cdot 9\\
27&=&3\cdot 9
\end{eqnarray*}
So, $s$ must be $\geq 28$.
Since $s$ is the smallest element in {\em Blue}, we have $s' =  s-4 \geq 24$, 
and $s' \in Pink$. But, 
\[
~~s' \in Pink~~ \longrightarrow ~~ s' + 4 \in Pink ~~\longrightarrow s\in Pink
\]
since $s'+4$ is the sum of 
perfect squares $\geq 2$. But it cannot be that $s\in Blue$, and $s\in Pink$,
since {\em Blue $\cap$ Pink $=\emptyset$}. Contradiction!  
Hence, {\em Blue} is indeed empty, and so every natural number $\geq 24$ is 
{\em pink}.
\end{proof}
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

\bparts
\ppart We do not have enough base cases to support the claim. The proof
breaks down when we assume $2^1=3^1$ by the induction hypothesis, which
had to be shown to be true as a base case.
\ppart The inductive hypothesis is involed wrongly in the inductive
step. $n+1$ need not be composite; it could very well be a prime.
\eparts

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

\end{problems}

\begin{center}
\large \bf Some common mistakes in your solutions
\end{center}

{\bf Problems 1 and 2:} 
\begin{itemize} 
\item some students gave extraneous base cases.
\item a few forgot to argue the base case.
\item a few refered to $P(n)$ without defining it.
\end{itemize}
{\bf Problem 3:} 
\begin{itemize}
\item several people forgot the $a_1=a_2$ case.
\item a few people forgot to define a base case.
\end{itemize}
{\bf Problem 4:} 
\begin{itemize}
\item almost everyone used circular reasoning.
\item a few assumed that a $2^n\times 2^n\times 2^n$ block with one 
cubic foot missing could be built without
offerring any proof of it.
\end{itemize}
{\bf Problem 5:} 
\begin{itemize}
\item several students just gave a few examples and didn't use induction.
\item some people forgot the base case.
\item several people identified steps that violated the {\em $3,4$-tree} 
property as valid construction steps in their inductive argument.
\end{itemize}
{\bf Problem 6:} 
\begin{itemize}
\item a few people just gave a few examples but didn't prove it.
\item a few displayed a fundamental lack of understanding of 
the well-ordering principle.
\end{itemize}
{\bf Problem 7:} 
\begin{itemize}
\item some people said ``the math was wrong'', {\em i.e.}, $2^1\not = 3^1$,
$\log_2{n}\not = 0$ if $n\not = 0$, therefore the proof was false.
\item several people showed that the theorem was false, not that the
proof was invalid.
\end{itemize}

\end{document}





