Mathematics for Computer Science PDF Download – Lehman, Leighton & Meyer (MIT OCW)

BSCS students taking a Discrete Mathematics or Discrete Structures course — or anyone who wants the mathematical foundations computer science is actually built on — can read the complete textbook “Mathematics for Computer Science” by Eric Lehman, F. Thomson Leighton, and Albert R. Meyer, free from MIT OpenCourseWare. It’s a 21-chapter, university-level text built directly from MIT’s own 6.042/6.1200J course, covering proof technique, discrete structures, counting, probability, and recurrences, all motivated by computer science applications from RSA cryptography to network flows.

This revised May 2015 edition is published directly by MIT OpenCourseWare and licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0, covering proofs and induction (Part I, Chapters 1–7), number theory and graph structures (Part II, Chapters 8–12), counting techniques (Part III, Chapters 13–15), probability (Part IV, Chapters 16–20), and recurrence relations (Part V, Chapter 21) — making it both a complete course textbook and a lasting reference for the mathematics that underlies algorithms, cryptography, and randomized computation.

Book Overview

Chapter List

Part I: Proofs

Chapter 1: What is a Proof?

Difficulty: Easy · Discrete Math for CS · Proof Foundations · Key topics: mathematical claims, direct proof, proof by contradiction, disproof by counterexample, quantifiers, common proof errors

The opening chapter sets the ground rules for the rest of the book: what counts as a mathematical claim, what a proof actually has to establish, and why a claim “seeming true” or passing a handful of checked examples never suffices. It works through direct proof and proof by contradiction on simple number-theoretic claims, and treats disproof by a single counterexample as the standard way to kill a false universal claim. Along the way it catalogs several classic invalid “proofs” that look convincing but quietly assume what they are trying to prove, training students to read proofs skeptically rather than for reassurance. The real goal is a habit of mind: state exactly what is being claimed, match the proof technique to the claim’s logical shape, and check that every step earns its place.

Key Points:

• A mathematical claim (a proposition) is either true or false, never “true in most cases” — checking many examples never proves a universal statement.
• A single counterexample is enough to disprove a claim of the form “for all x, P(x)”.
• Direct proof assumes the hypothesis and derives the conclusion through a chain of justified steps.
• Proof by contradiction assumes the claim is false and derives an impossible consequence, showing the assumption cannot hold.
• A proof is only as strong as its weakest step — “obviously” or “clearly” is not a justification on its own.
• Classic invalid proofs show why every step needs its own justification, not just a plausible-sounding narrative.

Memory Tip: Decide which proof method to reach for by the claim’s shape: an “if P then Q” claim usually wants a direct proof, a claim that’s hard to attack head-on (like irrationality) usually wants contradiction, and a “for all” claim needs only one counterexample to die.

Common Mistake: Treating a proof as a persuasive essay rather than a logical chain — students often write true statements next to each other without the logical connective that actually turns them into a proof, which is not a valid argument even when every individual statement is true.

Important Questions:

• Q1: What is the difference between proving a claim and merely providing supporting evidence for it? Supporting evidence, such as checking the claim on several numbers, can make a claim plausible but never establishes that it is true for every case; a proof is a finite chain of logically justified steps that starts from agreed facts or the hypothesis and reaches the conclusion with certainty, covering all cases at once rather than only the ones actually checked.
• Q2: Why does a single counterexample suffice to disprove a universally quantified claim, but checking many examples never proves one? A universal claim “for all x, P(x)” is false as soon as even one x fails P(x), so exhibiting that one x is a complete disproof; but no finite number of successful checks can rule out failure at some untested x, so the same asymmetry that makes one counterexample decisive also makes many confirming examples inconclusive.

Chapter 2: The Well Ordering Principle

Difficulty: Easy · Discrete Math for CS · Proof Foundations · Key topics: well ordering principle, least element, proof by smallest counterexample, division algorithm, prime factorization

This chapter introduces the Well Ordering Principle (WOP) — every nonempty set of nonnegative integers has a least element — as a proof tool distinct from, but closely related to, induction. It is used to prove that every integer greater than one has a prime factor, by considering the smallest counterexample and showing it cannot actually fail. The chapter also proves the division algorithm (that dividing one integer by a positive integer produces a unique quotient and remainder) using WOP applied to the set of possible nonnegative remainders. The unifying technique running through every example is proof by smallest counterexample: assume a counterexample exists, take the smallest one, and derive a contradiction from its minimality.

Key Points:

• The Well Ordering Principle: every nonempty set of nonnegative integers has a least (smallest) element.
• WOP applies only to sets of nonnegative integers, not to sets of all integers or of real numbers, which need not have a least element.
• “Proof by smallest counterexample” assumes a nonempty set of counterexamples exists, invokes WOP to grab the smallest one, and derives a contradiction from that minimality.
• Every integer greater than 1 has a prime factor, proved by smallest-counterexample: the smallest failing number can’t be prime itself and can’t have a smaller factor that fails either.
• The division algorithm (a = qn + r with 0 ≤ r < n) is proved using WOP on the set of nonnegative values of a − qn as q ranges over integers.

Memory Tip: Whenever a proof needs “assume not, take the smallest failure,” that is WOP in disguise — it is the natural tool for claims about the positive integers where induction feels awkward to set up directly.

Common Mistake: Applying the Well Ordering Principle to a set that is not guaranteed to consist only of nonnegative integers — WOP’s guarantee of a least element only holds under that condition, and skipping the check is a common silent error.

Important Questions:

• Q1: Why does the Well Ordering Principle require the set to consist of nonnegative integers specifically? The set of all integers has no least element since it is unbounded below, and an arbitrary set of positive real numbers, such as the open interval of numbers greater than 0, has no smallest element either; WOP’s guarantee depends specifically on both the nonnegativity and the discreteness of the integers, and without both conditions there is no reason a least element must exist.
• Q2: How does “proof by smallest counterexample” use the Well Ordering Principle to prove every integer greater than 1 has a prime factor? Assume, for contradiction, that some integer greater than 1 has no prime factor; the set of all such integers is a nonempty set of positive integers, so by WOP it has a smallest element n; n cannot be prime, since a prime is its own prime factor, so n = ab for smaller integers a, b greater than 1, and by minimality of n, a must have a prime factor, which is then also a prime factor of n — contradicting that n was assumed to have none.

Chapter 3: Logical Formulas

Difficulty: Easy · Discrete Math for CS · Proof Foundations · Key topics: propositions, AND/OR/NOT/IMPLIES, truth tables, tautologies and contradictions, logical equivalence, De Morgan’s laws, quantifiers

This chapter builds propositional logic from the ground up: propositional variables, the connectives AND, OR, NOT and IMPLIES, and truth tables as the tool for evaluating and comparing compound statements. It covers logical equivalence, key laws such as De Morgan’s laws, and the notions of tautology and contradiction. The chapter then extends to predicate logic, introducing the universal and existential quantifiers and the rules for correctly negating a quantified statement, one of the most error-prone skills in the whole course. Precise translation between English sentences and logical formulas is treated as a skill in its own right, since a misplaced quantifier changes a claim’s meaning entirely.

Key Points:

• A truth table lists every combination of truth values for a formula’s variables and the resulting truth value of the formula, defining what AND, OR, NOT and IMPLIES mean precisely.
• P IMPLIES Q is false only when P is true and Q is false; it is true whenever P is false, regardless of Q, which is a common source of confusion.
• Two formulas are logically equivalent when they have identical truth tables for every assignment of their variables.
• De Morgan’s laws state that NOT (P AND Q) is equivalent to (NOT P) OR (NOT Q), and NOT (P OR Q) is equivalent to (NOT P) AND (NOT Q).
• The negation of a universally quantified statement (“for all x, P(x)”) is an existentially quantified statement (“there exists x such that NOT P(x)”), and vice versa.
• A tautology is true under every possible assignment of truth values to its variables; a contradiction is false under every assignment.

Memory Tip: To negate a quantified statement, flip the quantifier and push NOT past it onto the inner statement — doing this one quantifier at a time from the outside in never goes wrong, even for deeply nested statements.

