\documentclass[11pt, twoside]{article}

\usepackage{epsf}

\input{macros-course}

\newcommand{\nand}{|}
\renewcommand{\implies}{\longrightarrow}
\askaboutsolutions

\begin{document}
\psol{2}{September 19, 2000}

\textbf{Self-study:}
Read:  Rosen, \textit{Discrete Mathematics and Its Applications}, 
Section 2.3 up to p. 122 \\
Self-study problems: (not to be handed in) Rosen, Section 2.3, exercises 1, 5, 7, 9, 11, 15,
29, 31, 33, 35, 37 \\

Note:  The self-study reading covers basic mathematical topics that we
will not explicitly cover in lecture.
We recommend that you read them and discuss any topics that are
unclear to you with your TA during the weekly tutorial.
The self-study problems are intended for you to get some practice with
the mathematical topics covered by the self-study readings.
The weekly mini-quiz will be based on that week's self-study reading
and/or problems.

-----------------------------------------------------------------------------\\
\textbf{Reading:} 
Velleman, \textit{How to Prove It}, Chapter 2; Sections 3.3, 6.1-6.4 \\
Rosen, Sections 1.1, 3.1-3.3 


\medskip
\begin{problems}

\problem
%Basic predicate manipulations
%Predicate and quantifier logic proofs

\ppart Rosen 1.3, 24 (c), (d), (e)

