Exam (elaborations) TEST BANK FOR A Discrete Transition to Advanced Mathematics By Bettina Richmond and Thomas Richmond (Student's Solution Manual)

Exam (elaborations) TEST BANK FOR A Discrete Transition to Advanced Mathematics By Bettina Richmond and Thomas Richmond (Student's Solution Manual) Contents 1 Sets and Logic 1 1.1 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Set Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.4 Logic and Truth Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.5 Quantifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.6 Implications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2 Proofs 9 2.1 Proof Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 Mathematical Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.3 The Pigeonhole Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3 Number Theory 15 3.1 Divisibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.2 The Euclidean Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.3 The Fundamental Theorem of Arithmetic . . . . . . . . . . . . . . . . . . . . 17 3.4 Divisibility Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.5 Number Patterns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4 Combinatorics 23 4.1 Getting from Point A to Point B . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.2 The Fundamental Principle of Counting . . . . . . . . . . . . . . . . . . . . . 24 4.3 A Formula for the Binomial Coefficients . . . . . . . . . . . . . . . . . . . . . 25 4.4 Combinatorics with Indistinguishable Objects . . . . . . . . . . . . . . . . . . 25 4.5 Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 5 Relations 29 5.1 Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 5.2 Equivalence Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 5.3 Partial Orders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 5.4 Quotient Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 6 Functions and Cardinality 35 6.1 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 6.2 Inverse Relations and Inverse Functions . . . . . . . . . . . . . . . . . . . . . 36 6.3 Cardinality of Infinite Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 6.4 An Order Relation on Cardinal Numbers . . . . . . . . . . . . . . . . . . . . . 38 7 Graph Theory 39 7.1 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 7.2 Matrices, Digraphs, and Relations . . . . . . . . . . . . . . . . . . . . . . . . 40 7.3 Shortest Paths in Weighted Graphs . . . . . . . . . . . . . . . . . . . . . . . . 41 7.4 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 8 Sequences 45 8.1 Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 8.2 Finite Differences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 8.3 Limits of Sequences of Real Numbers . . . . . . . . . . . . . . . . . . . . . . . 47 8.4 Some Convergence Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 8.5 Infinite Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 8.6 Recurrence Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 9 Fibonacci Numbers and Pascal’s Triangle 53 9.1 Pascal’s Triangle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 9.2 The Fibonacci Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 9.3 The Golden Ratio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 9.4 Fibonacci Numbers and the Golden Ratio . . . . . . . . . . . . . . . . . . . . 56 9.5 Pascal’s Triangle and the Fibonacci Numbers . . . . . . . . . . . . . . . . . . 58 10 Continued Fractions 59 10.1 Finite Continued Fractions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 10.2 Convergents of a Continued Fraction . . . . . . . . . . . . . . . . . . . . . . . 60 10.3 Infinite Continued Fractions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 10.4 Applications of Continued Fractions . . . . . . . . . . . . . . . . . . . . . . . 61 This solution manual accompanies A Discrete Transition to Advanced Mathematics by Bettina Richmond and Tom Richmond. The text contains over 650 exercises. This manual includes solutions to parts of 210 of them. These solutions are presented as an aid to learning the material, and not as a substitute for learning the material. You should attempt to solve each problem on your own and consult the solutions manual only as a last resort. It is important to note that there are many different ways to solve most of the exercises. Looking up a solution before following through with your own approach to a problem may stifle your creativity. Consulting the solution manual after finding your own solution might reveal a different approach. There is no claim that the solutions presented here are the “best” solutions. These solutions use only techniques which should be familiar to you. Chapter 1 Sets and Logic 1.1 Sets 1. (a) True (b) The elements of a set are not ordered, so there is no “first” element of a set. 2. |{M, I, S, S, I, S, S, I, P, P, I}| = |{M, I, S, P}| = 4 7 = |{F, L,O,R, I,D,A}|. 3. (a) {1, 2, 3} ⊆ {1, 2, 3, 4} (b) 3 ∈ {1, 2, 3, 4} (c) {3} ⊆ {1, 2, 3, 4} (d) {a} ∈ {{a}, {b}, {a, b}} (e) ∅ ⊆ {{a}, {b}, {a, b}} (f) {{a}, {b}} ⊆ {{a}, {b}, {a, b}} 5. (a) A 0-element set ∅ has 20 = 1 subset, namely ∅. (b) A 1-element set {1} has 21 = 2 subsets, namely ∅ and {1}. (c) A 2-element set has 22 = 4 subsets. A 3-element set has 23 = 8 subsets. A 4-element set {1, 2, 3, 4} should have 24 = 16 subsets (d) The 16 subsets of {1, 2, 3, 4} are: ∅, {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4} (e) A 5-element set has 25 = 32 subsets. A 6-element set has 26 = 64 subsets. An n-element set has 2n subsets. 1 2 CHAPTER 1. SETS AND LOGIC 8. (a) 3, 4, 5, and 7: |S3| = |{t, h, r, e}| = 4 = |S4| = |{f, o, u, r}| = |S5| = |{f, i, v, e}| = |S7| = |{s, e, v, n}|. (b) S21 = S22 or S2002 = S2000, for example. (c) a ∈ S1000 and a 6∈ Sk for k = 1, 2, . . . , 999. (d) (i) True (ii) True (iii) True (iv) False (v) False (vi) True (vii) True (viii) False (ix) True (x) True (xi) True: {n, i, e} = S9 ∈ S. (xii) True (xiii) False (xiv) True (xv) True (xvi) False 9. (a) D1 = ∅,D2 = {2},D10 = {2, 5},D20 = {2, 5} (b) (i) True (ii) False (iii) False (iv) True (v) True (vi) False (vii) True (viii) False (ix) True (x) True (xi) False (xii) True (c) |D10| = |{2, 5}| = 2; |D19| = |{19}| = 1. (d) Observe that D2 = D4 = D8 = D16, D6 = D12 = D18, D3 = D9, D10 = D20. Thus |D| = |{D1,D2, . . . ,D20}| = |{D1,D2,D3,D5, D6,D7,D10,D11,D13,D14, D15,D17,D19}| = 13. 10. For example, let S1 = S2 = S3 = {1, 2, 3}, S4 = {4}, and S5 = {5}. Now S = {Sk}5 k=1 = {{1, 2, 3}, {4}, {5}}, so |S| = 3. 1.2 Set Operations 1. (a) S ∩ T = {1, 3, 5} (b) S ∪ T = {1, 2, 3, 4, 5, 7, 9} (c) S ∩ V = {3, 9} (d) S ∪ V = {1, 3, 5, 6, 7, 9} (e) (T ∩ V ) ∪ S = {3} ∪ S = S = {1, 3, 5, 7, 9} (f) T ∩ (V ∪ S) = T ∩ {1, 3, 5, 6, 7, 9} = {1, 3, 5}. (g) V × T = {(3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (6, 1), (6, 2), (6, 3), (6, 4), (6, 5), (9, 1), (9, 2), (9, 3), (9, 4), (9, 5)} (h) U × (T ∩ S) = {(3, 1), (3, 3), (3, 5), (6, 1), (6, 3), (6, 5), (9, 1), (9, 3), (9, 5)}. 2. (a) A ∩ D = {A♦}; cardinality 1 (c) A ∩ (S ∪ D) = {A♠,A♦}; cardinality 2 (e) (A ∩ S) ∪ (K ∩ D) = {A♠,K♦}; cardinality 2 (g) K ∩ Sc = {K♣,K♦,K♥}; cardinality 3 (i) (A ∪ K)c ∩ S = {2♠, 3♠, 4♠, 5♠, 6♠, 7♠, 8♠, 9♠, 10♠, J♠,Q♠}; cardinality 11 (n) K S = {K♥,K♣,K♦}; cardinality 3 1.3. PARTITIONS 3 7. (x, y) ∈ A × (B ∩ C) ⇐⇒ x ∈ A, y ∈ B ∩ C ⇐⇒ x ∈ A, y ∈ B and y ∈ C ⇐⇒ x ∈ A and y ∈ B and x ∈ A and y ∈ C ⇐⇒ (x, y) ∈ (A × B) ∩ (A × C). This shows that the elements of A×(B ∩C) are precisely those of (A×B) ∩(A×C), and thus the two sets are equal. 9. The conditions are not equivalent. For example, the collection {S1, S2} where S1 = S2 6= ∅ satisfies (Si ∩ Sj 6= ∅ ⇒ Si = Sj ), but not (Si ∩ Sj 6= ∅ ⇒ i = j). However, if the sets of the collection {Si|i ∈ I} are distinct, the statements will be equivalent. 10. Let A be the set of students taking Algebra and let S be the set of students taking Spanish. Now |A ∪ S| = |A| + |S| − |A ∩ S| = 43 + 32 − 7 = 68. Thus, there are 68 students taking Algebra or Spanish. 12. A tree diagram for the outcomes will have 2 branches for the choice of meat, each stem of which has 7 branches for the possible choices for vegetables, and each of these stems has 5 branches for the choice of dessert. Thus, 2 choices for meat, 7 choices for vegetable, and 5 choices for dessert give 2 · 7 · 5 = 70 choices for the special. 15. Observe that there are not 4 · 3 options, for Luis can not take both physics and chemistry at 2:00. There are only 11 scheduling options, as shown in the tree diagram below. PPPP 234 PPPP 234 PPPP 234 PPPP 34 2 1 12 11 1.3 Partitions 3. (a) Not necessarily. Some Bi may be empty. (b) Yes (S 6= ∅ and L 6= ∅), S ∪ L = B, and S ∩ L = ∅. (c) No. S and P partition A, but D has nonempty intersection with S or P yet D 6= S and D 6= P. (d) No. X = ∅. (e) No. R ∩ S = S 6= ∅, but R 6= S. 4 CHAPTER 1. SETS AND LOGIC 5. (a) Yes. (b) No. L3 6= L4 even though L3 ∩ L4 = {(0, 0)} 6= ∅. Also, (0, 1) 6∈ S D. (c) Yes. (d) Yes. (e) No. (0, 1) 6∈ S G. Also, P3 6= P4 yet P3 ∩ P4 = {(0, 0)} 6= ∅. (f) No. (π, π) 6∈ S H. 8. Each Ci is nonempty: Given i ∈ I, Bi 6= ∅, so ∃b ∈ Bi, and √b ∈ Ci. C is a mutually disjoint collection: If Ci ∩ Cj 6= ∅, then ∃z ∈ Ci ∩ Cj , and from the definition of Ci and Cj , we have z2 ∈ Bi ∩ Bj . Since Bi ∩ Bj 6= ∅ and {Bi|i ∈ I} is a partition, it follows that Bi = Bj , so {x ∈ R|x2 ∈ Bi} = {x ∈ R|x2 ∈ Bj}, that is, Ci = Cj . S C = R: Clearly S C ⊆ R, so it suffices to show R ⊆ S S C. Given x ∈ R, x2 ∈ [0,1) = B, so x2 ∈ Bi for some i ∈ I, which shows x ∈ Ci. Thus, x ∈ R ⇒ x ∈ S C, as needed. 11. (a) Given any partition P of S, each block of P may be partitioned into singleton sets (that is, into blocks of D), so D is finer than any partition P of S. (b) The coarsest partition of a set S is the one-block partition I = {S}. Given any partition P of S, the block S of I is further partitioned by the blocks of P, so ever partition P of S is finer than I. (c) Since each block of the coarser partition Q is the union of one or more blocks of the finer partition P, we have |P| ≥ |Q|. (d) No. P = {(−1, 0], (0,1)} and Q = {(−1, 5], (5, 6), [6,1)} are partitions of R with |P| ≤ |Q|, but neither partition is a refinement of the other. 1.4 Logic and Truth Tables 1. (a) S∧ ∼ G (b) H∨ ∼ S (c) ∼ (S ∧ G) (d) (S ∧ G) ∨ (∼ H) (e) (S∨ ∼ S) ∧ G (f) S ∧ H ∧ G (g) (S ∧ H) ∨ (∼ G) 7. (a) P Q P ∧ Q ∼ (P ∧ Q) ∼ Q ∼ (P ∧ Q)∧ ∼ Q T T T F F F T F F T T T F T F T F F F F F T T T ∼ (P ∧Q)∧ ∼ Q = ∼ Q since the columns for these two statements are identical. (b) Note that if Q fails, then (P ∧Q) fails, so that Q fails and (P ∧Q) fails. On the other hand, if Q fails and some other conditions occur (namely, (P ∧ Q) fails), then Q fails. 1.5. QUANTIFIERS 5 10. Answers may vary. P Q (a) (b) (c) (d) (e)