Common Mistake: Treating P IMPLIES Q as equivalent to its converse Q IMPLIES P — the two have different truth tables, so proving one direction of an implication never automatically proves the other, a distinction that trips up nearly every student the first time they see it.

Important Questions:

• Q1: When is the formula P IMPLIES Q false, and why does this trip up so many students? P IMPLIES Q is false in exactly one case: when P is true and Q is false; in every other case, including whenever P itself is false, the implication is true by the definition of the truth table, which feels counterintuitive to students used to everyday language, where “if P then Q” is rarely evaluated when P doesn’t happen.
• Q2: How do you correctly negate the statement “for every x, there exists a y such that P(x, y)”? Working from the outside in, negating “for every x, Q(x)” gives “there exists an x such that NOT Q(x)”; applying that once more to the inner “there exists a y such that P(x, y)” gives “for every y, NOT P(x, y)”; combining both steps, the full negation is “there exists an x such that for every y, NOT P(x, y)” — each quantifier flips in turn as the negation moves inward.

Chapter 4: Mathematical Data Types

Difficulty: Easy · Discrete Math for CS · Proof Foundations · Key topics: sets, sequences, functions, relations, Cartesian products, injections, surjections, bijections

This chapter formalizes the basic mathematical objects used throughout the rest of the book: sets and set operations, sequences and tuples, the Cartesian product of sets, and functions and relations built on top of Cartesian products. Functions are classified as injective, surjective and bijective, with each property defined precisely and illustrated with small finite examples before being used later for counting and cardinality arguments. Binary relations are introduced as sets of ordered pairs, laying groundwork for later chapters on partial orders, equivalence relations and directed graphs. The chapter is deliberately notation-heavy because the vocabulary defined here, especially “bijection” and “relation,” recurs in nearly every later chapter of the book.

Key Points:

• A set is an unordered collection of distinct elements; a sequence (or tuple) is ordered and can repeat elements.
• The Cartesian product A × B is the set of all ordered pairs (a, b); a binary relation on A and B is a subset of A × B.
• A function is injective if distinct inputs always map to distinct outputs, surjective if every element of the codomain is hit by some input, and bijective if it is both.
• A bijection between two finite sets proves they have the same number of elements — this becomes the central tool of the later Counting chapters.
• The power set of a set A is the set of all subsets of A, and has 2^|A| elements when A is finite.

Memory Tip: Keep injective/surjective/bijective straight with arrows: injective means no two arrows land on the same target, surjective means every target has an arrow landing on it, and bijective means both at once — a perfect pairing.

Common Mistake: Confusing a function’s codomain (the set it is declared to map into) with its range (the set of values it actually outputs) — a function can fail to be surjective precisely because its range is a proper subset of its codomain, and mixing these two up makes it impossible to correctly check surjectivity.

Important Questions:

• Q1: What does it mean for a function to be a bijection, and why does that matter for counting finite sets? A function is a bijection when it is both injective and surjective, which together mean it pairs up every element of the domain with exactly one element of the codomain and vice versa; when a bijection exists between two finite sets, it proves the two sets have exactly the same number of elements, which is the standard technique used later to count a complicated set by matching it with a simpler one of known size.
• Q2: How is a binary relation defined in terms of the Cartesian product, and how does this connect to functions? A binary relation on sets A and B is defined as any subset of the Cartesian product A × B, a collection of ordered pairs indicating which elements of A are related to which elements of B; a function turns out to be a special case of a relation, namely one where every element of A appears as the first coordinate of exactly one pair, which is exactly the condition that each input has one well-defined output.

Chapter 5: Induction

Difficulty: Medium · Discrete Math for CS · Induction and Infinity · Key topics: ordinary induction, base case and inductive step, strong induction, sum formulas, the horse-color fallacy

This chapter develops mathematical induction as a proof technique for claims about all natural numbers, built directly on the Well Ordering Principle from Chapter 2. It carefully separates a proof into the base case and the inductive step, and works through classic examples such as closed-form sum formulas and inequalities. Strong induction is introduced as a variant that allows the inductive step to assume the claim for all smaller values, not just the immediately preceding one, and is applied to problems like showing every amount above a threshold can be made from two denominations. The chapter closes with a deliberately broken “proof” that all horses are the same color, used to train students to spot exactly where an induction argument’s inductive step secretly fails.

Key Points:

• A proof by ordinary induction has two parts: a base case verifying the claim for the smallest value, and an inductive step showing the claim for n implies the claim for n+1.
• Strong induction’s inductive step may assume the claim holds for every value up to n, not just n itself, which is useful when a step “skips” values.
• Ordinary induction and strong induction are logically equivalent in power — anything provable with one is provable with the other — but strong induction is often more natural to write.
• The classic “all horses are the same color” fallacy fails because its inductive step silently breaks for the smallest nontrivial case, a reminder that every inductive step must actually be checked, not just asserted.
• Induction and the Well Ordering Principle are two sides of the same coin: each can be used to prove the other, and both ultimately rest on the structure of the natural numbers.

Memory Tip: Write “Base case” and “Inductive step: assume P(n), show P(n+1)” as literal headings before filling in a single line of an induction proof — stating exactly what is assumed and what must be shown catches most errors before they happen.

Common Mistake: Writing an inductive step that only checks a specific small case instead of proving the general implication “P(n) implies P(n+1)” for an arbitrary n — an inductive step must work for every value of n above the base case, or the induction never actually gets off the ground.

Important Questions:

• Q1: What is the essential difference between ordinary induction and strong induction, and why are they equally powerful despite that difference? Ordinary induction’s inductive step may only assume the claim holds for the single previous value n when proving it for n+1, while strong induction’s inductive step may assume the claim holds for every value from the base case up through n; despite looking stronger, the two are logically equivalent, because any strong-induction proof can be rewritten as an ordinary-induction proof of the stronger statement “the claim holds for all values up to n”, so nothing strong induction proves is actually out of ordinary induction’s reach.
• Q2: Where exactly does the “all horses are the same color” inductive argument break down? The argument tries to show that in any group of n horses all horses are the same color, by splitting a group of n+1 horses into two overlapping groups of n horses each and using the inductive hypothesis on each group; this step secretly requires the two overlapping groups to actually share a horse in common, which is true for n+1 ≥ 3 but fails exactly at the transition from a group of 1 horse to a group of 2 horses, since two singleton groups of 1 horse each do not overlap at all — the base case and the first inductive step are never actually connected.

Chapter 6: Recursive Data Types

Difficulty: Medium · Discrete Math for CS · Induction and Infinity · Key topics: recursive definitions, structural induction, full binary trees, well-formed formulas, strings

This chapter shows how to define infinite families of mathematical objects recursively — strings, full binary trees, and well-formed logical or arithmetic expressions are all built from a small set of base cases plus rules for combining smaller instances into larger ones. It then introduces structural induction as the natural proof technique for such recursively defined objects: prove the claim for the base cases, then show that if it holds for the pieces used to build a larger object, it holds for that larger object too. Worked examples prove structural facts such as that every full binary tree has one more leaf than internal node, and that every well-formed formula has balanced parentheses. The chapter frames structural induction as ordinary induction in disguise, applied to the size of a recursively built object rather than directly to the natural numbers.

Key Points:

• A recursive definition specifies a set by listing base cases and rules for building new elements from existing ones.
• Structural induction proves a claim about every object in a recursively defined set by proving it for the base cases and showing each construction rule preserves the claim.
• A full binary tree (every internal node has exactly two children) with n internal nodes always has exactly n+1 leaves — a standard structural induction example.
• Well-formed arithmetic and logical expressions, defined recursively from atomic terms combined by operators, always have balanced parentheses by construction.
• Structural induction is really ordinary induction applied to a recursively defined object’s size or generation number, which is why the two techniques feel similar but are stated differently.

Memory Tip: When a set is defined by starting from base cases and building up with rules, reach for structural induction automatically — prove the base cases, then check each construction rule one at a time.

Common Mistake: Forgetting to verify every base case of a recursive definition, not just the “obvious” one — a recursively defined set can have several distinct base cases, and skipping any one of them leaves a genuine gap in the structural induction proof.

Important Questions:

• Q1: How does structural induction differ from ordinary induction on the natural numbers, in terms of what is actually being inducted on? Ordinary induction proves a claim for every natural number n by inducting directly on n; structural induction instead proves a claim about every object in a recursively defined set, such as all full binary trees, by inducting on how that object was built — verifying the base cases, then showing each rule for combining smaller objects into a larger one preserves the claim; the two are really the same idea, since the size of a recursively built object plays the same role n did before.
• Q2: Why does a full binary tree with n internal nodes always have exactly n+1 leaves, proved by structural induction? The base case is a single leaf with 0 internal nodes and 1 leaf, satisfying leaves = internal nodes + 1; the inductive step considers a tree built by joining two smaller full binary trees under a new root, and if the two smaller trees have i_1 and i_2 internal nodes with i_1+1 and i_2+1 leaves respectively by the inductive hypothesis, the combined tree has i_1+i_2+1 internal nodes (including the new root) and (i_1+1)+(i_2+1) = i_1+i_2+2 leaves, exactly one more than its internal node count.

Chapter 7: Infinite Sets

Difficulty: Medium · Discrete Math for CS · Induction and Infinity · Key topics: countable and uncountable sets, cardinality, bijections between infinite sets, Cantor’s diagonal argument, Hilbert’s Hotel

This chapter extends the idea of “size” from finite sets to infinite ones by defining two sets as having the same cardinality when a bijection exists between them, producing the surprising early result that the integers and the rational numbers are all countably infinite, even though one looks like it should be larger than the other. Hilbert’s Hotel is used as an intuitive device for showing an infinite set can absorb more elements without changing its cardinality. The chapter then proves, using Cantor’s diagonal argument, that the real numbers are strictly larger than the countably infinite sets — an uncountable set — by showing no list of real numbers can ever be complete. This centerpiece result demonstrates that “infinite” is not a single size, and diagonalization becomes a reusable proof technique the book gestures toward again later.

Key Points:

• Two sets have the same cardinality when a bijection exists between them, regardless of whether one set “looks” larger by naive inclusion.
• A set is countably infinite if it can be put in bijection with the natural numbers; the integers and even the rational numbers are both countably infinite.
• Hilbert’s Hotel illustrates that a countably infinite set can absorb additional elements, even infinitely many more, while remaining the same cardinality.
• Cantor’s diagonal argument proves the real numbers are uncountable by assuming a complete list of them and constructing a new number, differing from every listed number in at least one digit, that cannot appear on the list.
• Since the real numbers are uncountable while the rationals are countable, there are strictly more real numbers than rational numbers — a first concrete example of two genuinely different sizes of infinity.

Memory Tip: Remember Cantor’s diagonal argument by its construction: build a new number one digit at a time by looking at the diagonal entry of the n-th listed number and choosing something different, guaranteeing the new number disagrees with every single entry on the list at some position.

Common Mistake: Assuming a set must be “smaller” simply because it looks like a proper subset of another set — this reasoning is valid for finite sets, but fails for infinite sets, where a proper subset can still have exactly the same cardinality as the whole set.

Important Questions:

• Q1: How does Cantor’s diagonal argument prove that the real numbers between 0 and 1 are uncountable? The argument assumes, for contradiction, that all real numbers between 0 and 1 could be listed in some sequence, each written as an infinite decimal expansion; it then constructs a new number by choosing its n-th digit to differ from the n-th digit of the n-th listed number, guaranteeing the new number differs from every number on the list in at least one decimal place; since this new number cannot appear anywhere on the supposedly complete list, the assumption that such a list exists must be false.
• Q2: Why are the rational numbers countably infinite even though there seem to be “many more” rationals than integers between any two integers? Despite the density of the rationals, an explicit bijection can still be constructed between the rationals and the natural numbers, for instance by arranging all fractions in a grid indexed by numerator and denominator and traversing that grid along its diagonals, skipping any fraction that reduces to one already counted; this traversal visits every rational number exactly once in a sequence indexed by the natural numbers, exactly the definition of countable infinity.

Part II: Structures

Chapter 8: Number Theory

Difficulty: Medium · Discrete Math for CS · Number Theory · Key topics: divisibility, greatest common divisor, Euclidean algorithm, Bezout’s identity, modular arithmetic, Fermat’s little theorem, RSA

This chapter develops the number theory needed for cryptography, starting from divisibility and the greatest common divisor, and building up to the Euclidean algorithm for computing the GCD efficiently and its extended version, which additionally produces integer coefficients satisfying Bezout’s identity. Modular arithmetic is introduced together with the notion of a multiplicative inverse modulo n, which the extended Euclidean algorithm computes directly. Fermat’s Little Theorem is proved and used as the key fact underlying modular exponentiation. The chapter’s capstone is the RSA public-key cryptosystem, built explicitly from every preceding piece: key generation from two large primes, encryption and decryption via modular exponentiation, and correctness that depends directly on Fermat’s Little Theorem.

Key Points:

• The Euclidean algorithm computes the greatest common divisor of two integers by repeated remainder-taking, in time logarithmic in the size of the inputs.
• The extended Euclidean algorithm additionally produces integers x and y satisfying Bezout’s identity ax + by = gcd(a, b), which is exactly what’s needed to compute a modular inverse.
• An integer a has a multiplicative inverse modulo n exactly when gcd(a, n) = 1, and the extended Euclidean algorithm computes that inverse directly.
• Fermat’s Little Theorem states that for a prime p and any integer a not divisible by p, a^(p−1) ≡ 1 (mod p), and underlies both fast modular exponentiation and RSA’s correctness.
• RSA key generation multiplies two large primes to form the modulus n, chooses a public exponent coprime to (p−1)(q−1), and derives the matching private exponent via the extended Euclidean algorithm.
• RSA’s security rests on the presumed difficulty of factoring the large modulus n back into its two prime factors.

Memory Tip: Keep the four number-theory tools in build order: Euclidean algorithm gives the GCD, extended Euclidean gives Bezout coefficients, Bezout coefficients give modular inverses, and modular inverses plus Fermat’s Little Theorem give RSA’s private key.

Common Mistake: Assuming every integer has a multiplicative inverse modulo n — an inverse exists only when the integer is coprime to n; this is exactly why RSA’s public exponent must be chosen coprime to (p−1)(q−1).

Important Questions:

• Q1: What does the extended Euclidean algorithm compute beyond the ordinary GCD, and why does RSA need it? Beyond computing gcd(a, b) itself, the extended Euclidean algorithm also produces integers x and y satisfying ax + by = gcd(a, b); RSA needs exactly this to compute the modular inverse of the public exponent e modulo (p−1)(q−1) during key generation, since that inverse is precisely the private decryption exponent d.
• Q2: How does Fermat’s Little Theorem underlie the correctness of RSA decryption? RSA decryption relies on the fact that raising a message to the public exponent and then to the private exponent returns the original message modulo n; the proof of this fact, worked out modulo each prime factor separately before combining, depends directly on Fermat’s Little Theorem’s guarantee that a^(p−1) ≡ 1 (mod p) for any a not divisible by p, which is what makes the exponents’ product work out to recovering the original message.

Chapter 9: Directed graphs & Partial Orders

Difficulty: Medium · Discrete Math for CS · Graphs and Networks · Key topics: directed graphs, relations, partial orders, Hasse diagrams, total orders, topological sort, equivalence relations

This chapter treats binary relations as directed graphs, formalizing properties like reflexivity, symmetry, antisymmetry and transitivity in terms of edges and paths. Equivalence relations (reflexive, symmetric, transitive) are shown to partition a set into equivalence classes, connecting back to earlier ideas about sets. Partial orders (reflexive, antisymmetric, transitive) are developed in depth, including Hasse diagrams as a visual way to represent them with redundant edges removed, and the distinction between a partial order, where some pairs may be incomparable, and a total order, where every pair is comparable. The chapter closes by connecting partial orders back to directed acyclic graphs via topological sort, showing that every finite partial order can be extended to a total order consistent with it.

Key Points:

