iv Contents
5 Induction and Recursion ..........................................311
5.1 Mathematical Induction ......................................................311
5.2 Strong Induction and Well-Ordering ...........................................333
5.3 Recursive Definitions and Structural Induction..................................344
5.4 Recursive Algorithms ........................................................360
5.5 Program Correctness .........................................................372
End-of-Chapter Material .....................................................377
6 Counting ..........................................................385
6.1 The Basics of Counting.......................................................385
6.2 The Pigeonhole Principle .....................................................399
6.3 Permutations and Combinations ...............................................407
6.4 Binomial Coefficients and Identities ...........................................415
6.5 Generalized Permutations and Combinations ...................................423
6.6 Generating Permutations and Combinations ....................................434
End-of-Chapter Material .....................................................439
7 Discrete Probability ...............................................445
7.1 An Introduction to Discrete Probability ........................................445
7.2 Probability Theory...........................................................452
7.3 Bayes’Theorem .............................................................468
7.4 Expected Value and Variance..................................................477
End-of-Chapter Material .....................................................494
8 Advanced Counting Techniques ...................................501
8.1 Applications of Recurrence Relations ..........................................501
8.2 Solving Linear Recurrence Relations ..........................................514
8.3 Divide-and-Conquer Algorithms and Recurrence Relations.......................527
8.4 Generating Functions ........................................................537
8.5 Inclusion–Exclusion .........................................................552
8.6 Applications of Inclusion–Exclusion ...........................................558
End-of-Chapter Material .....................................................565
9 Relations ..........................................................573
9.1 Relations and Their Properties ................................................573
9.2 n-ary Relations and Their Applications.........................................583
9.3 Representing Relations .......................................................591
9.4 Closures of Relations ........................................................597
9.5 Equivalence Relations........................................................607
9.6 Partial Orderings ............................................................618
End-of-Chapter Material .....................................................633
