63
A Discrete
Transition
to Advanced
Mathematics
Second Edition
Bettina Richmond
Thomas Richmond
, Pure and Applied
Sally
The UNDERGRADUATE TEXTS • 63
SERIES
A Discrete
Transition
to Advanced
Mathematics
Second Edition
Bettina Richmond
Thomas Richmond
,Contents
Preface ix
Preface to the Second Edition xiii
Chapter 1. Sets and Logic 1
1.1. Sets 2
1.2. Set Operations 9
1.3. Partitions 23
1.4. Logic and Truth Tables 27
1.5. Quantifiers 37
1.6. Implications 43
Chapter 2. Proofs 53
2.1. Proof Techniques 54
2.2. Mathematical Induction 66
2.3. The Pigeonhole Principle 76
Chapter 3. Number Theory 85
3.1. Divisibility 85
3.2. The Euclidean Algorithm 96
3.3. The Fundamental Theorem of Arithmetic 105
3.4. Divisibility Tests 113
3.5. Number Patterns 124
Chapter 4. Combinatorics 135
4.1. Getting from Point A to Point B 135
4.2. The Fundamental Principle of Counting 145
v
, vi Contents
4.3. A Formula for the Binomial Coefficients 156
4.4. Permutations with Indistinguishable Objects 164
4.5. Combinations with Indistinguishable Objects 170
4.6. The Inclusion-Exclusion Principle 177
4.7. Circular Permutations 184
4.8. Probability 189
Chapter 5. Relations 197
5.1. Relations 197
5.2. Equivalence Relations 206
5.3. Partial Orders 213
5.4. Quotient Spaces 223
Chapter 6. Functions and Cardinality 235
6.1. Functions 236
6.2. Inverse Relations and Inverse Functions 246
6.3. Cardinality of Infinite Sets 255
6.4. An Order Relation for Cardinal Numbers 262
Chapter 7. Graph Theory 271
7.1. Graphs 272
7.2. Matrices, Digraphs, and Relations 282
7.3. Shortest Paths in Weighted Graphs 295
7.4. Trees 304
Chapter 8. Sequences 313
8.1. Sequences 314
8.2. Finite Differences 320
8.3. Limits of Sequences of Real Numbers 329
8.4. Some Convergence Properties 337
8.5. Infinite Arithmetic 342
8.6. Recurrence Relations 356
Chapter 9. Fibonacci Numbers and Pascal’s Triangle 371
9.1. Pascal’s Triangle 372
9.2. The Fibonacci Numbers 385
9.3. The Golden Ratio 396
9.4. Fibonacci Numbers and the Golden Ratio 404
9.5. Pascal’s Triangle and the Fibonacci Numbers 412
A Discrete
Transition
to Advanced
Mathematics
Second Edition
Bettina Richmond
Thomas Richmond
, Pure and Applied
Sally
The UNDERGRADUATE TEXTS • 63
SERIES
A Discrete
Transition
to Advanced
Mathematics
Second Edition
Bettina Richmond
Thomas Richmond
,Contents
Preface ix
Preface to the Second Edition xiii
Chapter 1. Sets and Logic 1
1.1. Sets 2
1.2. Set Operations 9
1.3. Partitions 23
1.4. Logic and Truth Tables 27
1.5. Quantifiers 37
1.6. Implications 43
Chapter 2. Proofs 53
2.1. Proof Techniques 54
2.2. Mathematical Induction 66
2.3. The Pigeonhole Principle 76
Chapter 3. Number Theory 85
3.1. Divisibility 85
3.2. The Euclidean Algorithm 96
3.3. The Fundamental Theorem of Arithmetic 105
3.4. Divisibility Tests 113
3.5. Number Patterns 124
Chapter 4. Combinatorics 135
4.1. Getting from Point A to Point B 135
4.2. The Fundamental Principle of Counting 145
v
, vi Contents
4.3. A Formula for the Binomial Coefficients 156
4.4. Permutations with Indistinguishable Objects 164
4.5. Combinations with Indistinguishable Objects 170
4.6. The Inclusion-Exclusion Principle 177
4.7. Circular Permutations 184
4.8. Probability 189
Chapter 5. Relations 197
5.1. Relations 197
5.2. Equivalence Relations 206
5.3. Partial Orders 213
5.4. Quotient Spaces 223
Chapter 6. Functions and Cardinality 235
6.1. Functions 236
6.2. Inverse Relations and Inverse Functions 246
6.3. Cardinality of Infinite Sets 255
6.4. An Order Relation for Cardinal Numbers 262
Chapter 7. Graph Theory 271
7.1. Graphs 272
7.2. Matrices, Digraphs, and Relations 282
7.3. Shortest Paths in Weighted Graphs 295
7.4. Trees 304
Chapter 8. Sequences 313
8.1. Sequences 314
8.2. Finite Differences 320
8.3. Limits of Sequences of Real Numbers 329
8.4. Some Convergence Properties 337
8.5. Infinite Arithmetic 342
8.6. Recurrence Relations 356
Chapter 9. Fibonacci Numbers and Pascal’s Triangle 371
9.1. Pascal’s Triangle 372
9.2. The Fibonacci Numbers 385
9.3. The Golden Ratio 396
9.4. Fibonacci Numbers and the Golden Ratio 404
9.5. Pascal’s Triangle and the Fibonacci Numbers 412
