Contents xiii Structural Induction 176 Important Concepts,Formulas,and Theorems 178 Problems 180 4.2 Recursion,Recurrences,and Induction 183 Recursion 183 Examples of First-Order Linear Recurrences 185 Iterating a Recurrence 187 Geometric Series 188 First-Order Linear Recurrences 191 Important Concepts,Formulas,and Theorems 195 Problems 197 4.3 Growth Rates of Solutions to Recurrences 198 Divide and Conquer Algorithms 198 Recursion Trees 201 Three Different Behaviors 209 Important Concepts,Formulas,and Theorems 210 Problems 212 4.4 The Master Theorem 214 Master Theorem 214 Solving More General Kinds of Recurrences 217 Extending the Master Theorem 218 Important Concepts,Formulas,and Theorems 220 Problems 221 4.5 More General Kinds of Recurrences 222 Recurrence Inequalities 222 The Master Theorem for Inequalities 223 A Wrinkle with Induction 225 Further Wrinkles in Induction Proofs 227 Dealing with Functions Other Than ne 230 Important Concepts,Formulas,and Theorems 232 Problems 233Contents xiii Structural Induction 176 Important Concepts, Formulas, and Theorems 178 Problems 180 4.2 Recursion, Recurrences, and Induction 183 Recursion 183 Examples of First-Order Linear Recurrences 185 Iterating a Recurrence 187 Geometric Series 188 First-Order Linear Recurrences 191 Important Concepts, Formulas, and Theorems 195 Problems 197 4.3 Growth Rates of Solutions to Recurrences 198 Divide and Conquer Algorithms 198 Recursion Trees 201 Three Different Behaviors 209 Important Concepts, Formulas, and Theorems 210 Problems 212 4.4 The Master Theorem 214 Master Theorem 214 Solving More General Kinds of Recurrences 217 Extending the Master Theorem 218 Important Concepts, Formulas, and Theorems 220 Problems 221 4.5 More General Kinds of Recurrences 222 Recurrence Inequalities 222 The Master Theorem for Inequalities 223 A Wrinkle with Induction 225 Further Wrinkles in Induction Proofs 227 Dealing with Functions Other Than nc 230 Important Concepts, Formulas, and Theorems 232 Problems 233