Page 110 - Discrete Mathematics and Its Applications

1.7 Introduction to Proofs 89

Mistakes in Proofs

There are many common errors made in constructing mathematical proofs. We will briefly
describe some of these here.Among the most common errors are mistakes in arithmetic and basic
algebra. Even professional mathematicians make such errors, especially when working with
complicated formulae.Whenever you use such computations you should check them as carefully
as possible. (You should also review any troublesome aspects of basic algebra, especially before
you study Section 5.1.)
Each step of a mathematical proof needs to be correct and the conclusion needs to follow
logically from the steps that precede it. Many mistakes result from the introduction of steps that
do not logically follow from those that precede it. This is illustrated in Examples 15–17.

EXAMPLE 15 What is wrong with this famous supposed “proof” that 1 = 2?

“Proof:" We use these steps, where a and b are two equal positive integers.

Step Reason
1. a = b Given
2
2. a = ab Multiply both sides of (1) by a
2
2
2
3. a − b = ab − b 2 Subtract b from both sides of (2)
4. (a − b)(a + b) = b(a − b) Factor both sides of (3)
5. a + b = b Divide both sides of (4) by a − b
6. 2b = b Replace a by b in (5) because a = b
and simplify
7. 2 = 1 Divide both sides of (6) by b
Solution: Every step is valid except for one, step 5 where we divided both sides by a − b. The
error is that a − b equals zero; division of both sides of an equation by the same quantity is
valid as long as this quantity is not zero. ▲

EXAMPLE 16 What is wrong with this “proof?”
2
“Theorem:” If n is positive, then n is positive.

2
“Proof:" Suppose that n is positive. Because the conditional statement “If n is positive, then
2
n is positive” is true, we can conclude that n is positive.

2
Solution: Let P(n) be “n is positive” and Q(n) be “n is positive.” Then our hypothesis is Q(n).
2
The statement “If n is positive, then n is positive” is the statement ∀n(P(n) → Q(n)). From
the hypothesis Q(n) and the statement ∀n(P(n) → Q(n)) we cannot conclude P(n), because
we are not using a valid rule of inference. Instead, this is an example of the fallacy of affirming
2
the conclusion. A counterexample is supplied by n =−1 for which n = 1 is positive, but n is
negative. ▲

EXAMPLE 17 What is wrong with this “proof?”
2
“Theorem:” If n is not positive, then n is not positive. (This is the contrapositive of the
“theorem” in Example 16.)