Exam 2

100 points possible.

1. (10 pts.) Evaluate each of these. (You may use your fancy calculator.)

(a)

5! 3!

(b)

0!

(c)

P(7,3)

(d)

æ ç ç ç è 8 3 ö ÷ ÷ ÷ ø

2. (10 pts.) Find an explicit formula for the sequence with the given initial terms.

1 2 ,- 2 3 , 3 4 ,- 4 5 , 5 6 ,- 6 7

3. (10 pts.) One urn contains one blue ball and three red balls (labeled R1, R2, and R3). A second urn contains two red balls (R4 and R5) and two blue balls (B1 and B2). An experiment is performed in which one of the two urns is chosen at random and then two balls are randomly chosen from it, one after the other without replacement.

(a) Construct the possibility tree showing all possible outcomes of this experiment.

(b) What is the total number of outcomes of this experiment?

(c) What is the probability that two red balls are chosen?

4. (10 pts.) A standard deck of 52 cards contains 4 different suits, with 13 different ranks in each suit. There are 2,598,960 possible five-card hands.

(a) How many ``three-of-a-kind'' hands are there? (A three-of-a-kind consists of three cards of the same rank, and two other cards of different ranks.)

(b) How many ``one-pair'' hands are there? (A one-pair consists of two cards of one rank, and three other cards all of different ranks.)

5. (10 pts.) (a) How many onto functions are there from a set with three elements to a set with two elements?

(b) How many onto functions are there from a set with three elements to a set with five elements?

6. (10 pts.) Find the terms t₂, t₃, t₄, and t₅ for this recursively defined sequence.

tk=2tk-1+tk-2,    for all integers k ³ 2

t0=2,    t1=3

7. (10 pts.) (a) Write a negation for the following statement: " sets S, $ a set T such that SÇT=Æ. Which is true, the statement or its negation? Explain briefly (i.e., don't prove, but support your answer).

(b) Write a negation for the following statement: $ a set S such that " sets T, SÈT=Æ. Which is true, the statement or its negation? Explain briefly (i.e., don't prove, but support your answer).

8. (15 pts.) Here is a proof of a theorem. Fill in the blanks. (Note: Some blanks are filled by a single variable, others by a short phrase, and others by one or more sentences.)

Theorem For any sets A, B, and C, AÇ(BÈC)=(AÇB)È(AÇC). 

Proof. Suppose A, B, and C are particular but arbitrarily chosen sets.

Step 1-Show AÇ(BÈC) Í (AÇB)È(AÇC):

Let x Î AÇ(BÈC). [We must show that x Î (a).] By definition of intersection, x Î (b) and x Î (c). Thus, x Î A and by definition of union, x Î B or (d).

Case 1

(x Î B): In this case, since we know x Î A, then by definition of intersection x Î (e), and so by definition of union, x Î (AÇB)È(AÇC).

Case 2

(x Ï B): In this case, we must have x Î C. Since we know x Î A, then (f).

[So AÇ(BÈC) Í (AÇB)È(AÇC) by definition of subset.]

Step 2-Show (AÇB)È(AÇC) Í AÇ(BÈC):

Let x Î (AÇB)È(AÇC). [We must show that x Î (g).] By definition of union, x Î (h) or x Î (i).

Case 1

(x Î AÇB): In this case, by definition of intersection x Î (j) and x Î (k). Since x Î B, by definition of union, x Î BÈC. Hence x Î A and x Î BÈC, and so by definition of intersection, x Î (l).

Case 2

(x Ï AÇB): In this case, we must have x Î AÇC. Then (m).

[Thus (AÇB)È(AÇC) Í AÇ(BÈC) by definition of subset.]

[Since both subset relations have been proved, it follows by definition of set equality that (n).]    

9. (15 pts.) Choose ONE of these two proofs and do it. If you try both, clearly mark the one you want graded, or your evil instructor might grade the worse. (The next page is blank, for your convenience.)

A. Prove the following statement by contraposition.

If a product of two positive real numbers is greater than 10000, then at least one of the numbers is greater than 100.

B. Prove the following statement by mathematical induction.

12+22+...+n2= n(n+1)(2n+1) 6 ,    "integers n ³ 1.