Solutions for Exam #2 November 6, 2003

1. { 10 points: +2 points for a right answer, −1 point for a wrong one, 0 points if none or both of
the boxes are checked. In case the total is negative, 0 points will be given for this problem. }
For each of the following statements determine whether it is true or false.
It is not necessary to justify your answers.

(A) {2} ⊆ {1, {2}, {3}}. false

{2} is an element, not a subset.

(B) 3 ∈ {1, {2}, {3}}. false

{3} is an element, but 3 is not.

(C) For all sets A, B, and C, if A ⊆ B then A ∩ C ⊆ B ∩ C. true

Let x ∈ A ∩ C. Then x ∈ A and x ∈ C. Since from A ⊆ B and x ∈ A
it follows that x ∈ B , we receive x ∈ B ∩ C.

(D) For all sets A, B, and C, if A * B and B * C then A * C. false

counterexample: A = C = {1} and B = {2}.

(E) For all sets A and B, if B ⊆ Ac then A ∩ B = ∅. true

c
Let x ∈ B. Then from B ⊆ A it follows that x ∈
/ A. Hence, the sets A and B
have no common elements.

2. { 10 points } Suppose A = {1, 3, 5} and B = {2, 3}. Find each of the following.

A ∪ B = {1, 2, 3, 5} .

A − B = {1, 5} .

P(A) = { ∅, {1}, {3}, {5}, {1, 3}, {1, 5}, {3, 5}, {1, 3, 5} } .

P(A ∩ B) = P({3}) = { ∅, {3} } .

A × B = { (1, 2), (1, 3), (3, 2), (3, 3), (5, 2), (5, 3) } .
3. { 10 points } A combination lock requires four selections of numbers, each from
0 to 9.

(A) How many different combinations are possible?

10 · 10 · 10 · 10 = 104 = 10 000 .

(B) Suppose the lock is constructed in such a way that no number can be
used twice. How many different combinations are possible?
µ ¶
10!
10 · 9 · 8 · 7 = 5 040 = P (10, 4) = .
6!

4. { 10 points } Suppose that four computer boards in a production run of sixty

are defective. A sample of five is to be selected to be checked for defects.
The answers can be given as arithmetic expressions, if you do not use a calculator.

(A) How many different samples can be chosen?

µ ¶
60 60 · 59 · 58 · 57 · 56
nA = = = 5 461 512 .
5 1·2·3·4·5

(B) How many samples will contain at least one defective board?
¡ ¢
60−4 = 56 boards are not defective, so 56 5 samples will not have a defective
board. Thus, the answer is
µ ¶ µ ¶
60 56 60 · 59 · 58 · 57 · 56 − 56 · 55 · 54 · 53 · 52
nB = − = = 1 641 696 .
5 5 1·2·3·4·5

(C) What is the probability that a randomly chosen sample of five will contain at least one
defective board?
nB 60 · 59 · 58 · 57 − 55 · 54 · 53 · 52
P = = ≈ 0.30059 .
nA 60 · 59 · 58 · 57
5. { 10 points } Use the Binomial Theorem to show that for all integers n ≥ 0,
µ ¶ µ ¶ µ ¶ µ ¶ µ ¶
n n n 2 n 3 n n n
4 = +3 +3 +3 + ... + 3 .
0 1 2 3 n

µ ¶ µ ¶ µ ¶ µ ¶ µ ¶ X n µ ¶
n n 2 n 3 n n n i n
+3 +3 +3 + ... + 3 = 3
0 1 2 3 n i=0
i
Xn µ ¶
n n−i i
= 1 3 = (1 + 3)n = 4n .
i=0
i

6. { 10 points }
How many functions are there from a set with four elements to a set with
ten elements?
10 · 10 · 10 · 10 = 104 = 10 000 .

How many of these functions are one-to-one?

10 · 9 · 8 · 7 = 5 040 .

How many of these functions are onto?

0
Every element from the second set should be assigned as a value of the function.
This is impossible since there are ten elements for only four values.

7. { 10 points } Determine whether or not the function f (x) = 2x+1

x−1 , defined for
all real numbers x 6= 1 , is one-to-one and justify your answer.
The function is one-to-one. To prove this, we have to show that if x1 6= x2
then f (x1 ) 6= f (x2 ). We shall now prove the validity of an equivalent statement, namely its
contrapositive: if f (x1 ) = f (x2 ) then x1 = x2 .
Let x1 and x2 be arbitrary real numbers different from 1, and such that f (x1 ) = f (x2 ).
2x1 + 1 2x2 + 1
Then = , which gives (2x1 + 1)(x2 − 1) = (2x2 + 1)(x1 − 1) . After
x1 − 1 x2 − 1
the multiplication we receive 2x1 x2 − 2x1 + x2 − 1 = 2x1 x2 − 2x2 + x1 − 1 . A simplification
gives 3x2 = 3x1 , and therefore x1 = x2 .
8. { 10 points } Show that the sequence an = 2n − 1 for n = 0, 1, 2, ... satisfies the
recurrence relation

