Section 2.1 Proof Techniques
99
To Prove or Not to Prove
A textbook will often say, “Prove the following theorem,” and the reader will
know that the theorem is true; furthermore, it is probably stated in its most polished form. But suppose you are doing research in some subject. You observe a
number of cases in which whenever P is true, Q is also true. On the basis of these
experiences, you may formulate a conjecture: P S Q. The more cases you find
where Q follows from P, the more confident you are in your conjecture. This process illustrates inductive reasoning, drawing a conclusion based on experience.
No matter how reasonable the conjecture sounds, however, you will not be
satisfied until you have applied deductive reasoning to it as well. In this process, you try to verify the truth or falsity of your conjecture. You produce a proof
of P S Q (thus making it a theorem), or else you find a counterexample that
disproves the conjecture, a case in which P is true but Q is false. (We were using
deductive reasoning in predicate logic when we either proved that a wff was valid
or found an interpretation in which the wff was false.)
If you are simply presented with a conjecture, it may be difficult to decide
which of the two approaches you should try—to prove the conjecture or to disprove it! A single counterexample to a conjecture is sufficient to disprove it. Of
course, merely hunting for a counterexample and being unsuccessful does not
constitute a proof that the conjecture is true.
ReMinDeR
One counterexample is
enough to disprove a
conjecture.
PrACTiCe 1 Provide counterexamples to the following conjectures.
a. All animals living in the ocean are fish.
b. Every integer less than 10 is bigger than 5.
■
eXAMPLe 1
For a positive integer n, n factorial is defined as n(n − 1)(n − 2) c 1, and is denoted
by n!. Prove or disprove the conjecture, “For every positive integer n, n! ≤ n
2
.”
Let’s begin by testing some cases:
n
n!
n
2
n! ≤ n
2
1
1
1
yes
2
2
4
yes
3
6
9
yes
So far, this conjecture seems to be looking good. But for the next case,
n
n!
n
2
n! ≤ n
2
4
24 16
no
we have found a counterexample. The fact that the conjecture is true for n = 1, 2,
and 3 does nothing to prove the conjecture, but the single case n = 4 is enough to
disprove it.
99
To Prove or Not to Prove
A textbook will often say, “Prove the following theorem,” and the reader will
know that the theorem is true; furthermore, it is probably stated in its most polished form. But suppose you are doing research in some subject. You observe a
number of cases in which whenever P is true, Q is also true. On the basis of these
experiences, you may formulate a conjecture: P S Q. The more cases you find
where Q follows from P, the more confident you are in your conjecture. This process illustrates inductive reasoning, drawing a conclusion based on experience.
No matter how reasonable the conjecture sounds, however, you will not be
satisfied until you have applied deductive reasoning to it as well. In this process, you try to verify the truth or falsity of your conjecture. You produce a proof
of P S Q (thus making it a theorem), or else you find a counterexample that
disproves the conjecture, a case in which P is true but Q is false. (We were using
deductive reasoning in predicate logic when we either proved that a wff was valid
or found an interpretation in which the wff was false.)
If you are simply presented with a conjecture, it may be difficult to decide
which of the two approaches you should try—to prove the conjecture or to disprove it! A single counterexample to a conjecture is sufficient to disprove it. Of
course, merely hunting for a counterexample and being unsuccessful does not
constitute a proof that the conjecture is true.
ReMinDeR
One counterexample is
enough to disprove a
conjecture.
PrACTiCe 1 Provide counterexamples to the following conjectures.
a. All animals living in the ocean are fish.
b. Every integer less than 10 is bigger than 5.
■
eXAMPLe 1
For a positive integer n, n factorial is defined as n(n − 1)(n − 2) c 1, and is denoted
by n!. Prove or disprove the conjecture, “For every positive integer n, n! ≤ n
2
.”
Let’s begin by testing some cases:
n
n!
n
2
n! ≤ n
2
1
1
1
yes
2
2
4
yes
3
6
9
yes
So far, this conjecture seems to be looking good. But for the next case,
n
n!
n
2
n! ≤ n
2
4
24 16
no
we have found a counterexample. The fact that the conjecture is true for n = 1, 2,
and 3 does nothing to prove the conjecture, but the single case n = 4 is enough to
disprove it.