Discrete Mathematics: An Open Introduction, 3rd Edition

Description

Discrete Mathematics: An Open Introduction is a free, open source textbook appropriate for a first or second year undergraduate course for math majors, especially those who will go on to teach. Since Spring 2013, the book has been used as the primary textbook or a supplemental resource at more than 75 colleges and universities around the world (see the partial adoptions list). The text is endorsed by the American Institute of Mathematics' Open Textbook Initiative and is well reviewed on the Open Textbook Library. This 3rd edition brings many improvements, including nearly 100 new exercises, a new section on trees in the graph theory chapter, and improved exposition throughout. Previous editions will continue to be available indefinitely. A few times a year, the text is updated with a new "printing" to correct errors. See the errata list for more information. New for Fall 2019: Online homework sets are available through Edfinity or as WeBWorK sets from the author. Additional exercises have been added since Spring 2020. Please contact the author with feedback and suggestions, or if you are decide to use the book in a course you are teaching. Acknowledgements Preface How to use this book Introduction and Preliminaries What is Discrete Mathematics? Mathematical Statements Atomic and Molecular Statements Implications Predicates and Quantifiers Exercises Sets Notation Relationships Between Sets Operations On Sets Venn Diagrams Exercises Functions Describing Functions Surjections, Injections, and Bijections Image and Inverse Image Exercises Counting Additive and Multiplicative Principles Counting With Sets Principle of Inclusion/Exclusion Exercises Binomial Coefficients Subsets Bit Strings Lattice Paths Binomial Coefficients Pascal's Triangle Exercises Combinations and Permutations Exercises Combinatorial Proofs Patterns in Pascal's Triangle More Proofs Exercises Stars and Bars Exercises Advanced Counting Using PIE Counting Derangements Counting Functions Exercises Chapter Summary Chapter Review Sequences Describing Sequences Exercises Arithmetic and Geometric Sequences Sums of Arithmetic and Geometric Sequences Exercises Polynomial Fitting Exercises Solving Recurrence Relations The Characteristic Root Technique Exercises Induction Stamps Formalizing Proofs Examples Strong Induction Exercises Chapter Summary Chapter Review Symbolic Logic and Proofs Propositional Logic Truth Tables Logical Equivalence Deductions Beyond Propositions Exercises Proofs Direct Proof Proof by Contrapositive Proof by Contradiction Proof by (counter) Example Proof by Cases Exercises Chapter Summary Chapter Review Graph Theory Definitions Exercises Trees Properties of Trees Rooted Trees Spanning Trees Exercises Planar Graphs Non-planar Graphs Polyhedra Exercises Coloring Coloring in General Coloring Edges Exercises Euler Paths and Circuits Hamilton Paths Exercises Matching in Bipartite Graphs Exercises Chapter Summary Chapter Review Additional Topics Generating Functions Building Generating Functions Differencing Multiplication and Partial Sums Solving Recurrence Relations with Generating Functions Exercises Introduction to Number Theory Divisibility Remainder Classes Properties of Congruence Solving Congruences Solving Linear Diophantine Equations Exercises Selected Hints Selected Solutions List of Symbols Index