vili Contents 4 More Proof 135 19 Contradiction 135 Proof by Contrapositive 135 Reductio ad Absurdum 137 A Matter of Style 141 Recap 141 Exercises 141 20 Smallest Counterexample 142 Well-Ordering 148 Recap 153 Exercises 153 And Finally 154 21 Induction 155 The Induction Machine 155 Theoretical Underpinnings 157 Proof by Induction 157 Proving Equations and Inequalities 160 Other Examples 162 Strong Induction 163 A More Complicated Example 165 A Matter of Style 168 Recap 168 Exercises 168 22 Recurrence Relations 171 First-Order Recurrence Relations 172 Second-Order Recurrence Relations 175 The Case of the Repeated Root 178 Sequences Generated by Polynomials 180 Recap 187 Exercises 188 Chapter 4 Self Test 190 5 Functions 193 23 Functions 193 Domain and Image 195 Pictures of Functions 196 Counting Functions 197 Inverse Functions 198 Counting Functions,Again 202 Recap 203 Exercises 203viii Contents 4 More Proof 135 f 19 Contradiction 135 Proof by Contrapositive 135 Reductio ad Absurdum 137 A Matter of Style 141 Recap 141 Exercises 141 20 Smallest Counterexample 142 Well-Ordering 148 Recap 153 Exercises 153 And Finally 154 21 Induction 155 The Induction Machine 155 Theoretical Underpinnings 157 Proof by Induction 157 Proving Equations and Inequalities 160 Other Examples 162 Strong Induction 163 A More Complicated Example 165 A Matter of Style 168 Recap 168 Exercises 168 22 Recurrence Relations 171 First-Order Recurrence Relations 172 Second-Order Recurrence Relations 175 The Case of the Repeated Root 178 Sequences Generated by Polynomials 180 Recap 187 Exercises 188 Chapter 4 Self Test 190 5 Functions 193 23 Functions 193 Domain and Image 195 Pictures of Functions 196 Counting Functions 197 Inverse Functions 198 Counting Functions, Again 202 Recap 203 Exercises 203