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

%	\addtolength{\topmargin}{-.35in}
%	\setlength{\textheight}{9in}
\input psfig

\begin{document}

\pset{2}{September 10, 1996}{Start of Class, Tuesday, September 17, 1996}

{\bf Reading:} Sections 3.2-3.4.
Background: 2.3

\bigskip

\begin{problems}
\problem
%3.2-10

Prove that $1 \cdot 1! + 2 \cdot 2! + ... + n \cdot n! = (n+1)! - 1$ 
whenever $n$ is a positive integer.

\problem
%Simple inductive proof based on Fibonacci recursive definition.
%Also, a sum of series.
%Section 3.3-10

Prove that $f_1^2+f_2^2+...+f_n^2 = f_nf_{n+1}$, where  $f_n$ is the
{\em n}th Fibonacci number and $n$ is a positive integer.

\problem 
%3.3-18

Give a recursive definition of the functions {\em max} and {\em min} so that 
{\em max}$(a_1,a_2,...,a_n)$ and {\em min}$(a_1,a_2,...,a_n)$ are the maximum
and minimum of the $n$ numbers $a_1,a_2,...,a_n$, respectively.



\problem
%Nancy Lynch--Generalization of the tiling example to 3 dimensions.
The C.I.A. wants you design plans to build (for an arbitrary $k \geq 1$)
a $2^k \times 2^k \times 2^k$ cubic foot granite cube that is solid
except for a missing single cubic foot that is one of the eight cubic
feet nearest the center of the cube.
It will have one of its corners exactly at the center of the large
cube.
The C.I.A. is not telling you what is to be placed inside the cube.

You are to build this by cementing together {\em basic blocks} that
are 2-foot $\times$ 2-foot $\times$ 2-foot cubes, with one one-foot 
cube missing from its corner -- see the diagram below. 
\begin{figure}[h]
\centerline{\psfig{figure=cube.ps,height=1in}}
\end{figure}


Describe your method for doing this.  Your plans should be described
inductively on $k$.

%\problem
%algorithm verification
%On page 215 of the text, an iterative algoritm is given for finding the
%$n$th Fibonacci number.
%Consider the algorithm only for $n \geq 1$.
%Outline a proof by simple mathematical induction on $k$, that 
%after the $k$th iteration of the algorithm, $k \geq 0$:\\
%(a) The value of $x$ is $f_{k-1}$.\\
%(b) The value of $y$ is $f_k$.
%(For the case where $k = 0$, consider the point after the
%initialization of $x$ and $y$.)

%You do {\em not} need to use any of the program verification methods
%in Section 3.5.  Just argue informally, in words, about what happens
%to the values of $x$ and $y$ as a result of a single iteration.

\problem
%Nancy Lynch--[[[structural induction]]]
In a {\em $3,4$-tree}, every node is either a {\em leaf node} with no 
children, or an {\em internal node} with exactly $3$ or exactly $4$ children.

(a) What is the relationship between the number of edges and the
number of nodes in a $3,4$-tree?

(b) Prove your conjecture from (a) using structural induction,
that is, strong induction on the number $n$ of recursive formation 
steps needed to construct the tree.

%\problem
%Prove that the strong induction axiom implies the weak induction
%axiom.

\problem
% well ordering
Define a natural number to be {\em pink} if it is:
\begin{enumerate}
\item
Expressible as the sum of (not necessarily distinct) perfect squares
of numbers $\geq 2$,
\item
and it is $\geq 24$.
\end{enumerate}

(a) Characterize exactly what the pink numbers are.\\
(b) Prove your answer to (a), using well ordering.


\problem
%Mojdeh Mohtashemi
Find the fallacies in the proofs of the following theorems.

(a) {\em Theorem}: $2^n = 3^n$ for all natural numbern $n$.

{\em BASIS STEP}: $2^0 =  3^0 = 1$ by definition.

{\em INDUCTIVE STEP}: Assume that $2^k = 3^k$ for all natural numbers
$k \leq n$. Then 
\[
2^{n+1} = 2^n*2^1 = 3^n*3^1 = 3^{n+1}
\]
by inductive hypothesis.

(b) {\em Theorem}: $\log_2 n = 0$ for all natural numbers $n$.

{\em BASIS STEP}: $\log_2 1 = 0$ is true.

{\em INDUCTIVE STEP}: Assume that $\log_2 k = 0$ for all natural numbers
$k \leq n$, and show it is true for $n+1$. Write $n+1$ as a product of 
two natural numbers $p$ and $q$ so that we have:  
\[
\log_2 (n+1) = \log_2 (p.q) = \log_2 p +\log_2 q = 0 + 0 = 0  
\]
which is true by inductive hypothesis.

\end{problems}
\end{document}