• A relation is reflexive if every element relates to itself, symmetric if the relation goes both ways whenever it goes one way, and transitive if related pairs chain together.
• An equivalence relation partitions its underlying set into disjoint equivalence classes that cover the whole set.
• A partial order is reflexive, antisymmetric, and transitive; unlike a total order, it permits pairs of elements that are simply incomparable to each other.
• A Hasse diagram draws a partial order visually by omitting edges implied by transitivity and reflexivity, showing only the covering relations directly.
• Every finite partial order can be extended to a total order consistent with it — exactly what topological sort computes on the corresponding directed acyclic graph.

Memory Tip: Check the three defining properties of a partial order in the same order every time: reflexive, antisymmetric, transitive — missing any one of the three means it isn’t a partial order at all.

Common Mistake: Confusing antisymmetry with asymmetry — antisymmetry allows a related to a (reflexive pairs are fine) and only forbids a related to b and b related to a for distinct a and b; a relation that is symmetric, like ordinary equality, can still be antisymmetric.

Important Questions:

• Q1: Why does an equivalence relation partition its underlying set into disjoint classes? Reflexivity guarantees every element belongs to at least its own class, symmetry guarantees the “belongs to the same class” relationship is mutual, and transitivity guarantees that two elements related to a common third element are also related to each other; together these force every element into exactly one equivalence class, so the classes cannot overlap and their union covers the entire set, exactly the definition of a partition.
• Q2: What does it mean for a finite partial order to be extended to a total order, and how does topological sort compute one? Extending a partial order to a total order means finding a linear ordering of every element that agrees with the original partial order wherever it makes a comparison, while also resolving every incomparable pair one way or the other; representing the partial order as a directed acyclic graph, topological sort produces exactly such a linear ordering by outputting vertices only after all their predecessors, guaranteeing the resulting sequence respects every edge of the original partial order.

Chapter 10: Communication Networks

Difficulty: Medium · Discrete Math for CS · Graphs and Networks · Key topics: flow networks, cuts and capacity, max-flow min-cut theorem, augmenting paths, bipartite matching

This chapter models communication and transportation networks as edge-weighted directed graphs, where edge weights represent capacities, and develops the maximum flow problem: how much total flow can be pushed from a source to a sink without exceeding any edge’s capacity. It introduces cuts, partitions of the vertices separating source from sink, and proves the max-flow min-cut theorem, showing that the maximum possible flow always exactly equals the minimum capacity of any cut separating source and sink. The Ford-Fulkerson method for finding augmenting paths and increasing flow step by step is developed as the constructive half of this equivalence. The chapter closes by applying the same machinery to bipartite matching, showing that a maximum matching problem reduces directly to a maximum flow problem on an associated network.

Key Points:

• A flow network assigns a nonnegative capacity to each directed edge, and a flow assigns each edge a value respecting that capacity while conserving flow at every vertex other than the source and sink.
• A cut separates the source from the sink; the capacity of a cut is the total capacity of edges crossing from the source’s side to the sink’s side.
• The max-flow min-cut theorem: the maximum possible flow value always exactly equals the minimum capacity over all cuts separating source and sink.
• An augmenting path is a path along which more flow can still be pushed, accounting for both forward capacity and the ability to undo existing flow on reverse edges.
• The Ford-Fulkerson method repeatedly finds an augmenting path and pushes flow along it until no augmenting path remains, at which point the current flow is provably maximum.
• Bipartite matching reduces directly to maximum flow, by connecting a source to one side, a sink to the other, and giving every edge capacity 1.

Memory Tip: Remember max-flow min-cut as a two-way guarantee: no flow can ever exceed any single cut’s capacity, and the Ford-Fulkerson method’s termination proves a flow matching the minimum cut’s capacity is always achievable.

Common Mistake: Forgetting that an augmenting path can use reverse edges to undo previously pushed flow, not just unused forward capacity — without considering reverse edges, an algorithm can get stuck at a flow that is not actually maximum.

Important Questions:

• Q1: What does the max-flow min-cut theorem state, and why is it useful beyond just computing the maximum flow value? It states that the value of the maximum possible flow from source to sink is always exactly equal to the minimum capacity among all cuts separating them; beyond giving the maximum flow’s numeric value, this is useful as a certificate of optimality — once a flow is found whose value matches some cut’s capacity, that flow is guaranteed maximum without any further search, since no cut, and therefore no flow, can ever do better than the minimum cut’s capacity.
• Q2: How does the bipartite matching problem reduce to a maximum flow problem? Build a flow network with a new source connected to every vertex on one side of the bipartite graph, a new sink connected to every vertex on the other side, the original bipartite edges kept between the two sides, and every edge given capacity 1; a maximum flow in this network corresponds exactly to a maximum matching, because capacity-1 edges from the source and to the sink force each vertex to be used in at most one unit of flow, exactly the condition a matching requires.

Chapter 11: Simple Graphs

Difficulty: Medium · Discrete Math for CS · Graphs and Networks · Key topics: undirected graphs, degree, handshake lemma, trees, bipartite graphs, Euler circuits, graph coloring

This chapter develops the vocabulary of simple undirected graphs — vertices, edges, degree, paths, cycles and connectivity — and proves the handshake lemma, that the sum of all vertex degrees is always twice the number of edges, which becomes a recurring counting tool. Trees are characterized as connected graphs with no cycles, with several equivalent characterizations proved. The chapter also covers bipartite graphs and a simple test for bipartiteness based on the absence of odd-length cycles, Euler circuits and Euler’s theorem characterizing exactly which graphs have one, and an introduction to graph coloring, including the chromatic number and simple bounds on it.

Key Points:

• The handshake lemma: in any undirected graph, the sum of all vertex degrees equals exactly twice the number of edges, since each edge contributes to two vertices’ degrees.
• A tree is a connected graph with no cycles; equivalently, a connected graph on n vertices is a tree exactly when it has exactly n−1 edges.
• A graph is bipartite if and only if it contains no cycle of odd length.
• Euler’s theorem: a connected graph has an Euler circuit, a closed walk using every edge exactly once, if and only if every vertex has even degree.
• The chromatic number of a graph is the fewest colors needed so no edge connects two same-colored vertices; a graph is 2-colorable exactly when it is bipartite.

Memory Tip: Remember the handshake lemma literally: every handshake (edge) involves exactly two hands (vertex-endpoints), so summing everyone’s handshake count always double-counts the total.

Common Mistake: Confusing an Euler circuit (uses every edge exactly once) with a Hamiltonian cycle (visits every vertex exactly once) — Euler circuits are fully characterized by a simple degree condition, while no such simple test is known for Hamiltonian cycles.

Important Questions:

• Q1: How does the handshake lemma follow from how degree is defined, and what is it typically used for? Since every edge has exactly two endpoints, each edge contributes exactly 1 to the degree count of each of its two endpoints, so summing the degree of every vertex counts each edge exactly twice, giving the handshake lemma; it is typically used to prove parity facts, such as that any graph must have an even number of vertices with odd degree, since an odd sum of an odd number of odd degrees would contradict the total having to equal an even number.
• Q2: What does Euler’s theorem say about which connected graphs have an Euler circuit? Euler’s theorem states a connected graph has an Euler circuit if and only if every vertex has even degree; intuitively, every time the walk passes through a vertex it uses one edge to arrive and a different edge to leave, using up the vertex’s incident edges in pairs, so if any vertex had odd degree, the walk would eventually get stuck there with one unused edge left over and no matching edge to pair it with.

Chapter 12: Planar Graphs

Difficulty: Medium · Discrete Math for CS · Graphs and Networks · Key topics: planarity, Euler’s formula, edge bounds, Kuratowski’s theorem, the four color theorem

This chapter studies graphs that can be drawn in the plane without any edges crossing, proving Euler’s formula, V − E + F = 2, relating vertices, edges and faces of any connected planar drawing, as the central structural fact of the chapter. Euler’s formula is used to derive a simple necessary condition for planarity, an upper bound on the number of edges relative to vertex count, which is used to prove that the complete graph on five vertices and the complete bipartite graph K3,3 are both non-planar. Kuratowski’s theorem is stated, that a graph is planar if and only if it contains no subdivision of either of those two graphs, as the full characterization of planarity, without a complete proof. The chapter closes by connecting planarity to graph coloring, stating the celebrated four color theorem.