\solution{
\medskip
\textbf{Solutions:}
Using the transformations on page 33 of Rosen, de Morgan's laws, and the fact that $\neg \neg x = x$:\\
%% a. $\forall y \forall x \neg P(x, y)$\\
%% b. $\exists x \forall y \neg P(x, y)$\\
c. $\forall y (\neg Q(y) \vee \exists x R(x,y))$\\
d. $\forall y (\forall x \neg R(x,y) \wedge \exists x \neg S(x,y)$\\
e. $\forall y (\exists x \forall z \neg T(x, y,z) \wedge \forall x \exists z \neg U(x, y, z)$}
\ppart Rosen 1.3, 34

\solution{
\medskip
\textbf{Solutions:}\\
a. $\forall x (P(x) \implies \neg S(x))$\\
b. $\forall x (R(x) \implies S(x))$\\
c. $\forall x (Q(x) \implies P(x))$\\
d. $\forall x (Q(x) \implies \neg R(x))$\\
e. Yes. \\  
   Combine c and a to get (1): $\forall x (Q(x) \implies \neg S(x))$.\\
   Then, take the contrapositive of b to get (2): $\forall x (\neg S(x) \implies \neg R(x)).$
   Finally, combine (1) and (2) to get $\forall x (Q(x) \implies \neg R(x))$, which is statement d. Hence d follows from a, b, and c.
}

\ppart Rosen 1.3, 52

\solution{
\medskip
\textbf{Solution:}
$\forall \epsilon \in \mathbb{R}^{+} \exists N \in \mathbb{N}^{+} \forall n \in
\mathbb{N}^{+} (n > N \implies | a_n - L | < \epsilon)$   
} 
 
\problem
% Explicit identification of EI, EG, UI, UG steps in a logical proof.

\ppart Give a formal reason for each starred line in the following structured 
proof. Refer to previous steps wherever you think that will be helpful in 
understanding your proof.

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Given:  $\forall x  \forall y [P(x) \vee Q(y)]$ \\
Prove:  $(\forall x  P(x)) \vee (\forall y Q(y))$ \\
1. Assume $\neg \forall x P(x)$ \\
2(*). $\exists x \neg P(x)$ \> \> \> \> \> \solution{ Negation of universal quantifier}\\
3(*). Choose $x_0$ such that $\neg P(x_0)$. \> \> \> \> \> \solution{ Existential Instantiation }\\
4(*). $\forall y (P(x_0) \vee Q(y))$ \> \> \> \> \> \solution{ Universal Instantiation of hypothesis}\\
5. $\forall y Q(y)$ \\
\> 1. Pick an arbitrary $y_0$ \\
\> 2(*). $P(x_0) \vee Q(y_0)$  \> \> \> \> \solution{ Universal Instantiation, using 4.}\\
\> 3(*). $Q(y_0)$ \> \> \> \>  \solution{ Propositional reasoning, using 5.2. and 3.}\\
\> 4(*). QED ($\forall y Q(y)$) \> \> \> \> \solution{ Universal Generalization }\\
6(*). QED ($(\forall x  P(x)) \vee (\forall y Q(y))$) \> \> \> \> \> \solution{ Propositional reasoning, using 5.  
			  ($B \implies A \vee B$)}\\
\end{tabbing}
\ppart
Write your own structured proof of the other direction, complete with reasons:
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Given:  $(\forall x  P(x)) \vee (\forall y Q(y))$ \\
Prove:  $\forall x  \forall y [P(x) \vee Q(y)]$ \\
\solution{
\medskip
\textbf{Solution:}\\
1. First, we will prove $(\forall x  P(x)) \implies \forall x \forall y [P(x) \vee Q(y)]$\\
 \> 1. Assume $\forall x P(x)$ \\
 \> 2. To prove 1, use 1.1 to prove $\forall x \forall y [P(x) \vee Q(y)]$ \\
 \> \> 1. Pick an arbitrary $x_0$, $y_0$ \\
 \> \> 2. $P(x_0)$ 
 \> \> \> Universal Instantiation, from 1.1. \\
 \> \> 3. $P(x_0) \vee Q(y_0)$ 
       \> \> \> Propositional reasoning, from 1.2.2 \\
 \> \> 4. QED
       \> \> \> Universal Generalization \\
 \> 3. QED 
    \> \> \> \> Implication\\
 2. Next, prove $(\forall y  Q(y)) \implies \forall x \forall y [P(x) \vee Q(y)]$ 
 \> \> \> \> \> Similar argument to the one for 1. \\
 3. Combine 1 and 2 to get $[(\forall x  P(x)) \vee (\forall y Q(y))] \implies [\forall x  \forall y [P(x) \vee Q(y)]]$ \\
 \> \> \> \> \> Cases\\
 4. QED
 \> \> \> \> \> Modus ponens, from 3. and ``Given''.
}
\end{tabbing}
\problem
% Ordinary induction, sum of series
Rosen 3.2, exercise 16.

\solution{
\medskip
\textbf{Solution:}
The proof is by induction.
Let $P(n)$ be the proposition that $1 \cdot 2 \cdot 3 + 2 \cdot 3 \cdot 4 + 
\ldots + n(n+1)(n+2) = \frac {n(n+1)(n+2)(n+3)}{4}$. \\
Base case: $n=1. 1 \cdot 2 \cdot 3 = 6; \frac {1(2)(3)(4)}{4} = 6.$ \\
Inductive step: By our inductive hypothesis, $1 \cdot 2 \cdot 3 + \ldots + 
n(n+1)(n+2) = \frac {n(n+1)(n+2)(n+3)}{4}$. Adding $(n+1)(n+2)(n+3)$ yields\\ 
\begin{eqnarray*}
\lefteqn{1 \cdot 2 \cdot 3 + \ldots + n(n+1)(n+2) +
(n+1)(n+2)(n+3)}\hspace{1.5in}  \\ 
& \mbox{}& \\
& = & \frac {n(n+1)(n+2)(n+3)}{ 4} + (n+1)(n+2)(n+3)\\
& = &\frac {n(n+1)(n+2)(n+3)}{4} + \frac {4(n+1)(n+2)(n+3)}{4}\\
& = &\frac {(n+4)(n+1)(n+2)(n+3)}{4}
\end{eqnarray*}
Hence $P(n) \implies P(n+1)$. QED. 
}
\problem
% Ordinary induction, divisibility
Velleman 6.1, problem 7
\solution{
\medskip

\textbf{Solution:}
The proof is by induction.
Let P(n) be the proposition that $64 | 9 ^ {n}-8n-1$.\\
Base case: $n = 1$. $9^n-8n-1=9-8-1=0$. $64 | 0$.\\
Inductive step: We must prove that $64 | 9 ^{n+1} -8(n+1)-1$.\\
\begin{eqnarray*}
9 ^{n+1} - 8(n+1) -1 & = & 9 ^{n+1} - 8n -9\\
& = & 9 (9 ^{n} -1) -8n\\
& = & 9 (9 ^{n} -1) -72n + 64n\\
& = & 9 (9 ^{n} -8n -1) + 64n\\
\end{eqnarray*}
Clearly, $64 | 64n$, and we know $ 64 | 9 ^{n} -8n -1$ from the 
inductive hypothesis. Hence 

\[ 64 | 9 ^{n+1} -8(n+1)-1 .\] 

So $P(n) \implies P(n+1)$. QED.
}
%% \problem
% Ordinary induction, inequalities
%% Velleman 6.1, problem 10, parts (a), (b), and (c).

\problem
% Ordinary induction, tiling
Velleman 6.2, problem 6
% Sorry -- I have no program handy to draw proper diagrams for this problem,
% and I don't know how to insert them in a LaTeX document. Not for the first
% time, I wonder why we can't just do these in Word...
% Anyway, if someone could insert some properly drawn figures, I think that
% is pretty much essential to understanding the solution.
\solution{
\medskip

\textbf{Solution:}
The proof is by induction.\\
Let P(n) be the proposition that any equilateral triangle, that is cut into 
$4^n$ congruent equilateral triangles with one corner removed, can be tiled 
using tiles composed of three of the smaller congruent triangles.\\
Base case: $n=1$. With one corner removed, a single tile can be used to cover
the remaining area.\\
%\mbox{\epsfbox{figures/ps2P5BaseCase.ps}}
Inductive step: Consider a triangle, called T, cut into $4^{n+1}$ congruent equilateral
triangles. We can think of this triangle as being cut into four smaller 
equilateral triangles, which are each then cut into $4^n$ equilateral 
triangles. Remove the top corner of T. We know that we can tile the triangle
that contains the removed corner by the inductive hypothesis. Note that the
remaining area contains three triangles, who have corners that meet in the same
place; namely, the bottom of T, directly below the removed corner. If we
consider each of these triangles with the touching corners removed, then the
inductive hypothesis says that we can tile each one separately. To complete
the tiling, simply use a single tile to cover the three adjacent removed 
corners. See Figure 1.
\begin{figure}
\centering
\mbox{\epsfbox{figures/ps2P5inductive.ps}}
\caption{\textbf{Figure 1:} The original triangle T. Dark lines indicate borders of the four smaller triangles; light lines indicate borders of the $4^n$ triangles that the smaller triangles are cut into. The black triangle is the removed corner; the gray triangles indicate the corners that are removed from the smaller triangles in order to apply the inductive hypothesis, which are then covered by a single tile.}
\end{figure}
\\
\\
\\
}

\problem
% Strong induction 
\ppart What is the smallest natural number $h$ such that towers of all heights
greater than or equal to $h$ can be built out of blocks of height 5,
6, and 9?

\solution {
\medskip
\textbf{Solution:}
14.} 
\ppart Prove that $h$ is the smallest such number.

\solution{
\medskip
\textbf{Solution:}
 This question has two parts: prove that $h$ satisfies the requirement, and
 prove that no smaller number also satisfies the requirement. The first part
 is asked in part c. To prove the second part, we show that a tower
 of height 13 cannot be made with our given blocks, via a case
 analysis.  Observe that if there were a way to build a tower of
 height 13, then this tower could have at most two blocks of heights 5
 or 6.  If there were more blocks of these heights, then the tower
 would be too long.  Similarly, any valid solution can have at most
 one block of height 9.  We can enumerate all the possible
 configurations consisting of at most two blocks of height 5 or
 6, and at most one block at height 9, and check that none of them add
 up to thirteen.  We can actually eliminate many of these cases.   

 Hence no natural number
 equal to or less than 13 satisfies the given requirements. Therefore, if 14
 does satisfy the requirements, it must be the smallest such number.}
\ppart Prove that all heights $h$ or greater can be built of of blocks
of height 5, 6, and 9.

\solution{
\medskip
\textbf{Solution:}
 The proof is by strong induction.
 Let P(n) be the proposition that all natural numbers,
 starting with our smallest base case, going up to and including n, can be 
 formed by adding 5, 6, and 9.
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Base cases: 14 is formed by 5+9.\\
 \> 15 is formed by 6+9 (or 5+5+5).\\
 \> 16 is formed by 5+5+6.\\
 \> 17 is formed by 5+6+6.\\
 \> 18 is formed by 9+9 (or 6+6+6).\\
\end{tabbing}
Inductive step: Assume P(n) to prove P(n+1). Note that we have proved P(n) 
true for five consecutive base cases. Hence, by our inductive hypothesis, 
we can always create a tower of height n+1-5. We can then simply add a block 
of height 5 to that tower, creating a tower of height n+1. P(n) $\implies$ P(n+1). QED.
}
\problem
% Strong induction, recursive definitions (Fibonacci)
Velleman 6.4, problem 5 (a) (d) \\
{Note:} By convention, the book considers $F_1$ to be 1, $F_2$ to be 1, $F_3$
to be 2, and so on. In other places, you may see $F_0 = 1, F_1 = 1, F_2 = 2$,
etc.
\\

\solution{
\medskip
\textbf{Solutions:}\\
\textbf{(a)} The proof is by induction. 
Let $P(n)$ be the proposition that $\sum_{i=0}^n F_i = F_{n+2} - 1$.\\ 
Base case: $n=1$. 
\begin{eqnarray*}
\sum_{i=0}^1 F_i & = & F_0 + F_1\\
		& = & F_1\\
		& = & 1\\
		& = & 2 - 1\\
		& = & F_3 - 1\\
		& = & F_{1+2} -1\\
\end{eqnarray*}
Inductive step: We must prove $\sum_{i=0}^{n+1} F_i = F_{n+3} - 1$.
\begin{eqnarray*}
\sum_{i=0}^{n+1} F_i & = & \sum_{i=0}^n F_i + F_{n+1}\\
& = & F_{n+2} - 1 + F_{n+1} \mbox {    by the inductive hypothesis}\\
& = & F_{n+3} - 1 \mbox {    by the definition of $F_n$}\\
\end{eqnarray*}

$P(n) \implies P(n+1)$. QED.

\iffalse  %% COMMENTS OUT EVERYTHING UNTIL THE \fi COMMAND%%

\textbf{(c)}  The proof is by induction.
Let $P(n)$ be the proposition that $\sum_{i=0}^n F_{2i+1} = F_{2n+2}$.\\
Base case: $n = 1.$ 
\begin{eqnarray*}
\sum_{i=0}^1 F_{2i+1} & = & F_1 + F_3\\
		& = & 1 + 2 \\
		& = & 3\\
		& = & F_4\\
\end{eqnarray*}
Inductive step: We must prove $\sum_{i=0}^{n+1} F_{2i+1} = F_{2n+4}$.
\begin{eqnarray*}
\sum_{i=0}^{n+1} F_{2i+1} & = & \sum_{i=0}^n F_{2i+1} + F_{2n+3}\\
& = & F_{2n+2} + F_{2n+3} \mbox {    by the inductive hypothesis}\\
& = & F_{2n+4} \mbox {    by the definition of $F_n$}\\
\end{eqnarray*}
$P(n) \implies P(n+1)$. QED.

\fi
%% STOP COMMENTING EVERYTHING OUT.

\textbf{(d)}  We can construct the following table:
\begin{eqnarray*}
n & F_n & \sum_{i=0}^n F_{2i}\\
1 & 1   & 1\\
2 & 1    & 4\\
3 & 2    & 12\\
4 & 3    & 33\\
5 & 5    \\
6 & 8    \\
7 & 13   \\
8 & 21   \\
9 & 34   \\
\end{eqnarray*}
Hmm. It looks like $\sum_{i=0}^n F_{2i}$ might be $F_{2n+1} -1$. So let's take
a crack at proving that.\\

The proof is by induction.\\
Let $P(n)$ be the proposition that $\sum_{i=0}^n F_{2i} = F_{2n+1} - 1$.\\
Base case: n = 1. 
\begin{eqnarray*}
\sum_{i=0}^n F_{2i} & = & F_0 + F_2\\
		& = & F_2\\
		& = & 1\\
		& = & 2 - 1\\
		& = & F_3 - 1\\
\end{eqnarray*}
Inductive step: We must prove $\sum_{i=0}^{n+1} F_{2i} = F_{2n+3} - 1$.
\begin{eqnarray*}
\sum_{i=0}^{n+1} F_{2i} & = & \sum_{i=0}^n F_{2i} + F_{2n +2}\\
& = & F_{2n+1} -1 + F_{2n+2} \mbox {    by the inductive hypothesis}\\
& = & F_{2n+3} -1 \mbox {    by the definition of $F_n$}\\
\end{eqnarray*}
$P(n) \implies P(n+1)$. QED.

\iffalse  %% START COMMENTING OUT EVERYTHING UNTIL \fi command %%

\textbf{(e)}  The proof is by strong induction on n. (surprise!)\\
Let $P(n)$ be the proposition that $F_{m+n} = F_{m-1}F_n + F_mF_{n+1}$ for all
natural numbers $\leq$ n.\\
Base case: n = 1.
\begin{eqnarray*}
F_{m+n} & = & F_{m+1}\\
	& = & F_{m-1} + F_m \mbox {    by the definition of $F_n$}\\
	& = & F_{m-1}(1) + F_m(1)\\
	& = & F_{m-1}F_1 + F_mF_2\\
\end{eqnarray*}
Inductive step: We must prove $F_{m+n+1} = F_{m-1}F_{n+1} + F_mF_{n+2}$.
\begin{eqnarray*}
F_{m+n+1} & = & F_{m+n} + F_{m+n-1} by the definition of F_n\\
& = & (F_{m-1}F_n + F_mF_{n+1}) + (F_{m-1}F_{n-1} + F_mF_{n}) \mbox {     by the inductive hypothesis}\\
& = & F_{m-1}(F_n + F_{n-1}) + F_m(F_{n+1} + F_{n})\\
& = & F_{m-1}F_{n+1} + F_mF_{n+2} \mbox {    by the definition of $F_n$}\\
\end{eqnarray*}
$P(n) \implies P(n+1)$. QED.
}

\fi
%%  END COMMENTING OUT.

\end{problems}

\end{document}

