Discrete Mathematics: An Open Introduction, 3rd Edition

✍ Scribed by Oscar Levin

• Publisher: discretetext.oscarlevin.com
• Year: 2021
• Tongue: English
• Leaves: 414
• Edition: 3
• Category: Library

✦ Synopsis

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.

✦ Table of Contents

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