80 CHAPTER 2 Discrete Mathematics
of color. The proof rested on the fact that this setCof criminals must
have aleast element, which meant that any positive integermwhich
is less than any element ofC cannot be a criminal.
Before formalizing the above, let’s take up an example of a somewhat
different nature. Consider the proposition that, for anyn∈N, one has
12 + 2^2 + 3^2 +···+n^2 =n(n+ 1)(2n+ 1)
6.
Naturally, for each such n, either the above statement is true or
false. This allows us to divideN into two subsets: the subset G (for
“good guys”) of integersn∈Nfor which the above statement is true,
and the setC (for “criminals”) for which the above statement is false.
Obviously
N = G∪C, and G∩C=∅.
Also — and this is important — note that 1∈G, i.e., ifn= 1, then
the above statement is easily verified to be true. Put differently, 1 is
not a criminal; it’s a good guy!
In order to prove that the above statement is truefor alln∈N, we
need only show thatC =∅.Thus, letm be theleast elementofC,
and note that since 16∈C we have thatm− 1 ∈G: that is to say the
above statement is valid withn=m−1. Watch this:
12 + 2^2 + 3^2 +···+m^2 = 1^2 + 2^2 + 3^2 +···(m−1)^2 +m^2
=(m−1)m(2(m−1) + 1)
6+m^2 (This is the key step!)=1
6
(2m^3 − 3 m^2 +m+ 6m^2 ) (This is just algebra.)=1
6
(m(m^2 + 3m+ 1) =m(m+ 1)(2m+ 1)
6(A little more algebra.)Let’s have a look at what just happened. We started with the as-
sumption that the integer m is a criminal, the least criminal in fact,
and then observed in the end that 1^2 + 2^2 + 3^2 +···+n^2 =n(n+1)(2 6 n+1),
meaning that m is not a criminal. This is clearly a contradiction!
What caused this contradiction is the fact that there was an element in
C, so the only way out of this contradiction is to conclude thatC=∅.