Key Points:

• Euler’s formula for a connected planar graph drawn without edge crossings: V − E + F = 2, where F counts faces including the unbounded outer face.
• Euler’s formula implies every simple planar graph with n ≥ 3 vertices has at most 3n − 6 edges.
• The complete graph on 5 vertices (K5) and the complete bipartite graph K3,3 are both non-planar, provable directly from the edge-count bound.
• Kuratowski’s theorem: a graph is planar if and only if it contains no subgraph that is a subdivision of K5 or K3,3.
• The four color theorem states every planar graph can be properly colored with at most four colors — famous both for the difficulty of its proof and for being one of the first major theorems proved with computer assistance.

Memory Tip: Remember the two “forbidden” graphs by name: K5 is too densely connected among 5 vertices, and K3,3 is too densely connected between two groups of 3, and Kuratowski’s theorem says these two shapes, or subdivisions of them, are the only obstructions to planarity.

Common Mistake: Trying to use the 3n − 6 edge bound to prove a graph containing many triangles is non-planar — the bound is a necessary condition for planarity, not a sufficient one, and passing it does not prove a graph is planar.

Important Questions:

• Q1: How does Euler’s formula lead to a proof that K5 is non-planar? K5 has 5 vertices and, since every pair is connected, exactly 5×4/2 = 10 edges; Euler’s formula implies any simple planar graph with n ≥ 3 vertices can have at most 3n − 6 edges, which for n = 5 gives an upper bound of 3(5) − 6 = 9 edges; since K5’s 10 edges exceed this bound, K5 cannot be drawn in the plane without edge crossings, proving it is non-planar.
• Q2: What does Kuratowski’s theorem add beyond the edge-count bound derived from Euler’s formula? The edge-count bound is only a necessary condition for planarity — a graph can satisfy it while still being non-planar for structural reasons the edge count alone can’t detect; Kuratowski’s theorem gives a full characterization instead, stating a graph is planar if and only if it contains no subgraph that is a subdivision of K5 or K3,3, meaning these two graphs are the only fundamental obstructions to planarity.

Part III: Counting

Chapter 13: Sums and Asymptotics

Difficulty: Medium · Discrete Math for CS · Combinatorics · Key topics: summation techniques, telescoping sums, bounding sums by integrals, asymptotic notation O/Θ/Ω

This chapter develops techniques for evaluating and bounding sums that appear throughout algorithm analysis and combinatorics, including telescoping sums, closed-form geometric and arithmetic series, and bounding a sum by comparing it to an integral of a related continuous function. It then introduces asymptotic notation — big-O, big-Omega, and big-Theta — precisely, as ways to describe a function’s growth rate up to constant factors and for large enough inputs, distinguishing an upper bound, a lower bound, and a matching tight bound respectively. Several worked examples bound the growth of sums like the harmonic series using these tools together. The throughline is that estimating a sum’s asymptotic size is often more useful, and much easier, than finding its exact closed form.

Key Points:

• A telescoping sum collapses to just its first and last terms because consecutive terms cancel when the sum is rewritten as a sequence of differences.
• Bounding a sum by an integral works because a monotonic function’s sum over an interval is squeezed between the integral computed over slightly shifted ranges.
• f(n) = O(g(n)) means f grows no faster than a constant multiple of g for all sufficiently large n; f(n) = Ω(g(n)) means f grows at least as fast; f(n) = Θ(g(n)) means both, a tight bound.
• The harmonic sum 1 + 1/2 + 1/3 + … + 1/n grows like Θ(ln n), proved by comparing it to the integral of 1/x.
• Asymptotic notation deliberately ignores constant factors and lower-order terms, which is what makes it useful for comparing growth rates without getting bogged down in exact formulas.

Memory Tip: Keep O, Ω, and Θ straight the same way you’d keep ≤, ≥, and = straight for growth rates: O is an upper bound, Ω is a lower bound, and Θ is both at once.

Common Mistake: Writing f(n) = O(g(n)) when the intended and proven claim is actually the tighter f(n) = Θ(g(n)) — big-O only asserts an upper bound and says nothing about whether f actually grows that fast.

Important Questions:

• Q1: Why does comparing a sum to an integral give a valid way to bound the harmonic sum’s growth rate? For a decreasing function like 1/x, the sum of 1/k from k=1 to n can be sandwiched between the integral of 1/x from 1 to n+1 and 1 plus the integral of 1/x from 1 to n; since the integral of 1/x evaluates to ln(n), both bounds grow like Θ(ln n), which sandwiches the harmonic sum into the same growth rate.
• Q2: What exactly is the difference between saying f(n) = O(g(n)) and f(n) = Θ(g(n))? f(n) = O(g(n)) only claims f grows no faster than a constant multiple of g for large enough n, saying nothing about a lower bound, so f could actually grow much more slowly than g and the claim would still be true; f(n) = Θ(g(n)) is the stronger, two-sided claim that f grows both no faster and no slower than a constant multiple of g, meaning g genuinely captures f’s growth rate exactly, up to constant factors.

Chapter 14: Cardinality Rules

Difficulty: Medium · Discrete Math for CS · Combinatorics · Key topics: sum rule, product rule, pigeonhole principle, permutations, combinations, binomial coefficients, inclusion-exclusion

This chapter develops the basic combinatorial counting rules used throughout the rest of the Counting part: the sum rule for counting a union of disjoint choices, the product rule for counting a sequence of independent choices, and the pigeonhole principle, which guarantees a collision whenever more items are placed into fewer containers than items. Permutations and combinations are developed from the product rule, culminating in the binomial coefficient formula for choosing an unordered subset of a given size, along with several of its standard identities. The chapter closes with the inclusion-exclusion principle for correctly counting the size of a union of possibly-overlapping sets, extending the sum rule to the non-disjoint case by systematically correcting for double-counted overlaps.

Key Points:

• The sum rule counts a union of disjoint sets of choices by adding their sizes; the product rule counts a sequence of independent choices by multiplying the number of options at each step.
• The pigeonhole principle: if more than n items are placed into n containers, at least one container holds more than one item — simple to state but a powerful existence-proof tool.
• The number of permutations of n distinct items taken k at a time is n! / (n−k)!, and the number of unordered combinations, the binomial coefficient, is that divided further by k!.
• The binomial coefficient C(n, k) counts the number of k-element subsets of an n-element set, and satisfies Pascal’s identity C(n, k) = C(n−1, k−1) + C(n−1, k).
• Inclusion-exclusion computes the size of a union of overlapping sets by adding individual set sizes, subtracting pairwise intersections, adding back triple intersections, and so on, alternating signs.

Memory Tip: Decide sum rule versus product rule by one question: are the choices “or” (pick from one group or another, disjointly) or “and” (one option from each of several independent stages)? “Or” adds, “and” multiplies.

Common Mistake: Applying the sum rule to count a union of sets that are not actually disjoint — simply adding the sizes double-counts anything in the overlap; inclusion-exclusion exists precisely to correct for this.

Important Questions:

• Q1: How does the pigeonhole principle prove that among any 13 people, at least two must share a birth month? There are only 12 possible birth months, and 13 people are each assigned to one of those 12 months; since 13 items are being placed into only 12 containers, the pigeonhole principle guarantees at least one container must receive more than one item, meaning at least two of the 13 people must share a birth month, without needing to know which specific people or which specific month.
• Q2: Why does inclusion-exclusion need to add back the triple intersection after subtracting the pairwise intersections, when counting the union of three sets? Simply adding the three individual set sizes double-counts every element in exactly two of the sets and triple-counts every element in all three; subtracting the three pairwise intersections correctly removes the double-counting for elements in exactly two sets, but it over-corrects for elements in all three, removing them three times after they were added three times, leaving them net zero instead of counted once; adding back the single triple intersection restores exactly one count for those elements.

Chapter 15: Generating Functions

Difficulty: Hard · Discrete Math for CS · Combinatorics · Key topics: generating functions, formal power series, convolution, solving counting problems algebraically

