\problem\pts{32} \textbf{Proof Comprehension}

For each of the following proofs, determine whether it is valid or
invalid.  If it is valid, say so.  If it is invalid, what about the
proof is incorrect?  (NOTE:  If you say a proof is valid, feel free
to give some explanation for why you think that proof is valid.  This
may give you some partial credit if you are incorrect.)

\begin{problemparts}

\problempart {\bf (8 points)}  

\begin{tabbing}
Theorem: 2 = 1.  \\
Proof:\\
1.  Assume $2 = 1$.\\
2.  $x^2 + 2 = x^2 + 1$.\\
3.  $2x dx = 2x dx$.  (differentiating both sides)\\
4.  $2 = 2$  (dividing both sides by $x dx$)\\
5.  Therefore, $2 = 1$ (QED)
\end{tabbing}

\solution{
\bigskip {\bf Solution: }
Step 5 is invalid.  After step 4 we have proven that $(2 = 1) \rightarrow
(2 = 2)$.  This is an implication, and is true even if $2 \neq 1$.  So
we can't conclude that $2 =1$.  This is known as the fallacy of affirming
the conclusion.
}

\smallspace

\problempart {\bf (8 points)}  

\begin{tabbing}
Theorem:  All rational numbers $x$ greater than
or equal to 1 are such that $x \leq 2^x$.\\
Proof:  Let $P(n)$ be the statement ``$n \leq 2^n.$''\\
1.  We know that $1 \leq 2^1 = 2$.  Therefore, $P(1)$.\\
2.  Assume $P(n)$ where $n \geq 1$.\\
3.  Then, $n \leq 2^n$\\
4.  Adding $1$ to both sides, we get $n + 1 \leq 2^n + 1$\\
5.  Substituting that $1 \leq n$, we get $n + 1 \leq 2^n + n$.\\
6.  Substituting from step 3 into the RHS of step 5, we get $n+1 \leq
    2^n + 2^n$\\
7.  Simplifying, we get $n+1 \leq 2^{n+1}$.\\
8.  Thus, $P(n+1)$.  Therefore, by induction, $\forall n P(n)$.
\end{tabbing}

\solution{ 
\bigskip {\bf Solution: }
This proof is invalid.  Step 7 is invalid, since $\forall n
P(n)$ would be a statement about the rational numbers (since that was
the statement of the theorem), but induction allows us to conclude only
that $\forall n \in {\Bbb N} \; P(n)$.  }

\nextproblem

\problempart {\bf (8 points)} 

Theorem: If $G$ is a finite graph with
positive integer-weighted edges that has a spanning tree, it has a 
minimal spanning tree (a spanning tree $T$ such that the
sum of the weights of the edges in $T$ is as small as it could be
for any spanning tree).

Proof:  Every spanning tree of $G$ has a total weight $w$ which is
non-negative integer.  Therefore, the set of possible total weights of
spanning trees is a subset of the non-negative integers.  By the
well-ordering property, since there is a spanning tree, there must be
a least weight of a spanning tree, and therefore there must be a
spanning tree that has that weight.  Thus, there is a minimal spanning
tree.

\solution{
\bigskip {\bf Solution: }
This proof is valid.  
}

\problempart {\bf (8 points)} 

Theorem: There are infinitely many prime numbers.

Proof: Let $S$ be the set of all prime numbers.  Now let $k = 1 +
\prod_{p \in S} p$.  Note that $k$ is not divisible by any $p$ in $S$
since the remainder when dividing by $p$ would be 1.  Furthermore,
notice that if $p$ is any element of $S$ then $k = 1 + \prod_{q \in S}
q \geq 1 + p > p$.  But this is a contradiction.  Therefore, there
must be infinitely many prime numbers.

\solution{
\bigskip {\bf Solution: }
The proof is sloppy enough to be considered invalid.

This is basically just like the classical proof that there are
infinitely many primes, but it's sloppily done.  Here are the two
significant problems with the proof, from minor objections to major
ones.

1.  The author never explains why what has been derived about $k$
causes something new to be prime.  It should be mentioned that either
$k$ must be prime, or it must contain a prime factor not in $S$, which
is what creates the contradiction.  This is a serious omission, but
since this omission could just be filled in, it is not something bad
enough to make the proof invalid.

2.  Most importantly, the author never includes the assumption that
$S$ is finite.  If $S$ is infinite, the whole argument falls apart
since $k$ would not be a number and so everything that's reasoned
about $k$ would be invalid.  This is serious enough that the proof
is not valid without it.

}

\nextproblem

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Fall 1998 Midterm
% Added by George
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem {\bf (10 points)} Define the matrix

\begin{eqnarray*}
M & = & \left[
\begin{array}{cc}
0 & 1 \\
1 & 1
\end{array}
\right].
\end{eqnarray*}

Let $M^n$ denote the product of $n$ copies of the matrix $M$.  Use
ordinary induction to prove that for all $n \geq 1$, the upper right
entry of $M^n$ is $F_n$, the $n$-th Fibonacci number.  State your
inductive hypothesis clearly.

For reference, the standard formula for the product of $2 \times 2$
matrices is given below.

\begin{eqnarray*}
\left[
\begin{array}{cc}
a & b \\
c & d
\end{array}
\right]
\cdot
\left[
\begin{array}{cc}
e & f \\
g & h
\end{array}
\right]
& = &
\left[
\begin{array}{cc}
ae + bg & af + bh \\
ce + dg & cf + dh
\end{array}
\right]
\end{eqnarray*}

Recall that $F_0 = 0$, $F_1 = 1$, $F_2 = 1$, $F_3 = 2$, \ldots.

\solution{
\begin{proof}
The proof is by induction.  Let $P(n)$ be the proposition that

\begin{eqnarray*}
M^n & = & \left[
\begin{array}{cc}
F_{n-1} & F_n \\
F_n & F_{n+1}
\end{array}
\right].
\end{eqnarray*}

In the base case, $P(1)$ is true because

\begin{eqnarray*}
M^1 & = & 
\left[
\begin{array}{cc}
0 & 1 \\
1 & 1
\end{array}
\right] \\
& = &
\left[
\begin{array}{cc}
F_0 & F_1 \\
F_1 & F_2
\end{array}
\right].
\end{eqnarray*}
\end{proof}

In the inductive step, for $n \geq 1$ assume $P(n)$ to prove $P(n+1)$.
The following equalities hold.

\begin{eqnarray*}
M^{n+1} & = &   M^n \cdot M \\
    & = &   \left[
        \begin{array}{cc}
        F_{n-1} & F_n \\
        F_n & F_{n+1}
        \end{array}
        \right] \cdot
        \left[
        \begin{array}{cc}
        0 & 1 \\
        1 & 1
        \end{array}
        \right] \\
    & = &   \left[
        \begin{array}{cc}
        F_n & F_{n-1} + F_n \\
        F_{n+1} & F_n + F_{n+1}
        \end{array}
        \right] \\
    & = &   \left[
        \begin{array}{cc}
        F_n & F_{n+1} \\
        F_{n+1} & F_{n+2}
        \end{array}
        \right]
\end{eqnarray*}

The first step uses the definition of $M^n$.  The second step uses the
induction hypothesis and the definition of the matrix $M$.  We carry
out a matrix multiplication in the third step and use the Fibonacci
recurrence in the last step.  This shows that $P(n)$ implies $P(n+1)$,
and the claim is proved by induction.
}