Advanced Discrete Mathematics

(This course has been developed but has not yet been offered.)

Course Description

Prerequisite: Advanced Trigonometry/Precalculus (or the equivalent)

Discrete mathematics is the branch of mathematics that studies separate, individual objects that are countable rather than the continuous structures studied in Calculus. By its very nature, studying discrete mathematics is foundational for both mathematics and the use of computers. In this introductory course, students will work with logic, set theory, combinatorics, sequences and series (with recurrence relations), and mathematical induction. If time permits, the course will end with an introduction to graph theory and elementary number theory. Great emphasis will be placed on mathematical rigor and the writing of proofs.

The main textbook for the course will be Oscar Levin's Discrete Mathematics: An Open Introduction (4th Edition). This is a book that the author himself has made available electronically for free. 

• Website: https://discrete.openmathbooks.org/dmoi4.html

• PDF File: https://discrete.openmathbooks.org/pdfs/dmoi4.pdf

• To order a printed copy, here is the Amazon page with the ISBN: https://www.amazon.com/Discrete-Mathematics-Open-Introduction-Applications/dp/1032966165 

• Supplementary Literature: Richard Hammack's Book of Proof - Third Edition (which the author has made available for free online: https://richardhammack.github.io/BookOfProof/)

Please note: the posted lecture notes were originally intended for the instructor's purposes only and may not be complete. By no means are the posted lecture notes meant to serve as a substitute for attendance in class and the reading of the text. It is not guaranteed that they are without error either. Should there be any errors, notify and inform the instructor of the error immediately or as soon as possible. 

Very important: learning math is about doing problems. That is how you get better. While the complete answers to all questions are available to you, it is crucial that before consulting an answer, you must give the question a good try on your own. If you read the question and just immediately read the answer, then you will not learn. 

Unit 1: Logic and Proof

1. Assignments Sheet

2. Introduction to Logic - Connectives and Quantifiers (Lecture Notes)

3. Implications and Arguments (Lecture Notes)

4. Laws of Logic (Lecture Notes)

5. Techniques of Proof (Lecture Notes)

6. Supplemental Problems Worksheet - Implications

7. Supplemental Problems Worksheet - Logic

Unit 2: SEts, Relations, anD FuNctions

1. Assignments Sheet

2. Chapter 2 of Steven Lay's Analysis with an Introduction to Proof on Set Theory

   • Solutions and Errata

3. Set Operations - Introduction to Set Theory (Lecture Notes)

4. Relations (Lecture Notes)

5. Functions (Lecture Notes)

6. Cardinality (Lecture Notes)

Unit 3: Combinatorics

1. Assignments Sheet

2. Overview of Counting (Lecture Notes)

3. Lattice Paths and Bit Strings (Lecture Notes)

4. More on Counting - Examples (Lecture Notes)

5. PIE - Principle of Inclusion/Exclusion (Lecture Notes)

6. Combinations, Permutations, and Multisets (Lecture Notes)

7. Pascal's Arithmetical Triangle, Identities, and Combinatorial Proofs (Lecture Notes)

8. The Binomial Theorem (Lecture Notes)

9. Counting Worksheet

10. Sticks and Stones Supplemental Problems Worksheet

Unit 4: Sequences, series, and Induction

1. Assignments Sheet

2. Sequences (Lecture Notes)

3. Series (Lecture Notes)

4. Arithmetic and Geometric Sequences (Lecture Notes)

5. Arithmetic Series and Polynomial Fitting (Lecture Notes)

6. Geometric Series and Solving Recurrence Relations (Lecture Notes)

7. Mathematical Induction - Part 1 (Lecture Notes)

8. Mathematical Induction - Part 2 (Lecture Notes)

9. Mathematical Induction - Supplemental Problems from Steven Lay

10. (Additional) The Construction of Numbers (Beginning with Peano Axioms)

(Additional Topic) Koch's Snowflake

Unit 5: Graph Theory

1. Assignments Sheet

2. Introduction to Graph Theory: Konigsberg Bridge Problem and Eulerian Walks

3. Euler's Formula for Planar Graphs and Polyhedra

Unit 6: Number ThEory (If Time Allows)

Time-permitting, we will cover this unit with an inquiry-based approach known as the Moore Method. For this, we will use chapter 1 of Jim Hefferon's text An Inquiry-Based Introduction to Proofs. With the proof-writing skills you have developed throughout the semester, you will prove the results of chapter 1.