100
Proofs, Induction, and Number Theory
If a counterexample is not forthcoming, perhaps the conjecture is true and we
should try to prove it. What techniques can we use to try to do this? For the rest of
this section, we’ll examine various methods of attacking a proof.
Exhaustive Proof
While “disproof by counterexample” always works, “proof by example” seldom
does. The one exception to this situation occurs when the conjecture is an assertion about a finite collection. In this case, the conjecture can be proved true by
showing that it is true for each member of the collection. proof by exhaustion
means that all possible cases have been exhausted, although it often means that
the person doing the proof is exhausted as well!
tAbLe 2.1
number
Divisible by 6
Divisible by 3
1
no
2
no
3
no
4
no
5
no
6
yes: 6 = 1 × 6
yes: 6 = 2 × 3
7
no
8
no
9
no
10
no
11
no
12
yes: 12 = 2 × 6
yes: 12 = 4 × 3
13
no
14
no
15
no
16
no
17
no
18
yes: 18 = 3 × 6
yes: 18 = 6 × 3
19
no
20
no
eXAMPLe 2
Prove the conjecture, “If an integer between 1 and 20 is divisible by 6, then it is
also divisible by 3.” (“Divisible by 6,” means, “evenly divisible by 6,” that is, the
number is an integral multiple of 6.)
Because there is only a finite number of cases, the conjecture can be proved
by simply showing it to be true for all the integers between 1 and 20. Table 2.1 is
the proof.