This chapter introduces generating functions, formal power series whose coefficients encode a sequence of numbers, as a unifying algebraic tool for solving counting problems that are awkward to handle with combinatorial arguments alone. It shows how multiplying two generating functions corresponds to convolving their underlying sequences, which turns problems like counting the number of ways to make change into products of simple power series. Closed-form generating functions for standard sequences, constant sequences, geometric sequences, binomial coefficients, are derived and used as building blocks for more complicated ones. The chapter closes by previewing how generating functions can also be used to solve linear recurrences algebraically, a technique developed fully in the book’s final chapter.

Key Points:

• A generating function for a sequence a_0, a_1, a_2, … is the formal power series sum of a_k x^k, treated as an algebraic object rather than a function to be evaluated numerically.
• Multiplying two generating functions corresponds exactly to convolving their sequences, which is why generating functions are so useful for counting problems built from combining independent choices.
• The generating function for the constant sequence of all 1s is 1/(1−x), a single building block that underlies many counting arguments once appropriately substituted.
• The generating function for choosing subsets (binomial coefficients) is (1+x)^n, whose coefficients directly reproduce Pascal’s triangle.
• Generating functions turn certain counting and recurrence problems into algebraic manipulation rather than combinatorial argument, trading one kind of difficulty for another that is often more mechanical.

Memory Tip: Treat the variable x in a generating function as a purely formal bookkeeping device, never something to plug a number into — its powers just mark which term of the sequence a coefficient belongs to.

Common Mistake: Trying to evaluate a generating function at a specific numeric value of x as if it were an ordinary function — generating functions are used for their coefficients, and many of the series in this chapter don’t even converge for most values of x.

Important Questions:

• Q1: Why does multiplying two generating functions correspond to convolving their underlying sequences, and why is that useful? If A(x) is the generating function for a_k and B(x) for b_k, the coefficient of x^n in the product A(x)B(x) is the sum over i of a_i times b_(n−i), exactly the convolution of the two sequences; this is useful because many counting problems naturally split into independent choices whose combined count at each total is a convolution, so multiplying the two component generating functions directly produces the generating function for the combined counting problem.
• Q2: What is the generating function for the sequence of binomial coefficients C(n, 0), C(n, 1), …, C(n, n)? The generating function is (1+x)^n; expanding this via the binomial theorem gives exactly the sum of C(n, k) x^k, so the coefficient of x^k is precisely C(n, k), the number of ways to choose a k-element subset from an n-element set; this makes combinatorial sense too, since (1+x)^n is the product of n factors of (1+x), one per element, where choosing the x term from a factor represents including that element and choosing 1 represents excluding it.

Part IV: Probability

Chapter 16: Events and Probability Spaces

Difficulty: Medium · Discrete Math for CS · Probability Theory · Key topics: sample spaces, events, probability axioms, uniform probability spaces, counting-based probability

This chapter formalizes probability starting from a sample space, the set of all possible outcomes, and events, subsets of that sample space, and states the three axioms every probability function must satisfy: nonnegativity, total probability 1, and additivity over disjoint events. It focuses heavily on uniform probability spaces, where every outcome is equally likely, in which computing an event’s probability reduces to the purely combinatorial task of counting favorable outcomes over total outcomes, connecting this chapter directly back to the Counting part of the book. Several classic worked examples illustrate translating a real-world random experiment into a precise sample space and event before any probability is computed, and the chapter also covers the probability of a union via inclusion-exclusion.

Key Points:

• A sample space is the set of all possible outcomes of a random experiment; an event is any subset of the sample space.
• The three probability axioms: every event has probability at least 0, the entire sample space has probability 1, and disjoint events’ probabilities add.
• In a uniform probability space, every outcome is equally likely, so an event’s probability is its size divided by the size of the whole sample space, turning probability into pure counting.
• The probability of the union of two events follows inclusion-exclusion: P(A ∪ B) = P(A) + P(B) − P(A ∩ B).
• Correctly defining the sample space before computing any probability is the single most important step in solving a probability problem, since an ambiguous sample space silently produces a wrong answer.

Memory Tip: Before computing any probability, write down the sample space and the event as explicit sets first — most probability mistakes trace back to an implicit or wrong sample space rather than to arithmetic errors afterward.

Common Mistake: Assuming a probability space is uniform without checking — dividing favorable by total outcomes only gives the correct probability when every outcome genuinely has the same chance.

Important Questions:

• Q1: Why does computing probability in a uniform probability space reduce entirely to counting? In a uniform probability space, every individual outcome has exactly the same probability, namely 1 divided by the total number of outcomes; since an event’s probability is the sum of the probabilities of its individual outcomes, this sum simplifies to the size of the event divided by the size of the sample space, exactly the counting techniques developed in the earlier Counting chapters.
• Q2: How does inclusion-exclusion apply to computing the probability of a union of two events? Simply adding P(A) + P(B) counts every outcome in both A and B twice, overstating the true probability of the union whenever the two events overlap; inclusion-exclusion corrects this by subtracting P(A ∩ B), the probability of the overlap, exactly once, giving P(A ∪ B) = P(A) + P(B) − P(A ∩ B); when A and B are disjoint, P(A ∩ B) = 0 and the formula reduces to the simple additive rule from the probability axioms.

Chapter 17: Conditional Probability

Difficulty: Medium · Discrete Math for CS · Probability Theory · Key topics: conditional probability, Bayes’ theorem, independence, tree diagrams, the Monty Hall problem

This chapter develops conditional probability, how an event’s probability updates once another event is known to have occurred, and derives Bayes’ theorem as a way to reverse the direction of a conditional probability. Independence is defined precisely as the case where conditioning on one event leaves another event’s probability unchanged, and is distinguished carefully from mutual exclusivity, a common point of confusion. Tree diagrams are developed as a visual tool for working through multi-stage conditional probability problems systematically. The famous Monty Hall problem is worked through in detail as the chapter’s signature example, using conditional probability to resolve the counterintuitive result that switching doors doubles the contestant’s chance of winning.

Key Points:

• Conditional probability P(A|B) is defined as P(A ∩ B) / P(B), the probability of A restricted to the world where B is already known to have happened.
• Bayes’ theorem: P(A|B) = P(B|A) · P(A) / P(B), letting a conditional probability be reversed when the forward direction is easier to compute directly.
• Two events A and B are independent exactly when P(A|B) = P(A), equivalently P(A ∩ B) = P(A) · P(B), meaning knowing B occurred gives no information about A.
• Independence and mutual exclusivity are different, often confused, concepts — two mutually exclusive events with positive probability are actually maximally dependent.
• The Monty Hall problem shows switching doors after a reveal doubles a contestant’s winning probability from 1/3 to 2/3.

Memory Tip: When a probability problem reveals information in stages, draw a tree diagram with a branch per stage labeled with its conditional probability — multiplying down a path and summing across paths handles almost any multi-stage problem correctly.

Common Mistake: Conflating “independent” with “mutually exclusive” — these are opposite kinds of relationships, since mutually exclusive events are strongly dependent, and treating them as similar is one of the most common errors in introductory probability.

Important Questions:

• Q1: Why does Bayes’ theorem let you compute P(A|B) from P(B|A), and when is this actually useful? Bayes’ theorem states P(A|B) = P(B|A) · P(A) / P(B), derived from the definition of conditional probability applied in both directions to the same joint probability P(A ∩ B); it is especially useful when the forward conditional probability P(B|A), such as the probability of a symptom given a disease, is much easier to know directly than the reverse P(A|B) actually wanted, letting that harder quantity be computed from easier-to-obtain ingredients.
• Q2: Why does switching doors in the Monty Hall problem give a 2/3 chance of winning instead of 1/2? The contestant’s initial choice has a 1/3 chance of being correct and a 2/3 chance of being wrong, and this does not change just because the host, who knows where the prize is, then opens a different door guaranteed to be empty; conditioning on the host’s reveal, the entire original 2/3 probability that the prize is elsewhere becomes concentrated on the one remaining unopened door, so switching wins with probability 2/3, while staying keeps only the original 1/3 chance.

Chapter 18: Random Variables

Difficulty: Medium · Discrete Math for CS · Probability Theory · Key topics: random variables, expectation, indicator variables, linearity of expectation, variance

