Discrete Mathematics: An Open Introduction

Description

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