Working out the negation, we have
∼ ¡∀ ε ∈ (0, ∞), ∃M ∈ (0, ∞), (x > M) ⇒ (| f (x) − b| < ε)¢
=
∃ ε ∈ (0, ∞), ∼ ¡∃M ∈ (0, ∞), (x > M) ⇒ (| f (x) − b| < ε)¢
=
∃ ε ∈ (0, ∞), ∀M ∈ (0, ∞), ∼ ¡(x > M) ⇒ (| f (x) − b| < ε)¢.
Finally, using the idea from Example 2.14, we can negate the conditional
statement that appears here to get
∃ ε ∈ (0, ∞), ∀M ∈ (0, ∞), ∃x, (x > M)∧ ∼ (| f (x) − b| < ε)¢.
Negation: There exists a positive number ε with the property that for every
positive number M , there is a number x for which x > M and |f (x) − b| ≥ ε.
7. I don’t eat anything that has a face.
Negation: I will eat some things that have a face.
(Note. If your answer was “I will eat anything that has a face.” then that is
wrong, both morally and mathematically.)
9. If sin(x) < 0, then it is not the case that 0 ≤ x ≤ π.
Negation: There exists a number x for which sin(x) < 0 and 0 ≤ x ≤ π.
11. You can fool all of the people all of the time.
There are several ways to negate this, including:
There is a person that you can’t fool all the time. or
There is a person x and a time y for which x is not fooled at time y .
(But Abraham Lincoln said it better.)
253
Chapter 3 Exercises
Section 3.1
1. Consider lists made from the letters T, H, E, O, R, Y, with repetition allowed.
(a) How many length-4 lists are there? Answer: 6 · 6 · 6 · 6 = 1296.
(b) How many length-4 lists are there that begin with T?
Answer: 1 · 6 · 6 · 6 = 216.
(c) How many length-4 lists are there that do not begin with T?
Answer: 5 · 6 · 6 · 6 = 1080.
3. How many ways can you make a list of length 3 from symbols a,b,c,d,e,f if...
(a) ... repetition is allowed. Answer: 6 · 6 · 6 = 216.
(b) ... repetition is not allowed. Answer: 6 · 5 · 4 = 120.
(c) ... repetition is not allowed and the list must contain the letter a.
Answer: 5 · 4 + 5 · 4 + 5 · 4 = 60.
(d) ... repetition is allowed and the list must contain the letter a.
Answer: 6 · 6 · 6 − 5 · 5 · 5 = 91.
(Note: See Example 3.2 if a more detailed explanation is required.)
5. Five cards are dealt off of a standard 52-card deck and lined up in a row. How
many such line-ups are there in which all five cards are of the same color? (i.e.,
all black or all red.)
There are 26·25·24·23·22 = 7, 893, 600 possible black-card line-ups and 26·25·24·23·
22 = 7,893,600 possible red-card line-ups, so the answer is 7,893,600+7,893,600 =
15, 787, 200.
7. This problems involves 8-digit binary strings such as 10011011 or 00001010.
(i.e., 8-digit numbers composed of 0’s and 1’s.)
(a) How many such strings are there? Answer: 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 = 256.
(b) How many such strings end in 0? Answer: 2 · 2 · 2 · 2 · 2 · 2 · 2 · 1 = 128.
(c) How many such strings have the property that their second and fourth
digits are 1’s? Answer: 2 · 1 · 2 · 1 · 2 · 2 · 2 · 2 = 64.
(d) How many such strings are such that their second or fourth digits are 1’s?
Answer: These strings can be divided into three types. Type 1 consists of
those strings of form ∗1∗0∗∗∗∗, Type 2 consist of strings of form ∗0∗1∗∗∗∗,
and Type 3 consists of those of form ∗1 ∗ 1 ∗ ∗ ∗ ∗. By the multiplication
principle there are 26 = 64 strings of each type, so there are 3 · 64 = 192
8-digit binary strings whose second or fourth digits are 1’s.
9. This problem concerns 4-letter codes that can be made from the letters of the
English Alphabet.
(a) How many such codes can be made? Answer: 26 · 26 · 26 · 26 = 456976
254
Solutions
(b) How many such codes have no two consecutive letters the same?
We use the multiplication principle. There are 26 choices for the first letter.
The second letter can’t be the same as the first letter, so there are only 25
choices for it. The third letter can’t be the same as the second letter, so there
are only 25 choices for it. The fourth letter can’t be the same as the third letter,
so there are only 25 choices for it. Thus there are 26 · 25 · 25 · 25 = 406, 250
codes with no two consecutive letters the same.
11. This problem concerns lists of length 6 made from the letters A,B,C,D,E,F,G,H.
How many such lists are possible if repetition is not allowed and the list
contains two consecutive vowels?
Answer: There are just two vowels A and E to choose from. The lists we want
to make can be divided into five types. They have one of the forms V V ∗ ∗ ∗ ∗,
or ∗V V ∗ ∗∗, or ∗ ∗ V V ∗ ∗, or ∗ ∗ ∗V V∗, or ∗ ∗ ∗ ∗ V V , where V indicates a
vowel and ∗ indicates a consonant. By the multiplication principle, there are
2·1·6·5·4·3 = 720 lists of form V V ∗∗∗∗. In fact, that for the same reason there
are 720 lists of each form. Thus the answer to the question is 5 · 720 = 3600
Section 3.2
1. Answer n = 14.
5. 120!
118! = 120·119·118!
118!
= 120 · 119 = 14, 280.
3. Answer: 5! = 120.
7. Answer: 5!4! = 2880.
9. The case x = 1 is straightforward. For x = 2,3 and 4, use integration by parts.
For x = π, you are on your own.
Section 3.3
1. Suppose a set A has 37 elements. How many subsets of A have 10 elements?
How many subsets have 30 elements? How many have 0 elements?
¡37¢
¡37¢
¡37¢
Answers: 10 = 348,330,136; 30 = 10,295,472; 0 = 1.
3. A set X has exactly 56 subsets with 3 elements. What is the cardinality of X ?
¡n¢
The answer will be n, where 3 = 56. After some trial and error, you will
¡8¢
discover 3 = 56, so |X | = 8.
5. How many 16-digit binary strings contain exactly seven 1’s?
Answer: Make such a string as follows. Start with a list of 16 blank spots.
Choose 7 of the blank spots for the 1’s and put 0’s in the other spots. There
¡ 16 ¢
are
7
= 114, 40 ways to do this.
7. |{X ∈ P({0,1,2,3,4,5,6,7,8,9}) : |X | < 4}| = ¡10¢
¢
¢
¢
0
+ ¡ 10
1
+ ¡ 10
2
+ ¡ 10
3
= 1+10+45+120 =
176.
9. This problem concerns lists of length six made from the letters A,B,C,D,E,F,
without repetition. How many such lists have the property that the D occurs
before the A?
Answer: Make such a list as follows. Begin with six blank spaces and select
two of these spaces. Put the D in the first selected space and the A in the
¡ 6 ¢
second. There are
2
= 15 ways of doing this. For each of these 15 choices
there are 4! = 24 ways of filling in the remaining spaces. Thus the answer to
the question is 15 × 24 = 360 such lists.
255
11. How m
any 10-digit integers contain no 0’s and exactly three 6’s?
Answer: Make such a number as follows: Start with 10 blank spaces and choose
¡ 10 ¢
three of these spaces for the 6’s. There are
3
= 120 ways of doing this. For
each of these 120 choices we can fill in the remaining seven blanks with choices
from the digits 1, 2, 3, 4, 5, 7, 8, 9, and there are 87 to do this. Thus the answer to
¡ 10 ¢
the question is
3
· 87 = 251, 658, 240.
13.
¡n¢
¢
Assume n, k ∈ Z with 0 ≤ k ≤ n. Then
.
k =
n!
(n−k)!k! =
n!
k!(n−k)! =
n!
(n−(n−k))!(n−k)! = ¡ n
n−k
Section 3.4
1. Write out Row 11 of Pascal’s triangle.
Answer:
1
11
55
165
330
462
462
330
165
55
11
1
3. Use the binomial theorem to find the coefficient of x8 in (x + 2)13.
Answer: According to the binomial theorem, the coefficient of x8 y5 in (x + y)13
¡ 13 ¢
is
x8 y5
8
= 1287x8 y5. Now plug in y = 2 to get the final answer of 41184x8.
5.
Pn
¡ n ¢
Use the binomial theorem to show
= 2n
k=0 k
. Hint: Observe that 2n = (1+1)n.
Now use the binomial theorem to work out (x + y)n and plug in x = 1 and y = 1.
7.
Pn
¢
Use the binomial theorem to show
3k ¡ n = 4n
k=0
k
.
Hint: Observe that 4n = (1 + 3)n. Now look at the hint for the previous problem.
9.
¡ n ¢
¢
¢
¢
¢
¢
¢
Use the binomial theorem to show
0 − ¡ n
1 + ¡ n
2 − ¡ n
3 + ¡ n
4 − ¡ n
5 + . . . ± ¡ n
n
= 0.
Hint: Observe that 0 = 0n = (1 + (−1))n. Now use the binomial theorem.
11.
¢
Use the binomial theorem to show 9n = Pn
(−1)k ¡ n 10n−k
k=0
k
.
Hint: Observe that 9n = (10 + (−1))n. Now use the binomial theorem.
13.
¡n¢
¢
¢
¢
¢
¢
¢
¢
¢
Assume n ≥ 3. Then 3 = ¡n−1
3
+¡n−1
2
= ¡n−2
3
+¡n−2
2
+¡n−1
2
= · · · = ¡22 +¡32 +···+¡n−1
2
.
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?
Answer: Let A be the set of senior math majors and B be the set of senior
history majors. From |A ∪ B| = |A| + |B| − |A ∩ B| we get 523 = 100 + |B| − 33, so
|B| = 523 + 33 − 100 = 456. There are 456 history majors.
3. How many 4-digit positive integers are there that are even or contain no 0’s?
Answer: Let A be the set of 4-digit even positive integers, and let B be the
set of 4-digit positive integers that contain no 0’s. We seek |A ∪ B|. By the
multiplication principle |A| = 9 · 10 · 10 · 5 = 4500. (Note the first digit cannot be 0
and the last digit must be even.) Also |B| = 9·9·9·9 = 6561. Further, A∩B consists
of all even 4-digit integers that have no 0’s. It follows that |A∩B| = 9·9·9·4 = 2916.
Then the answer to our question is |A ∪B| = |A|+|B|−|A ∩B| = 4500+6561−2916 =
8145.
256
Solutions
5. How many 7-digit binary strings begin in 1 or end in 1 or have exactly four 1’s?
Answer: Let A be the set of such strings that begin in 1. Let B be the set of such
strings that end in 1. Let C be the set of such strings that have exactly four 1’s.
Then the answer to our question is |A ∪ B ∪ C|. Using Equation (3.4) to compute
this number, we have |A∪B∪C| = |A|+|B|+|C|−|A∩B|−|A∩C|−|B∩C|+|A∩B∩C| =
26 + 26 + ¡7¢
¢
¢
¢
4 − 25 − ¡ 6
3 − ¡ 6
3 + ¡ 5
2 = 64 + 64 + 35 − 32 − 20 − 20 + 10 = 101.
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 four cards are of the same suit or
all four cards are red?
Answer: Let A be the set of 4-card hands for which all four cards are of the
same suit. Let B be the set of 4-card hands for which all four cards are red.
Then A ∩ B is the set of 4-card hands for which the four cards are either all
hearts or all diamonds. The answer to our question is |A ∪B| = |A|+|B|−|A ∩B| =
4 ¡ 13 ¢
¢
¢
¢
¢
4
+ ¡ 26
4
− 2 ¡ 13
4
= 2 ¡ 13
4
+ ¡ 26
4
= 1430 + 14950 = 16380.
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.
Answer: Let A be the set of such lists for which the first two letters are
vowels, so |A| = 2 · 2 · 6 · 6 = 144. Let B be the set of such lists that end in D, so
|B| = 6 · 6 · 6 · 1 = 216. Then A ∩ B is the set of such lists for which the first two
entries are vowels and the list ends in D. Thus |A ∩ B| = 2 · 2 · 6 · 1 = 24. The
answer to our question is |A ∪ B| = |A| + |B| − |A ∩ B| = 144 + 216 − 24 = 336.
Chapter 4 Exercises
1. If x is an even integer, then x2 is even.
Proof. Suppose x is even. Thus x = 2a for some a ∈ Z.
Consequently x2 = (2a)2 = 4a2 = 2(2a2).
Therefore x2 = 2b, where b is the integer 2a2.
Thus x2 is even by definition of an even number.
■
3. If a is an odd integer, then a2 + 3a + 5 is odd.
Proof. Suppose a is odd.
Thus a = 2c + 1 for some integer c, by definition of an odd number.
Then a2 + 3a + 5 = (2c + 1)2 + 3(2c + 1) + 5 = 4c2 + 4c + 1 + 6c + 3 + 5 = 4c2 + 10c + 9
= 4c2 + 10c + 8 + 1 = 2(2c2 + 5c + 4) + 1.
This shows a2 + 3a + 5 = 2b + 1, where b = 2c2 + 5c + 4 ∈ Z.
Therefore a2 + 3a + 5 is odd.
■
5. Suppose x, y ∈ Z. If x is even, then xy is even.
Proof. Suppose x, y ∈ Z and x is even.
Then x = 2a for some integer a, by definition of an even number.
/>
Thus x y = (2a)( y) = 2(a y).
Therefore x y = 2b where b is the integer a y, so x y is even.
■
257
7. Suppose a, b ∈ Z. If a | b, then a2 | b2.
Proof. Suppose a | b.
By definition of divisibility, this means b = ac for some integer c.
Squaring both sides of this equation produces b2 = a2 c2.
Then b2 = a2d, where d = c2 ∈ Z.
By definition of divisibility, this means a2 | b2.
■
9. Suppose a is an integer. If 7 | 4a, then 7 | a.
Proof. Suppose 7 | 4a.
By definition of divisibility, this means 4a = 7c for some integer c.
Since 4a = 2(2a) it follows that 4a is even, and since 4a = 7c, we know 7c is even.
But then c can’t be odd, because that would make 7c odd, not even.
Thus c is even, so c = 2d for some integer d.
Now go back to the equation 4a = 7c and plug in c = 2d. We get 4a = 14d.
Dividing both sides by 2 gives 2a = 7d.
Now, since 2a = 7d, it follows that 7d is even, and thus d cannot be odd.
Then d is even, so d = 2e for some integer e.
Plugging d = 2e back into 2a = 7d gives 2a = 14e.
Dividing both sides of 2a = 14e by 2 produces a = 7e.
Finally, the equation a = 7e means that 7 | a, by definition of divisibility.
■
11. Suppose a, b, c, d ∈ Z. If a | b and c | d, then ac | bd.
Proof. Suppose a | b and c | d.
As a | b, the definition of divisibility means there is an integer x for which
b = ax.
As c | d, the definition of divisibility means there is an integer y for which
d = c y.
Since b = ax, we can multiply one side of d = c y by b and the other by ax.
This gives bd = axc y, or bd = (ac)(x y).
Since x y ∈ Z, the definition of divisibility applied to bd = (ac)(x y) gives ac | bd.
■
13. Suppose x, y ∈ R. If x2 + 5y = y2 + 5x, then x = y or x + y = 5.
Proof. Suppose x2 + 5y = y2 + 5x.
Then x2 − y2 = 5x − 5 y, and factoring gives (x − y)(x + y) = 5(x − y).
Now consider two cases.
Case 1. If x − y 6= 0 we can divide both sides of (x − y)(x + y) = 5(x − y) by the
non-zero quantity x − y to get x + y = 5.
Case 2. If x − y = 0, then x = y. (By adding y to both sides.)
Thus x = y or x + y = 5.
■
258
Solutions
15. If n ∈ Z, then n2 + 3n + 4 is even.
Proof. Suppose n ∈ Z. We consider two cases.
Case 1. Suppose n is even. Then n = 2a for some a ∈ Z.
Therefore n2 + 3n + 4 = (2a)2 + 3(2a) + 4 = 4a2 + 6a + 4 = 2(2a2 + 3a + 2).
So n2 + 3n + 4 = 2b where b = 2a2 + 3a + 2 ∈ Z, so n2 + 3n + 4 is even.
Case 2. Suppose n is odd. Then n = 2a + 1 for some a ∈ Z.
Book of Proof Page 36