Contents CHAPTER1 Counting 31 1.1 Basic Counting 31 The Sum Principle 31 Abstraction 33 Summing Consecutive Integers 33 The Product Principle 34 Two-Element Subsets 36 Important Concepts, Formulas, and Theorems 37 Problems 38 1.2 Counting Lists, Permutations, and Subsets 40 Using the Sum and Product Principles 40 Lists and Functions 42 The Bijection Principle 44 k-Element Permutations of a Set 45 Counting Subsets of a Set 46 Important Concepts, Formulas, and Theorems 48 Problems 50 1.3 Binomial Coeffiients 52 Pascal’s Triangle 52 A Proof Using the Sum Principle 54 The Binomial Theorem 56 Labeling and Trinomial Coefficient 58 Important Concepts, Formulas, and Theorems 59 Problems 60 1.4 Relations 62 What Is a Relation? 62 Functions as Relations 63 Properties of Relations 63 Equivalence Relations 66 Partial and Total Orders 69 Important Concepts, Formulas, and Theorems 71 Problems 72 1.5 Using Equivalence Relationsin Counting 73 The Symmetry Principle Equivalence Relations 75 The Quotient Principle 76 Equivalence Class Counting 76 Multisets 78 The Bookcase Arrangement Problem 80 The Number of k-Element Multisets of an n-Element Set 81 Usingthe Quotient Principle to Explain a Quotient 82 Important Concepts, Formulas, and Theorems 83 Problems 84 CHAPTER2 Cryptography and Number Theory 89 2.1 Cryptography and Modular Arithmetic 89 Introduction to Cryptography 89 Private-Key Cryptography 90 Public-Key Cryptosystems 93 Arithmetic Modulo n 95 Cryptography Using Addition mod n 98 Cryptography Using Multiplication mod n 99 Important Concepts, Formulas, and Theorems 101 Problems 102 2.2 Inverses and Greatest Common Divisors 105 Solutions to Equations and Inverses mod n 105 Inverses mod n 106 Converting Modular Equations to Normal Equations 109 Greatest Common Divisors 110 Euclid’s Division Theorem 111 Euclid’s GCD Algorithm 114 Extended GCD Algorithm 115 Computing Inverses 118 Important Concepts, Formulas, and Theorems 119 Problems 120 2.3 The RSA Cryptosystem 123 Exponentiation mod n 123 The Rules of Exponents 123 Fermat’s Little Theorem 126 The RSA Cryptosystem 127 The Chinese Remainder Theorem 131 Important Concepts, Formulas, and Theorems 132 Problems 134 2.4 Details of the RSA Cryptosystem 136 Practical Aspects of Exponentiation mod n 136 How Long Does It Take to Use the RSA Algorithm? 139 How Hard Is Factoring? 140 Finding Large Primes 140 Important Concepts, Formulas, and Theorems 143 Problems 144 CHAPTER3 Reflectionon Logic and Proof 147 3.1 Equivalence and Implication 147 Equivalence of Statements 147 Truth Tables 150 DeMorgan’s Laws 153 Implication 155 If and Only If 156 Important Concepts, Formulas, and Theorems 159 Problems 161 3.2 Variables and Quantifier 163 Variables and Universes 163 Quantifier 164 Standard Notation for Quantificatio 166 Statements about Variables 168 Rewriting Statements to Encompass Larger Universes 168 Proving Quantifie Statements Trueor False 169 Negation of Quantifie Statements 170 Implicit Quantificatio 173 Proof of Quantifie Statements 174 Important Concepts, Formulas, and Theorems 175 Problems 177 3.3 Inference 179 Direct Inference (Modus Ponens) and Proofs 179 Rules of Inference for Direct Proofs 181 Contrapositive Ruleof Inference 183 Proof by Contradiction 185 Important Concepts, Formulas, and Theorems 188 Problems 189 CHAPTER4 Induction, Recursion, and Recurrences 191 4.1 Mathematical Induction 191 Smallest Counterexamples 191 The Principle of Mathematical Induction 195 Strong Induction 199 Induction in General 201 A Recursive Viewof Induction 203 Structural Induction 206 Important Concepts, Formulas, and Theorems 208 Problems 210 4.2 Recursion, Recurrences, and Induction 213 Recursion 213 Examples of First-Order Linear Recurrences 215 Iteratinga Recurrence 217 Geometric Series 218 First-Order Linear Recurrences 221 Important Concepts,