This chapter introduces random variables as functions mapping outcomes of a probability space to numerical values, and expectation as the probability-weighted average value a random variable takes. Indicator random variables, taking the value 1 or 0 depending on whether an event occurs, are developed as a powerful bookkeeping trick, made especially useful by the linearity of expectation, which lets the expectation of a sum be computed as the sum of expectations even when the underlying random variables are dependent. The chapter works through classic examples using indicator variables and linearity, such as computing the expected number of fixed points in a random permutation, that would be far harder to compute directly. It closes by introducing variance as a measure of a random variable’s spread around its mean.

Key Points:

• A random variable is a function from a probability space’s outcomes to real numbers; its expectation is the probability-weighted average of the values it can take.
• An indicator random variable takes the value 1 if a specified event occurs and 0 otherwise, and its expectation always equals exactly the probability of that event.
• Linearity of expectation states E[X + Y] = E[X] + E[Y] for any two random variables, even ones that are dependent, which is what makes indicator variables so powerful.
• Expressing a complicated random variable as a sum of simple indicator variables, then applying linearity, is a standard technique for computing expectations that would be hard to reason about directly.
• Variance measures how spread out a random variable’s values typically are around its mean, defined as the expected squared deviation from the mean.

Memory Tip: When an expectation looks hard to compute directly, ask whether the quantity can be rewritten as a sum of simple 0/1 indicator variables — linearity lets you add up each indicator’s usually easy expectation without ever worrying whether the underlying events are independent.

Common Mistake: Assuming linearity of expectation requires the random variables involved to be independent — it does not; E[X + Y] = E[X] + E[Y] holds unconditionally for any random variables.

Important Questions:

• Q1: How does linearity of expectation let you compute the expected number of fixed points in a random permutation of n elements? Define an indicator random variable for each of the n positions, equal to 1 if that position is a fixed point and 0 otherwise; the total number of fixed points is exactly the sum of these n indicators, and by linearity of expectation, the expected total equals the sum of each indicator’s expectation; each position is a fixed point with probability exactly 1/n, so the expected number of fixed points is n · (1/n) = 1.
• Q2: Why does linearity of expectation hold even when the random variables being summed are dependent? Expectation is defined as a weighted sum over outcomes, and this structure is linear regardless of any relationship between the random variables involved; expanding E[X+Y] directly from the definition over the joint outcome space always simplifies algebraically to E[X] + E[Y], with no step in that derivation ever using or requiring independence, unlike many other facts about combining random variables.

Chapter 19: Deviation from the Mean

Difficulty: Hard · Discrete Math for CS · Probability Theory · Key topics: variance, standard deviation, Markov’s inequality, Chebyshev’s inequality, concentration bounds

This chapter develops tools for bounding how far a random variable is likely to stray from its expected value, starting with Markov’s inequality, which bounds the probability a nonnegative random variable exceeds some threshold using only its mean. Chebyshev’s inequality is then derived by applying Markov’s inequality to the squared deviation from the mean, giving a bound in terms of variance that applies to any random variable, not just nonnegative ones. Both inequalities are shown to be weaker but far more general than exact distribution-specific calculations, useful precisely because they require so little information. The chapter closes with worked examples showing how these concentration bounds argue that a random variable’s value is very likely close to its mean, an essential tool for analyzing randomized algorithms.

Key Points:

• Markov’s inequality: for a nonnegative random variable X and any a > 0, P(X ≥ a) ≤ E[X]/a — a bound requiring only the mean.
• Chebyshev’s inequality: for any random variable X with mean m and variance v, P(|X − m| ≥ a) ≤ v/a^2 — derived by applying Markov’s inequality to the squared deviation.
• Both inequalities are distribution-free: they hold for any random variable satisfying the stated conditions, in exchange for giving weaker bounds than an exact calculation for a known distribution.
• Chebyshev’s inequality is generally a much tighter bound than Markov’s inequality when variance is known, because it uses more information about the random variable.
• These inequalities are the standard tool for proving a random variable is concentrated near its expected value without needing to know its full probability distribution.

Memory Tip: Reach for Markov’s inequality when only a mean is known and the variable is nonnegative; reach for Chebyshev’s inequality once variance is also known, since squaring the deviation and applying Markov to that quantity is literally how Chebyshev’s inequality is derived.

Common Mistake: Applying Markov’s inequality to a random variable that can take negative values — the inequality’s proof depends on nonnegativity, and applying it to a variable that isn’t guaranteed nonnegative can produce a bound that is simply false.

Important Questions:

• Q1: How is Chebyshev’s inequality derived from Markov’s inequality? Chebyshev’s inequality is obtained by applying Markov’s inequality to the nonnegative random variable (X − m)^2, the squared deviation from the mean; since E[(X−m)^2] is exactly the definition of variance v, applying Markov’s inequality to bound P((X−m)^2 ≥ a^2) by v/a^2, and noting that (X−m)^2 ≥ a^2 is equivalent to |X−m| ≥ a, directly produces Chebyshev’s inequality.
• Q2: Why are Markov’s and Chebyshev’s inequalities useful despite typically giving much weaker bounds than an exact distribution calculation? An exact calculation of P(X ≥ a) requires knowing the random variable’s full probability distribution, which is often unknown or too complicated to work with; Markov’s inequality requires only the mean, and Chebyshev’s requires only the mean and variance, both frequently much easier to compute even when the full distribution is not tractable, making these the standard fallback tool for proving concentration near the mean.

Chapter 20: Random Walks

Difficulty: Hard · Discrete Math for CS · Probability Theory · Key topics: random walks on a line and on graphs, gambler’s ruin, hitting probability, expected hitting time

This chapter studies random walks, in which a process moves randomly between states at each time step, developed first on the simplest case of a walk on the integers before extending to walks on general graphs. The gambler’s ruin problem, a gambler with a fixed starting stake repeatedly betting until reaching either zero or a target amount, is worked through in detail, deriving the exact probability of eventual ruin as a function of the starting stake using a recurrence relation on the state. The chapter also covers expected hitting time, the expected number of steps for a walk to first reach a target state, derived for simple cases using similar recurrence techniques. Random walks generalize naturally from the integers to arbitrary graphs, connecting this chapter back to the earlier graph theory chapters.

Key Points:

• A random walk on the integers moves one step left or right at each time step according to some fixed probability, and the gambler’s ruin problem asks for the probability of eventually reaching one boundary before the other.
• The gambler’s ruin probability is derived by setting up a recurrence relating the ruin probability starting from state i to the ruin probabilities from states i−1 and i+1, then solving with known boundary conditions.
• For a fair random walk, the probability of reaching a target amount before going broke is exactly proportional to the starting stake relative to the total distance between the boundaries.
• Expected hitting time is computed using a similar recurrence-based approach, relating the expected time from each state to the expected times from its neighboring states.
• Random walks generalize naturally from a walk on the integers to a walk on an arbitrary graph, moving to a random neighbor at each step.

Memory Tip: Set up gambler’s-ruin-style problems the same way every time: write the one-step recurrence relating the probability from state i to its neighboring states, then solve using the two known boundary values at the edges of the state space.

Common Mistake: Assuming a random walk’s probability of reaching a target state is simply proportional to distance without deriving it, or applying the fair-walk proportional-distance formula to a biased random walk, where the actual formula is exponential in the bias rather than linear in distance.

Important Questions:

• Q1: How is the gambler’s ruin probability set up as a recurrence, and what are its boundary conditions? Let p_i denote the probability of eventually reaching the target amount rather than going broke, starting with a stake of i; since one step either increases or decreases the stake by 1 according to a fixed probability, p_i satisfies a recurrence relating it to p_(i+1) and p_(i−1), with boundary conditions p_0 = 0 (already broke) and p_N = 1 (already at the target N); solving this linear recurrence with those two boundary values gives the closed-form success probability as a function of the starting stake i.
• Q2: How does a random walk generalize from the integers to an arbitrary graph? On the integers, a random walk at each step moves to one of its at most two neighboring positions according to some probability; generalizing to an arbitrary graph, a random walk at each step moves from its current vertex to one of that vertex’s neighbors, typically chosen uniformly at random, rather than being restricted to left and right; hitting probability and expected hitting time generalize the same way, replacing the simple two-neighbor recurrence with a recurrence over however many neighbors each vertex actually has.

