106
Proofs, Induction, and Number Theory
x + x = x we get 2x = x and, after subtracting x from both sides, x = 0. We then
have x = 0 and x ∙ 0, a contradiction. However, in this argument we never made
use of the assumption x ∙ 0; we actually proved directly that x + x = x implies
x = 0.
Another misleading claim of proof by contradiction occurs when we assume
P ` Q′ and are able to deduce P′ without using the assumption P. Then we assert
P ` P′ as a contradiction. What really happened here is a direct proof of Q′ S P′,
and we have constructed a proof by contraposition, not a proof by contradiction.
In both this case and the previous one, it is not that the proofs are wrong, just that
they are not proofs by contradiction.
Table 2.2 summarizes useful proof techniques we have discussed so far.
tAbLe 2.2
Proof technique
Approach to Prove P S Q Remarks
Exhaustive proof
Demonstrate P S Q for all
possible cases.
May be used only to prove
a finite number of cases.
Direct proof
Assume P, deduce Q.
The standard approach—
usually the thing to try.
Proof by contraposition Assume Q′, deduce P′.
Use this if Q′ as a hypothesis seems to give more
ammunition than P would.
Proof by contradiction Assume P ` Q′, deduce a
contradiction.
Use this when Q says
something is not true.
Serendipity
Serendipity means a fortuitous happening, or good luck. While this isn’t really
a general proof technique, some of the most interesting proofs come from clever
observations that we can admire, even if we would never have thought of them
ourselves. We’ll look at two such proofs, just for fun.
eXAMPLe 12
A tennis tournament has 342 players. A single match involves 2 players. The winner of a match plays the winner of a match in the next round, while losers are
eliminated from the tournament. The 2 players who have won all previous rounds
play in the final game, and the winner wins the tournament. Prove that the total
number of matches to be played is 341.
The hard way to prove this result is to compute 342/2 = 171 to get the number of matches in the first round, resulting in 171 winners to go on to the second
round. For the second round, 171/2 = 85 plus 1 left over; there are 85 matches
and 85 winners, plus the 1 left over, to go on to the third round. The third round
has 86/2 = 43 matches, and so forth. The total number of matches is the sum of
171 + 85 + 43 + c .
The clever observation is to note that each match results in exactly 1 loser, so
there must be the same number of matches as losers in the tournament. Because
there is only 1 winner, there are 341 losers and therefore 341 matches.
Proofs, Induction, and Number Theory
x + x = x we get 2x = x and, after subtracting x from both sides, x = 0. We then
have x = 0 and x ∙ 0, a contradiction. However, in this argument we never made
use of the assumption x ∙ 0; we actually proved directly that x + x = x implies
x = 0.
Another misleading claim of proof by contradiction occurs when we assume
P ` Q′ and are able to deduce P′ without using the assumption P. Then we assert
P ` P′ as a contradiction. What really happened here is a direct proof of Q′ S P′,
and we have constructed a proof by contraposition, not a proof by contradiction.
In both this case and the previous one, it is not that the proofs are wrong, just that
they are not proofs by contradiction.
Table 2.2 summarizes useful proof techniques we have discussed so far.
tAbLe 2.2
Proof technique
Approach to Prove P S Q Remarks
Exhaustive proof
Demonstrate P S Q for all
possible cases.
May be used only to prove
a finite number of cases.
Direct proof
Assume P, deduce Q.
The standard approach—
usually the thing to try.
Proof by contraposition Assume Q′, deduce P′.
Use this if Q′ as a hypothesis seems to give more
ammunition than P would.
Proof by contradiction Assume P ` Q′, deduce a
contradiction.
Use this when Q says
something is not true.
Serendipity
Serendipity means a fortuitous happening, or good luck. While this isn’t really
a general proof technique, some of the most interesting proofs come from clever
observations that we can admire, even if we would never have thought of them
ourselves. We’ll look at two such proofs, just for fun.
eXAMPLe 12
A tennis tournament has 342 players. A single match involves 2 players. The winner of a match plays the winner of a match in the next round, while losers are
eliminated from the tournament. The 2 players who have won all previous rounds
play in the final game, and the winner wins the tournament. Prove that the total
number of matches to be played is 341.
The hard way to prove this result is to compute 342/2 = 171 to get the number of matches in the first round, resulting in 171 winners to go on to the second
round. For the second round, 171/2 = 85 plus 1 left over; there are 85 matches
and 85 winners, plus the 1 left over, to go on to the third round. The third round
has 86/2 = 43 matches, and so forth. The total number of matches is the sum of
171 + 85 + 43 + c .
The clever observation is to note that each match results in exactly 1 loser, so
there must be the same number of matches as losers in the tournament. Because
there is only 1 winner, there are 341 losers and therefore 341 matches.