((
)
(
)
(
)
)
K
K
J
K
J
Q
Q
Q
Q
B
=
,
,
,
,
,
,
,
,
, . . .
(Face cards)
♠
♦
♣
♥
♥
♥
♦
♣
♥
82
Counting
We seek the number of 3-card hands that are all red or all face cards,
and this number is |A ∪ B|. By Formula (3.3), |A ∪ B| = |A| + |B| − |A ∩ B|.
Let’s examine |A|, |B| and |A ∩ B| separately. Any hand in A is formed
¢
by selecting three cards from the 26 red cards in the deck, so |A| = ¡26
3 .
Similarly, any hand in B is formed by selecting three cards from the 12
¢
face cards in the deck, so |B| = ¡12
3 . Now think about A ∩ B. It contains all
the 3-card hands made up of cards that are red face cards.
((
)
(
)
(
)
)
K
K
J
K
J
Q
Q
J
Q
(Red face
A ∩ B =
,
,
,
,
,
, ,
,
,
, . . .
♥
♦
♥
♥
♥
♥
♦
♦
♥
cards)
¢
The deck has only 6 red face cards, so |A ∩ B| = ¡63 .
Now we can answer our question. The number of 3-card hands that
¢
¢
¢
are all red or all face cards is |A ∪ B| = |A| + |B| − |A ∩ B| = ¡26
3 + ¡12
3 − ¡6
3 =
2600 + 220 − 20 = 2800.
There is an analogue to Equation (3.3) that involves three sets. Consider
three sets A, B and C, as represented in the following Venn Diagram.
C
A
B
Using the same kind of reasoning that resulted in Equation (3.3), you can
convince yourself that
|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|.
(3.4)
There’s probably not much harm in ignoring this one for now, but if you
find this kind of thing intriguing you should definitely take a course in
combinatorics. (Ask your instructor!)
As we’ve noted, Equation (3.3) becomes |A ∪ B| = |A| + |B| if it happens
that A ∩ B = ;. Also, in Equation (3.4), note that if A ∩ B = ;, A ∩ C = ; and
B ∩ C = ;, we get the simple formula |A ∪ B ∪ C| = |A| + |B| + |C|. In general,
we have the following formula for n sets, none of which overlap. It is
sometimes called the addition principle.
Fact 3.4
(Addition Principle) If A1, A2,..., An are sets with Ai ∩ A j = ;
whenever i 6= j, then |A1 ∪ A2 ∪ · · · ∪ An| = |A1| + |A2| + · · · + |An|.
Inclusion-Exclusion
83
Example 3.9
How many 7-digit binary strings (0010100, 1101011, etc.)
have an odd number of 1’s?
Solution: Let A be the set of all 7-digit binary strings with an odd
number of 1’s, so the answer to the question will be |A|. To compute |A|,
we break A up into smaller parts. Notice any string in A will have either
one, three, five or seven 1’s. Let A1 be the set of 7-digit binary strings
with only one 1. Let A3 be the set of 7-digit binary strings with three 1’s.
Let A5 be the set of 7-digit binary strings with five 1’s, and let A7 be the
set of 7-digit binary strings with seven 1’s. Therefore A = A1 ∪ A3 ∪ A5 ∪ A7.
Notice that any two of the sets Ai have empty intersection, so Fact 3.4
gives |A| = |A1| + |A3| + |A5| + |A7|.
Now the problem is to find the values of the individual terms of this
sum. For instance take A3, the set of 7-digit binary strings with three 1’s.
Such a string can be formed by selecting three out of seven positions for
¢
the 1’s and putting 0’s in the other spaces. Therefore |A3| = ¡73 . Similarly
|A
¢
¢
¢
1| = ¡7
1 , | A5| = ¡7
5 , and | A7| = ¡7
7 . Finally the answer to our question is
|A| = |A
¢
¢
¢
¢
1| + | A3| + | A5| + | A7| = ¡7
1 + ¡7
3 + ¡7
5 + ¡7
7 = 7 + 35 + 21 + 1 = 64. There
are 64 seven-digit binary strings with an odd number of 1’s.
You may already have been using the Addition Principle intuitively,
without thinking of it as a free-standing result. For instance, we used it
in Example 3.2(c) when we divided lists into four types and computed the
number of lists of each type.
Exercises for Section 3.5
1. At a certain university 523 of the seniors are history majors or math majors
(or both). There are 100 senior math majors, and 33 seniors are majoring in
both history and math. How many seniors are majoring in history?
2. How many 4-digit positive integers are there for which there are no repeated
digits, or for which there may be repeated digits, but all are odd?
3. How many 4-digit positive integers are there that are even or contain no 0’s?
4. This problem involves lists made from the letters T,H,E,O,R,Y, with repetition
allowed.
(a) How many 4-letter lists are there that don’t begin with T, or don’t end in
Y?
(b) How many 4-letter lists are there in which the sequence of letters T,H,E
appears consecutively?
(c) How many 5-letter lists are there in which the sequence of letters T,H,E
appears consecutively?
84
Counting
5. How many 7-digit binary strings begin in 1 or end in 1 or have exactly four 1’s?
6. Is the following statement true or false? Explain. If A1 ∩ A2 ∩ A3 = ;, then
|A1 ∪ A2 ∪ A3| = |A1| + |A2| + |A3|.
7. This problem concerns 4-card hands dealt off of a standard 52-card deck. How
many 4-card hands are there for which all 4 cards are of the same suit or all 4
cards are red?
8. This problem concerns 4-card hands dealt off of a standard 52-card deck. How
many 4-card hands are there for which all 4 cards are of different suits or all 4
cards are red?
9. A 4-letter list is made from the letters L,I,S,T,E,D according to the following
rule: Repetition is allowed, and the first two letters on the list are vowels or
the list ends in D. How many such lists are possible?
10. A 5-card poker hand is called a flush if all car
ds are the same suit. How many
different flushes are there?
Part II
How to Prove Conditional
Statements
CHAPTER
4
Direct Proof
t is time to prove some theorems. There are various strategies for doing
I this; we now examine the most straightforward approach, a technique
called direct proof. As we begin, it is important to keep in mind the
meanings of three key terms: Theorem, proof and definition.
A theorem is a mathematical statement that is true and can be (and
has been) verified as true. A proof of a theorem is a written verification
that shows that the theorem is definitely and unequivocally true. A proof
should be understandable and convincing to anyone who has the requisite
background and knowledge. This knowledge includes an understanding of
the meanings of the mathematical words, phrases and symbols that occur
in the theorem and its proof. It is crucial that both the writer of the proof
and the readers of the proof agree on the exact meanings of all the words,
for otherwise there is an intolerable level of ambiguity. A definition is an
exact, unambiguous explanation of the meaning of a mathematical word or
phrase. We will elaborate on the terms theorem and definition in the next
two sections, and then finally we will be ready to begin writing proofs.
4.1 Theorems
A theorem is a statement that is true and has been proved to be true.
You have encountered many theorems in your mathematical education.
Here are some theorems taken from an undergraduate calculus text. They
will be familiar to you, though you may not have read all the proofs.
Theorem: Let f be differentiable on an open interval I and let c ∈ I.
If f (c) is the maximum or minimum value of f on I, then f 0(c) = 0.
Theorem:
P∞
If
a
k=1 k converges, then limk→∞ ak = 0.
Theorem: Suppose f is continuous on the interval [a, b]. Then f is
integrable on [a, b].
Theorem: Every absolutely convergent series converges.
88
Direct Proof
Observe that each of these theorems either has the conditional form “If
P , then Q ,” or can be put into that form. The first theorem has an initial
sentence “Let f be differentiable on an open interval I , and let c ∈ I ,” which
sets up some notation, but a conditional statement follows it. The third
theorem has form “Suppose P . Then Q ,” but this means the same thing
as “If P , then Q .” The last theorem can be re-expressed as “If a series is
absolutely convergent, then it is convergent.”
A theorem of form “If P , then Q ,” can be regarded as a device that
produces new information from P.
Whenever we are dealing with a
situation in which P is true, then the theorem guarantees that, in addition,
Q is true. Since this kind of expansion of information is useful, theorems
of form “If P , then Q ,” are very common.
But not every theorem is a conditional statement. Some have the form
of the biconditional P ⇔ Q, but, as we know, that can be expressed as two
conditional statements. Other theorems simply state facts about specific
things. For example, here is another theorem from your study of calculus.
Theorem: The series 1 + 12 + 13 + 14 + 15 + ··· diverges.
It would be difficult (or at least awkward) to restate this as a conditional
statement. Still, it is true that most theorems are conditional statements,
so much of this book will concentrate on that type of theorem.
It is important to be aware that there are a number of words that
mean essentially the same thing as the word “theorem,” but are used in
slightly different ways. In general the word “theorem” is reserved for a
statement that is considered important or significant (the Pythagorean
theorem, for example). A statement that is true but not as significant
is sometimes called a proposition. A lemma is a theorem whose main
purpose is to help prove another theorem. A corollary is a result that is
an immediate consequence of a theorem or proposition. It is not important
that you remember all these words now, for their meanings will become
clear with usage.
Our main task is to learn how to prove theorems. As the above examples
suggest, proving theorems requires a clear understanding of the meaning
of the conditional statement, and that is the primary reason we studied it
so extensively in Chapter 2. In addition, it is also crucial to understand
the role of definitions.
Definitions
89
4.2 Definitions
A proof of a theorem should be absolutely convincing. Ambiguity must be
avoided. Everyone must agree on the exact meaning of each mathematical
term. In Chapter 1 we defined the meanings of the sets N, Z, R, Q and
;, as well as the meanings of the symbols ∈ and ⊆, and we shall make
frequent use of these things. Here is another definition that we use often.
Definition 4.1
An integer n is even if n = 2a for some integer a ∈ Z.
Thus, for example, 10 is even because 10 = 2 · 5. Also, according to the
definition, 7 is not even because there is no integer a for which 7 = 2a.
While there would be nothing wrong with defining an integer to be odd if
it’s not even, the following definition is more concrete.
Definition 4.2
An integer n is odd if n = 2a + 1 for some integer a ∈ Z.
Thus 7 is odd because 7 = 2·3+1. We will use these definitions whenever
the concept of even or odd numbers arises. If in a proof a certain number
turns out to be even, the definition allows us to write it as 2a for an
appropriate integer a. If some quantity has form 2b + 1 where b is an
integer, then the definition tells us the quantity is odd.
Definition 4.3
Two integers have the same parity if they are both even
or they are both odd. Otherwise they have opposite parity.
Thus 5 and −17 have the same parity, as do 8 and 0; but 3 and 4 have
opposite parity.
Two points about definitions are in order. First, in this book the word
or term being defined appears in boldface type. Second, it is common to
express definitions as conditional statements even though the biconditional
would more appropriately convey the meaning. Consider the definition
of an even integer. You understand full well that if n is even then n = 2a
(for a ∈ Z), and if n = 2a, then n is even. Thus, technically the definition
should read “An integer n is even if and only if n = 2a for some a ∈ Z .”
However, it is an almost-universal convention that definitions are phrased
in the conditional form, even though they are interpreted as being in the
biconditional form. There is really no good reason for this, other than
economy of words. It is the standard way of writing definitions, and we
have to get used to it.
Here is another definition that we will use often.
90
Direct Proof
Definition 4.4
Suppose a and b are integers. We say that a divides b,
written a | b, if b =
ac for some c ∈ Z. In this case we also say that a is a
divisor of b, and that b is a multiple of a.
For example, 5 divides 15 because 15 = 5 · 3. We write this as 5 | 15.
Similarly 8 | 32 because 32 = 8 · 4, and −6 | 6 because 6 = −6 · −1. However,
6 does not divide 9 because there is no integer c for which 9 = 6 · c. We
express this as 6 - 9, which we read as “ 6 does not divide 9 .”
Be careful of your interpretation of the symbols. There is a big difference
between the expressions a | b and a/b. The expression a | b is a statement,
while a/b is a fraction. For example, 8 | 16 is true and 8 | 20 is false. By
contrast, 8/16 = 0.5 and 8/20 = 0.4 are numbers, not statements. Be careful
not to write one when you mean the other.
Every integer has a set of integers that divide it. For example, the set
©
of divisors of 6 is a ∈ Z : a | 6ª = © − 6, −3, −2, −1, 1, 2, 3, 6ª. The set of divisors
©
of 5 is
− 5, −1, 1, 5ª. The set of divisors of 0 is Z. This brings us to the
following definition, with which you are already familiar.
Definition 4.5
A natural number n is prime if it has exactly two positive
divisors, 1 and n.
For example, 2 is prime, as are 5 and 17. The definition implies that 1
is not prime, as it only has one (not two) positive divisor, namely 1. An
integer n is composite if it factors as n = ab where a, b > 1.
Definition 4.6
The greatest common divisor of integers a and b,
denoted gcd(a, b), is the largest integer that divides both a and b. The
least common multiple of non-zero integers a and b, denoted lcm(a, b),
is smallest positive integer that is a multiple of both a and b.
So gcd(18, 24) = 6, gcd(5, 5) = 5 and gcd(32, −8) = 8. Also gcd(50, 18) = 2,
but gcd(50, 9) = 1. Note that gcd(0, 6) = 6, because, although every integer
divides 0, the largest divisor of 6 is 6.
The expression gcd(0, 0) is problematic. Every integer divides 0, so the
only conclusion is that gcd(0, 0) = ∞. We circumvent this irregularity by
simply agreeing to consider gcd(a, b) only when a and b are not both zero.
Continuing our examples, lcm(4, 6) = 12, and lcm(7, 7) = 7.
Of course not all terms can be defined. If every word in a definition were
defined, there would be separate definitions for the words that appeared
in those definitions, and so on, until the chain of defined terms became
circular. Thus we accept some ideas as being so intuitively clear that
they require no definitions or verifications. For example, we will not find
Definitions
91
it necessary to define what an integer (or a real number) is. Nor will
Book of Proof Page 13