Note, this is the corrected Fall 2015 edition. A new edition will be available August 2016
This gentle introduction to discrete mathematics is written for first and second year math majors, especially those who intend to teach. The text began as a set of lecture notes for the discrete mathematics course at the University of Northern Colorado. This course serves both as an introduction to topics in discrete math and as the "introduction to proof" course for math majors. The course is usually taught with a large amount of student inquiry, and this text is written to help facilitate this.
Four main topics are covered: counting, sequences, logic, and graph theory. Along the way proofs are introduced, including proofs by contradiction, proofs by induction, and combinatorial proofs. The book contains 299 exercises, all with solutions (or at least a hint), as well as 45 additional more involved problems suitable for homework. There are also "Investigate!" problems throughout the text to support active, inquiry based learning.
While there are many fine discrete math textbooks available, this text has the following advantages: It is written to be used in an inquiry rich course. It is written to be used in a course for future math teachers. It is open source, with low cost print editions and free electronic editions.
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
