Discrete Math
Every lesson explains the concept, works through examples, and gives you practice problems with full solutions. Work through them in order, or jump to the topic you need.
32 lessons
- Counting Divisors: τ(n), σ(n) and Perfect NumbersCount and add the divisors of n from its prime factorization: τ(n) multiplies (exponent + 1), σ(n) multiplies geometric sums. Find perfect numbers like 6, 28 and 496.
- Counting Lattice Paths on a GridCount shortest grid paths with right and up steps: there are C(m + n, m) paths to (m, n). Multiply to count paths through a point; subtract to avoid it.
- Propositional Logic and Truth TablesCombine statements with and, or, not and if–then, build truth tables, and spot equivalent forms: the contrapositive, De Morgan's laws and why the converse differs.
- Predicate Logic: Quantifiers ∀ and ∃ and Their NegationsWrite statements with 'for all' and 'there exists', negate them by flipping the quantifier, and see why the order of nested quantifiers changes the meaning.
- Sets, Set Operations and Inclusion–ExclusionWork with sets: union, intersection, difference and complement, subsets and power sets, and count overlapping groups with the inclusion–exclusion principle.
- Proof Techniques: Direct, Contrapositive and ContradictionLearn the three standard ways to prove a statement: a direct proof from definitions, a proof of the contrapositive, and proof by contradiction, with classic examples.
- Combinatorial Proofs and Binomial Coefficient IdentitiesProve identities like Pascal's rule, the row sum 2ⁿ and Vandermonde's identity by counting one set in two different ways, with no algebra needed.
- Modular Arithmetic and CongruencesArithmetic with remainders: what a ≡ b (mod n) means, why you can reduce before adding or multiplying, fast powers, last digits, days of the week and modular inverses.
- Number Bases: Binary, Hexadecimal and Base bRead numbers in base 2, 3, 5 and 16 using place values that are powers of the base, convert from base 10 by repeated division, and turn binary into hex.
- Boolean Algebra and Logic GatesCompute with 0 and 1 using AND, OR and NOT, simplify expressions with the Boolean laws, build a formula from a truth table, and design circuits like a half adder.
- Stars and Bars: Combinations with RepetitionCount ways to share identical objects among groups with stars and bars: C(n + k − 1, k − 1) ways with empty groups allowed, C(n − 1, k − 1) when each gets one.
- Inclusion–Exclusion in General: Derangements and Onto FunctionsCount the objects with none of several properties by alternately subtracting and adding overlaps. Count derangements, onto functions and numbers free of given divisors.
- Strong Induction and the Well-Ordering PrincipleProve statements where each case depends on several earlier ones: assume all cases up to k, prove case k + 1, and supply enough base cases to start the chain.
- The Euclidean Algorithm and Bézout's IdentityFind the greatest common divisor of two large numbers by repeated division, write it as a combination ax + by with the extended algorithm, and compute modular inverses.
- Euler's Totient Function φ(n)Count the numbers up to n that share no factor with n. Compute φ(n) from the prime factorization with φ(n) = n(1 − 1/p₁)(1 − 1/p₂)⋯, and use φ(mn) = φ(m)φ(n).
- The Chinese Remainder TheoremSolve systems like x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7): with pairwise coprime moduli there is exactly one solution modulo their product.
- Linear Diophantine Equations: Whole-Number Solutions of ax + by = cDecide whether ax + by = c has integer solutions with the gcd test, find one with the extended Euclidean algorithm, write them all, and count the nonnegative ones.
- The Pigeonhole PrincipleIf more objects than boxes are placed in boxes, some box holds two. Use the pigeonhole principle and its general form ⌈n/k⌉ to prove that something must happen.
- Graphs, Degrees and the Handshaking LemmaGraph theory basics: vertices, edges, degree, paths and connectedness. Prove that degrees add to twice the number of edges, and count edges in complete graphs and trees.
- Euler and Hamilton Paths: The Bridges of KönigsbergWhen can you trace every edge of a graph once? Euler's theorem answers by counting odd-degree vertices. Contrast it with Hamilton paths, which visit every vertex once.
- Recurrence Relations and How to Solve ThemDefine sequences by recurrence, like Fibonacci and the Tower of Hanoi, and solve linear recurrences with a characteristic equation to get a closed formula.
- Catalan Numbers: Paths, Parentheses and TriangulationsThe Catalan numbers 1, 1, 2, 5, 14, 42, … count balanced parentheses, lattice paths that stay below the diagonal and polygon triangulations. Use Cₙ = C(2n, n)/(n + 1).
- Generating Functions: Counting with Power SeriesEncode a sequence as the coefficients of a power series, multiply series to count combinations, and use generating functions to solve recurrences like Fibonacci.
- One-to-One, Onto and Bijective FunctionsClassify functions between sets as one-to-one, onto or both, count the functions between finite sets, and see why only bijections have inverses.
- Countable and Uncountable Sets: Sizes of InfinityCompare infinite sets with bijections: the integers and the rationals can be listed like the natural numbers, but Cantor's diagonal argument shows the reals cannot.
- Relations, Equivalence Relations and Partial OrdersTest a relation for the reflexive, symmetric, antisymmetric and transitive properties, find equivalence classes, and see how equivalence relations split a set into parts.
- Trees, Spanning Trees and Kruskal's AlgorithmLearn what makes a graph a tree, why a tree on n vertices has n − 1 edges, and find a minimum spanning tree of a weighted network with Kruskal's algorithm.
- Planar Graphs and Euler's Formula V − E + F = 2Draw graphs without crossing edges, count faces, and prove Euler's formula V − E + F = 2. Use E ≤ 3V − 6 to show that K₅ and K₃,₃ are not planar.
- Graph Coloring and the Chromatic NumberColor the vertices of a graph so that neighbors differ, find the chromatic number, test for two-colorability with odd cycles, and schedule exams with no conflicts.
- Shortest Paths and Dijkstra's AlgorithmFind the shortest route through a weighted network with Dijkstra's algorithm: keep tentative distances, finalize the closest vertex, and update its neighbors.
- Fermat's Little Theorem and Euler's TheoremReduce huge powers mod n: a^(p−1) ≡ 1 (mod p) for a prime p, and a^φ(n) ≡ 1 (mod n) when gcd(a, n) = 1. Find remainders, last digits and modular inverses.
- RSA Encryption: Public Keys from Modular ArithmeticBuild RSA keys from two primes, encrypt with c = mᵉ mod n, decrypt with m = cᵈ mod n, and see why it works (Euler's theorem) and why it is secure (factoring is hard).