Page 123 - Discrete Mathematics and Its Applications

102 1 / The Foundations: Logic and Proofs
EXAMPLE 17
Looking for Counterexamples
In Section 1.7 we introduced the use of counterexamples to show that certain statements are
false. When confronted with a conjecture, you might first try to prove this conjecture, and if
your attempts are unsuccessful, you might try to find a counterexample, first by looking at
the simplest, smallest examples. If you cannot find a counterexample, you might again try to
prove the statement. In any case, looking for counterexamples is an extremely important pursuit,
which often provides insights into problems. We will illustrate the role of counterexamples in
Example 17.
In Example 14 in Section 1.7 we showed that the statement “Every positive integer is the sum of
two squares of integers” is false by finding a counterexample. That is, there are positive integers
that cannot be written as the sum of the squares of two integers. Although we cannot write every
positive integer as the sum of the squares of two integers, maybe we can write every positive
integer as the sum of the squares of three integers. That is, is the statement “Every positive
integer is the sum of the squares of three integers” true or false?
Solution: Because we know that not every positive integer can be written as the sum of two
squares of integers, we might initially be skeptical that every positive integer can be written as
the sum of three squares of integers. So, we first look for a counterexample. That is, we can
show that the statement “Every positive integer is the sum of three squares of integers” is false
if we can find a particular integer that is not the sum of the squares of three integers. To look
for a counterexample, we try to write successive positive integers as a sum of three squares.
2 2 2 2 2 2 2 2 2 2 2 2
We find that 1 = 0 + 0 + 1 ,2 = 0 + 1 + 1 ,3 = 1 + 1 + 1 ,4 = 0 + 0 + 2 ,5 =
2
2
2
2
2
2
0 + 1 + 2 ,6 = 1 + 1 + 2 , but we cannot find a way to write 7 as the sum of three
squares. To show that there are not three squares that add up to 7, we note that the only possible
squares we can use are those not exceeding 7, namely, 0, 1, and 4. Because no three terms where
each term is 0, 1, or 4 add up to 7, it follows that 7 is a counterexample. We conclude that the
statement “Every positive integer is the sum of the squares of three integers” is false.
We have shown that not every positive integer is the sum of the squares of three integers.
The next question to ask is whether every positive integer is the sum of the squares of four
positive integers. Some experimentation provides evidence that the answer is yes. For example,
2
2
2
2
2
2
2
2
2
2
2
2
7 = 1 + 1 + 1 + 2 ,25 = 4 + 2 + 2 + 1 , and 87 = 9 + 2 + 1 + 1 . It turns out the
conjecture “Every positive integer is the sum of the squares of four integers” is true. For a proof,
see [Ro10]. ▲
Proof Strategy in Action
Mathematics is generally taught as if mathematical facts were carved in stone. Mathematics
texts (including the bulk of this book) formally present theorems and their proofs. Such presen-
tations do not convey the discovery process in mathematics. This process begins with exploring
concepts and examples, asking questions, formulating conjectures, and attempting to settle these
conjectures either by proof or by counterexample. These are the day-to-day activities of math-
ematicians. Believe it or not, the material taught in textbooks was originally developed in this
way.
People formulate conjectures on the basis of many types of possible evidence. The exam-
ination of special cases can lead to a conjecture, as can the identification of possible patterns.
Altering the hypotheses and conclusions of known theorems also can lead to plausible conjec-
tures. At other times, conjectures are made based on intuition or a belief that a result holds.
No matter how a conjecture was made, once it has been formulated, the goal is to prove or
disprove it. When mathematicians believe that a conjecture may be true, they try to find a proof.
If they cannot find a proof, they may look for a counterexample. When they cannot find a coun-
terexample, they may switch gears and once again try to prove the conjecture. Although many
conjectures are quickly settled, a few conjectures resist attack for hundreds of years and lead to