Page 5 - Discrete Mathematics and Its Applications

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