ak = 3ak−1 − 2ak−2 , for all integers k ≥ 2 .

We have ak−1 = 2k−1 − 1 and ak−2 = 2k−2 − 1. Thus

¡ ¢ ¡ ¢
3ak−1 − 2ak−2 = 3 2k−1 − 1 − 2 2k−2 − 1 = 3 · 2k−1 − 3 − 2 · 2k−2 + 2
= 3 · 2k−1 − 2k−1 − 1 = 2 · 2k−1 − 1 = 2k − 1 = ak .

¡2 ¢3
9. { 10 points } Show that 7
(n + 1)(n2 − 7) is O(n9 ) .
µ ¶3
2 ¡ ¢3 ¡ ¢3
(n + 1)(n − 7) = O(n) O(n2 ) = O(n3 ) = O(n9 ) .
2
7

10. { 10 points } Prove the statement assuming that n is an integer variable that
takes positive integer values.

1 + 2 + 22 + 23 + 24 + ... + 2n is O(2n ) .

n
X
n i 1 − 2n+1
1 + 2 + 2 + 2 + 2 + ... + 2 =
2 3 4
2 = = 2n+1 − 1 ≤ 2 · 2n .
i=0
1−2

First Bonus Problem. { 10 points } Use iteration to guess an explicit formula for
the recursively defined sequence. Prove by induction the formula you received.
bk−1
bk = 1+bk−1 , for all integers k ≥ 1 ; b0 = 1 .
Let us evaluate the first five terms of the sequence
b0 1 1 b1 1 1
1
b0 = 1 , b1 = = = , b2 = = 2 = 2
= ,
1 + b0 1+1 2 1 + b1 1+ 1
2
3
2
3

b2 1 1
1 b3 1 1
1
b3 = = 3 = 3
= , b4 = = 4 = 4
= .
1 + b2 1+ 1
3
4
3
4 1 + b3 1+ 1
4
5
4
5

1
guess: bn = .
n+1
Proof. For k = 0 , b0 = 0+1 1
= 1 and the formula is valid.
Let k ≥ 1 and let assume that the formula is valid for n = k − 1 , i.e.
bk−1 = (k−1)+1
1
= k1 . Then from the recurrence relation we have

bk−1 1
k
1
k 1
bk = = = k+1
= .
1 + bk−1 1+ 1
k k
k+1

Thus, by induction, bn = 1
n+1 for all integers n ≥ 0.

Second Bonus Problem. { 10 points } An ordinary deck of cards contains 52 cards

divided into four suits ( ♣ , ♦ , ♥ , ♠ ). Each suit contains 13 cards of
following denominations: 2, 3, 4, 5, 6, 7, 8, 9, 10, J, D, K, A. A sample of 5 cards is
selected randomly from a deck of cards.
Give your answers as arithmetic expressions. It is not necessary to calculate the result.

(A) How many different samples are possible?

µ ¶
52 52 · 51 · 50 · 49 · 48
nA = = = 52 · 51 · 5 · 49 · 4 = 2 598 960.
5 1·2·3·4·5

(B) Determine the number of different samples such that all of the cards have the same suit?
¡ ¢
For each of the four suits we have 13 5 possible samples. Thus,
µ ¶
13 13 · 12 · 11 · 10 · 9
nB = 4 · =4· = 4 · 13 · 11 · 9 = 5 148.
5 120

(C) Determine the number of different samples such that three of the cards have one denom-
ination, and the other two have another one?

We can choose the first denomination in 13 different ways, and then the
second one in 12 ways.¡ ¢Then, we can choose three cards out of four for the
first denomination
¡4¢ in 43 = 4 different ways, and two out of four for the
second in 2 = 6 ways. Thus,
µ ¶ µ ¶
4 4
nC = 13 · 12 · · = 13 · 12 · 4 · 6 = 3 744.
3 2
(D) Determine the number of different samples such that exactly three of the cards have the
same denomination, and the denominations of the other two are different?

We can choose a denomination for the first three cards in 13 different ways,
a denomination for the fourth card in 13 − 1 = 12 ways, and a denomination

4
¢ the fifth card in 13 − 2 = 11 ways. In determining
¡for ¡4¢ the suits, we have
3 = 4 possibilities
¡4¢ for the first three cards, 1 = 4 possibilities for the
fourth card, and 1 = 4 possibilities for the fifth card. Thus,
µ ¶ µ ¶ µ ¶
4 4 4
nD = 13 · 12 · 11 · · · = 13 · 12 · 11 · 4 · 4 · 4 = 109 824.
3 1 1

(E) Compare the probabilities of the situations described in (B), (C), and (D).
nB nC nD
The probabilities are PB = , PC = , and PD = .
nA nA nA
Since nC < nB < nD , we have PC < PB < PD .
The numbers are
5 148 3 744
PB = ≈ 0.19808% , PC = ≈ 0.14406% ,
2 598 960 2 598 960
109 824
PD = ≈ 4.22569% .
2 598 960