Part V: Recurrences

Chapter 21: Recurrences

Difficulty: Hard · Discrete Math for CS · Recurrences · Key topics: linear recurrences, homogeneous and particular solutions, characteristic roots, solving recurrences with generating functions

The book’s final chapter develops general techniques for solving recurrence relations, equations defining a sequence in terms of its own earlier terms, building on the informal recurrence-solving already used in the Random Walks and Generating Functions chapters. It develops the characteristic-root method for linear recurrences with constant coefficients, finding the homogeneous solution from the roots of a characteristic polynomial and combining it with a particular solution when the recurrence has an additional non-homogeneous term. The Fibonacci recurrence is worked through in full as the chapter’s central example, producing its closed-form solution in terms of the golden ratio. The chapter also revisits generating functions as an alternative, purely algebraic method for solving the same recurrences, tying together several of the book’s major tools into one closing example.

Key Points:

• A linear recurrence with constant coefficients expresses each term as a fixed linear combination of a bounded number of preceding terms, plus possibly a non-homogeneous extra term.
• The characteristic-root method solves the homogeneous version of a linear recurrence by finding the roots of its associated characteristic polynomial, which determine the general form of the solution.
• When the characteristic polynomial has repeated roots, the general solution needs extra polynomial factors of increasing degree multiplied onto the repeated root’s term, not just a simple sum of exponentials.
• The Fibonacci recurrence F_n = F_(n−1) + F_(n−2) solves, via the characteristic-root method, to a closed form involving the golden ratio phi = (1 + sqrt(5)) / 2, showing Fibonacci numbers grow exponentially despite their additive definition.
• Generating functions offer an alternative solution method for the same recurrences: translating the recurrence into an algebraic equation on the generating function and extracting the coefficient formula from a partial-fraction expansion.

Memory Tip: Solving a linear recurrence always has the same two-part shape: find the general homogeneous solution from the characteristic polynomial’s roots, then add any one particular solution matching the non-homogeneous term — homogeneous plus particular, exactly like solving a linear differential equation.

Common Mistake: Writing the general solution to a linear recurrence with a repeated characteristic root as a plain sum of exponential terms, as if the roots were distinct — a repeated root of multiplicity k requires the solution to include that root’s term multiplied by increasing powers of n, and omitting these extra factors misses degrees of freedom needed to fit the recurrence’s actual initial conditions.

Important Questions:

• Q1: How does the characteristic-root method derive the closed-form solution to the Fibonacci recurrence? Assuming a solution of the form F_n = r^n and substituting into F_n = F_(n−1) + F_(n−2) gives the characteristic equation r^2 = r + 1, whose two roots are phi = (1+sqrt(5))/2 and psi = (1−sqrt(5))/2; since the roots are distinct, the general solution is F_n = A·phi^n + B·psi^n for constants A and B determined by the initial conditions F_0 and F_1, which works out to Binet’s formula, and since |psi| < 1, its term vanishes for large n, showing Fibonacci numbers grow like phi^n.
• Q2: Why is a linear recurrence’s general solution always the sum of a homogeneous solution and a particular solution, when the recurrence has a non-homogeneous term? The homogeneous solution solves the recurrence with the non-homogeneous term set to zero, capturing every solution the recurrence’s own structure freely allows; a particular solution is any single sequence that satisfies the full recurrence including the non-homogeneous term; adding them together works because the recurrence is linear — subtracting the particular solution from any full solution leaves something satisfying the homogeneous recurrence exactly, since the non-homogeneous terms cancel, which is precisely why every solution must be expressible as homogeneous plus particular.

Read or Download Mathematics for Computer Science for Free

This book is free from its official source — MIT OpenCourseWare publishes the complete, revised textbook by Eric Lehman, F. Thomson Leighton, and Albert R. Meyer as a single PDF alongside the full 6.042/6.1200J course materials, free for anyone to read or download. There is no separate paid edition; the legitimate free way to read or download the book is the official MIT OCW course page below.

How to Study This Book

Part I, Proofs (Chapters 1–7), is the foundation the rest of the book assumes — work through direct proof, contradiction, the Well Ordering Principle, and ordinary and strong induction by hand before moving on, since every later part leans on these techniques without re-explaining them. Chapter 7, Infinite Sets, is conceptually the hardest chapter in this part and rewards a second read.

Part II, Structures (Chapters 8–12), covers number theory, graphs, partial orders, and networks. Chapter 8’s RSA cryptosystem is a genuine capstone — make sure the Euclidean algorithm and modular arithmetic feel solid first. Chapters 9–12 build on each other: directed graphs and partial orders, then flow networks, then undirected simple graphs, then planarity.

Part III, Counting (Chapters 13–15), is comparatively short but dense — Chapter 14’s cardinality rules (sum rule, product rule, pigeonhole, inclusion-exclusion) are used constantly in Part IV’s probability chapters, so treat this part as a direct prerequisite for what follows rather than a self-contained unit.

Part IV, Probability (Chapters 16–20), builds a strict dependency chain: sample spaces and events (16) before conditional probability and Bayes’ theorem (17), before random variables and expectation (18), before variance and concentration bounds (19), before random walks (20). Skipping ahead in this part rarely works.

Part V is a single chapter, Recurrences (21), but it is worth reading last deliberately — it revisits generating functions from Chapter 15 and the recurrence-solving already used informally in Chapter 20’s gambler’s ruin, tying the book’s major tools together in one closing example.

If time is short, Chapters 1, 2, 5, and 6 (the core proof techniques) plus Chapter 8 (number theory/RSA) and Chapter 14 (cardinality rules) form the minimum set most CS programs actually test on; Chapters 12, 15, and 19–20 are the most commonly trimmed when a course runs short on time.

Used In These Programs

This book is used as a Discrete Mathematics / Discrete Structures for Computer Science core text, and as general reference material, in: BSCS coursework covering discrete mathematics. Browse all Computer Science category books.

Who Should Read This

Mathematics for Computer Science is written for students taking a Discrete Mathematics or Discrete Structures course, typically in the first or second year of a computer science degree, right alongside or just before a first data structures and algorithms course. It assumes only high-school algebra and builds up proof technique, discrete structures, counting, probability, and recurrences entirely from scratch — no prior exposure to formal proof is assumed. It is not a calculus or continuous-math text and does not cover linear algebra; students who have already finished this book’s material and want to go straight into algorithm design and analysis are well prepared for a book like Problem Solving with Algorithms and Data Structures using Python.

Applicable Universities

This book is useful for students at Pakistani universities offering BSCS programs with a Discrete Mathematics or Discrete Structures core course, including Punjab University, Virtual University, COMSATS, FAST, UET, NUST, GIKI, LUMS, and other HEC-recognized institutions, and for self-learners who want a free, rigorous, university-level discrete math textbook built specifically for computer science.

FAQs

Related Books

• Problem Solving with Algorithms and Data Structures using Python (the natural next step — applies this book’s proof, induction, and graph foundations directly to algorithm design)
• Data Structures in C++ – Aikman Series (graph, tree, and recursive-structure foundations that pair directly with this book’s Structures part)
• Think Python – Allen B. Downey (a gentle companion for students who want to implement this book’s algorithms and structures in code alongside the theory)
• Think Java – Downey & Mayfield (a Java-based companion for BSCS programs that pair a discrete math course with an early Java-based programming sequence)

Mathematics for Computer Science by Lehman, Leighton, and Meyer is a free, rigorous, MIT-built discrete mathematics textbook — covering proof technique, number theory, graphs, counting, probability, and recurrences in 21 chapters, published directly by MIT OpenCourseWare. Browse more Computer Science books for the rest of your semester.

Mathematics for Computer Science, by Eric Lehman, F. Thomson Leighton, and Albert R. Meyer. Revised edition, May 18, 2015. Licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported (CC BY-NC-SA 3.0). Free to read online from its official MIT OpenCourseWare source at https://ocw.mit.edu/courses/6-042j-mathematics-for-computer-science-spring-2015/