Page 117 - Discrete Mathematics and Its Applications

96 1 / The Foundations: Logic and Proofs

case is covered. The problem of proving a theorem is analogous to showing that a computer
program always produces the output desired. No matter how many input values are tested, unless
all input values are tested, we cannot conclude that the program always produces the correct
output.
EXAMPLE 8 Is it true that every positive integer is the sum of 18 fourth powers of integers?

Solution: To determine whether a positive integer n can be written as the sum of 18 fourth powers
of integers, we might begin by examining whether n is the sum of 18 fourth powers of integers
for the smallest positive integers. Because the fourth powers of integers are 0, 1, 16, 81,...,
if we can select 18 terms from these numbers that add up to n, then n is the sum of 18 fourth
powers. We can show that all positive integers up to 78 can be written as the sum of 18 fourth
powers. (The details are left to the reader.) However, if we decided this was enough checking,
we would come to the wrong conclusion. It is not true that every positive integer is the sum of
18 fourth powers because 79 is not the sum of 18 fourth powers (as the reader can verify). ▲

Another common error involves making unwarranted assumptions that lead to incorrect
proofs by cases where not all cases are considered. This is illustrated in Example 9.
EXAMPLE 9 What is wrong with this “proof?”
2
“Theorem:” If x is a real number, then x is a positive real number.
2
“Proof:" Let p 1 be “x is positive,” let p 2 be “x is negative,” and let q be “x is positive.” To
2
show that p 1 → q is true, note that when x is positive, x is positive because it is the product
2
of two positive numbers, x and x. To show that p 2 → q, note that when x is negative, x is
positive because it is the product of two negative numbers, x and x. This completes the proof.
Solution: The problem with this “proof” is that we missed the case of x = 0. When x = 0,
2
x = 0 is not positive, so the supposed theorem is false. If p is “x is a real number,” then
we can prove results where p is the hypothesis with three cases, p 1 , p 2 , and p 3 , where
p 1 is “x is positive,” p 2 is “x is negative,” and p 3 is “x = 0” because of the equivalence
p ↔ p 1 ∨ p 2 ∨ p 3 . ▲

Existence Proofs

Many theorems are assertions that objects of a particular type exist. A theorem of this type is a
proposition of the form ∃xP (x), where P is a predicate. A proof of a proposition of the form
∃xP (x) is called an existence proof. There are several ways to prove a theorem of this type.
Sometimes an existence proof of ∃xP (x) can be given by finding an element a, called a witness,
such that P(a) is true. This type of existence proof is called constructive. It is also possible
to give an existence proof that is nonconstructive; that is, we do not find an element a such
that P(a) is true, but rather prove that ∃xP(x) is true in some other way. One common method
of giving a nonconstructive existence proof is to use proof by contradiction and show that the
negation of the existential quantification implies a contradiction. The concept of a constructive
existence proof is illustrated by Example 10 and the concept of a nonconstructive existence
proof is illustrated by Example 11.
EXAMPLE 10 A Constructive Existence Proof Show that there is a positive integer that can be written as
the sum of cubes of positive integers in two different ways.

Solution: After considerable computation (such as a computer search) we find that
3
3
3
3
1729 = 10 + 9 = 12 + 1 .