Discrete Mathematics: An Open Introduction

Oscar Levin’s fourth edition of Discrete Mathematics: An Open Introduction develops reasoning through questions, constructions, examples, and practice. Its numbered Chapters 0–6 proceed through preliminaries, logic, graphs, counting, sequences, a return to discrete structures, and additional topics. Earlier editions have a different order, so exercise references should be matched to this edition. The guide emphasizes how to select and justify a method. It is intended to accompany active problem solving, including attempts that fail and reveal which assumptions a successful argument needs.

Chapter-by-chapter summaries

0. Introduction and preliminaries

Discrete mathematics studies individually distinguishable structures such as sets, sequences, relations, functions, and graphs. The opening questions encourage investigation before formal methods are supplied. Distinguish a sequence’s ordered positions from set membership, and a general relation from a function’s restricted assignment rule. Represent one example as a diagram, list, formula, and prose description. Explain what information each reveals. Definitions become useful tools when they resolve a specific ambiguity, rather than vocabulary learned without a problem to organize.

1. Logic and proofs

Predicates become statements when variables are specified or quantified. Implications, equivalences, truth tables, and deductions support direct proof, contraposition, and contradiction. These methods are applied to the structures introduced earlier. Match the method to the claim’s form: identify an implication’s hypothesis and target, and use a counterexample to refute a universal assertion. Negation changes the quantifier as well as its condition. Explain why the method establishes the required conclusion instead of merely producing plausible intermediate algebra.

2. Graph theory

Vertices and edges model networks, routes, and relationships. Degree, paths, cycles, connectedness, trees, and colouring answer different structural questions. Incidence counting constrains possible graphs, while similar drawings can hide different adjacencies. Separate properties of the underlying graph from accidents of its drawing. For a route problem, ask whether vertices or edges must be visited. For colouring, define what a conflict means in the application. A claimed optimum requires both a construction and a reason fewer resources cannot work.

3. Counting

Addition counts disjoint alternatives; multiplication counts successive choices. Permutations and combinations depend on order, while repetition creates another distinction. Binomial coefficients connect selections with expansion and combinatorial identities. Overcounting means multiple descriptions represent the same object, not simply that the arithmetic is inaccurate. Define an outcome before calculating, then check that the construction includes every valid outcome exactly once. Probability applications likewise require an appropriate outcome space; selecting a formula from a keyword does not establish that its assumptions hold.

4. Sequences

Explicit formulas, recurrences, differences, and sums provide different views of ordered numerical information. A recursive definition explains construction, while a closed form may expose growth or permit direct evaluation. A finite list never uniquely determines its continuation. Induction establishes that a proposed relationship holds across all relevant indices. Check initial conditions and identify precisely how the induction hypothesis is used. Compare algebraic summation with a structural counting argument to see how earlier ideas can explain the same sequence from another direction.

5. Discrete structures revisited

Sets, functions, and relations return with more formal tools available. Set identities can be proved through arbitrary elements; mapping properties depend on domains and codomains; relations can express equivalence or order when they meet the definitions. Construct examples and nonexamples separately for each property. A single collection supports many different relations, so the rule must be specified before classifying it. This chapter shows why revisiting introductory concepts is productive: proof techniques now explain relationships that the preliminary chapter could only introduce.

6. Additional topics

Extensions including generating functions and number theory demonstrate the reach of the main toolkit. Generating functions encode sequences as coefficients, transforming selected counting operations into algebra. Number theory applies precise concepts such as divisibility and congruence to integer relationships. Explain what every coefficient counts and state the modulus in modular arguments. Check a small case by enumeration before using an abstract method. The aim is to see a connected set of reasoning techniques opening new areas, while keeping each representation tied to the original problem.

Study instructions

1. Use the fourth-edition order and verify exercise references before working from another edition’s notes.
2. Attempt section previews first; record why your initial approach succeeded or failed.
3. Define objects and constraints in words before solving graph or counting problems.
4. Complete a mixed weekly set containing a proof, construction, count, and recurrence, explaining each method choice.

Questions for reflection

• Can two drawings encode the same graph?
• How do you prove a count has no omissions or duplicates?
• Why does a plausible sequence formula still need proof?

Sources and coverage

This original reading guide covers the linked edition’s main chapters, or the principal sections of its two-chapter calculus text. Consult the source for full arguments, cases, worked examples, exercises, illustrations, and references. Coverage follows the fourth edition; earlier editions differ in chapter order. Read the source edition.