Discrete Mathematics

A functional equation is an equation whose unknown is a function rather than a number, requiring the function to satisfy a stated relationship for all inputs in its domain — such as Cauchy's equation f(x+y) = f(x) + f(y). Unlike an algebraic equation with finitely many solutions, a functional equation can have infinitely many pathological solutions unless extra regularity (continuity, monotonicity, boundedness) is imposed; Cauchy's equation, for instance, forces f(x) = cx under continuity but admits wild, non-measurable solutions without it. Functional equations are a staple of olympiad mathematics and also model real recurrence-like relationships, such as the master theorem's f(n) = aT(n/b) + f(n) recursive structure, and functional identities like f(xy) = f(x) + f(y) that characterize the logarithm. Standard solution techniques include substituting special values (like x=0 or x=y), proving injectivity/surjectivity, and using induction to extend a formula from integers to rationals.

The master theorem gives a direct asymptotic solution for divide-and-conquer recurrences of the form T(n) = aT(n/b) + f(n), where a ≥ 1 and b > 1 are constants and f(n) is the cost of combining subproblem results. It compares f(n) against n^(log_b a), the cost implied by the recursive branching alone, and depending on which term dominates (or whether they balance), reads off Θ(n^(log_b a)), Θ(f(n)), or a Θ(f(n) log n) hybrid. It is the standard tool for analyzing algorithms like merge sort, binary search, and Strassen's matrix multiplication without solving the recurrence by hand each time. The theorem has three standard cases, plus gaps where none apply and the Akra–Bazzi method or direct recursion-tree analysis is needed instead.

A divide-and-conquer algorithm solves a problem of size n by splitting it into a smaller subproblems, each of size n/b, solving each recursively, and then combining the subproblem solutions with f(n) extra work. This translates directly into a recurrence relation T(n) = aT(n/b) + f(n), and reading off the correct (a, b, f(n)) triple from an algorithm's description is the essential first step before the Master Theorem (or any other recurrence-solving method) can be applied. Classic algorithms map onto this template directly: merge sort splits into 2 halves and does Θ(n) work merging (a=2, b=2, f(n)=n); binary search splits into 1 half of size n/2 with O(1) overhead (a=1, b=2, f(n)=1); Karatsuba multiplication splits an n-digit multiplication into 3 subproblems of half the size (a=3, b=2); and Strassen's matrix multiplication splits an n×n matrix multiply into 7 subproblems of size n/2 (a=7, b=2). Getting a, b, and f(n) right — and recognizing when a recurrence does NOT fit this template (e.g., unequal-size subproblems) — is the practical skill this concept builds toward using the Master Theorem.

A lattice is a partially ordered set (poset) in which every pair of elements has both a least upper bound (join, ∨) and a greatest lower bound (meet, ∧). Equivalently, a lattice can be defined algebraically as a set with two commutative, associative, idempotent binary operations satisfying the absorption laws. Familiar examples include the power set of a set ordered by inclusion (join = union, meet = intersection), the positive integers ordered by divisibility (join = lcm, meet = gcd), and any totally ordered set (join = max, meet = min). Lattices generalize Boolean algebras — a Boolean algebra is precisely a complemented, distributive lattice — and appear throughout logic, computer science, and abstract algebra.

A partially ordered set, or poset, is a set P equipped with a relation ≤ that is reflexive, antisymmetric, and transitive. Unlike a total order, a poset need not compare every pair of elements — divisibility on the integers is a classic example, since neither 4 ≤ 6 nor 6 ≤ 4 holds under 'divides'. Posets are typically visualized with Hasse diagrams, which draw only the covering relations (direct successor edges) and omit both loops and redundant edges implied by transitivity. Central poset concepts include maximal/minimal elements, upper/lower bounds, chains (totally ordered subsets), and antichains (subsets of pairwise incomparable elements).

The well-ordering principle states that every nonempty subset of the natural numbers has a least element. It is one of the defining properties of ℕ, is logically equivalent to the principle of mathematical induction (given the other Peano axioms), and is the engine behind proof by minimal counterexample: to show a property holds for all natural numbers, assume some counterexample exists, extract the smallest one, and derive a contradiction. The principle fails for other ordered sets such as ℤ or ℚ, which contain nonempty subsets (like ℤ itself, or the negative integers) with no least element.

Two propositional formulas are logically equivalent if they have the same truth value under every possible assignment of truth values to their variables, written p ≡ q. Equivalences let us rewrite statements into simpler or more useful forms without changing their meaning, much like algebraic identities let us rewrite expressions. A standard library of equivalences — De Morgan's laws, the distributive laws, double negation, contrapositive, and the biconditional's expansion — covers the vast majority of simplifications needed in proofs and digital logic. Verifying an equivalence can always be done mechanically by comparing truth tables, but recognizing and applying named equivalences is far faster in practice.

Propositional logic (also called statement logic, sentential calculus, or propositional calculus) is a branch of classical logic that studies propositions — statements that are either true or false — and the ways they combine into compound statements. Compound propositions are built from simpler ones using logical connectives: negation (not), conjunction (and), disjunction (or), implication (if...then), and biconditional (if and only if). Propositional logic is 'zeroth-order' in the sense that it treats propositions as indivisible units, without looking inside them at objects, predicates, or quantifiers — that refinement is the job of predicate logic.

A recurrence relation is an equation that defines each term of a sequence as a combination of previous terms. If only k previous terms appear in the equation, k is called the order of the relation. Given the first k values of the sequence (the initial conditions), every later term is determined by repeatedly applying the equation. The Fibonacci recurrence Fₙ = Fₙ₋₁ + Fₙ₋₂ and the factorial recurrence n! = n·(n-1)! are the two most famous examples: one is order 2, the other order 1.

Summation notation (sigma notation) is a compact way to write the sum of a sequence of terms without writing out every addend. The capital Greek letter Σ (sigma) stands for 'sum,' and an expression like Σᵢ₌₁ⁿ aᵢ means 'add up the terms aᵢ as the index i runs from 1 to n.' The index variable is a placeholder — it takes each integer value in the given range exactly once, and the notation says nothing about how the sum is computed, only what is being added. Sigma notation is indispensable for writing series, statistical formulas (means, variances), polynomial expansions, and algorithm running-time analyses concisely, and it comes with a small set of algebraic rules (linearity, splitting, reindexing) that let sums be manipulated symbolically before any arithmetic is done.

A recursive definition defines an object — a function, a sequence, or a set — in terms of smaller or simpler instances of itself, together with one or more base cases that stop the self-reference from going on forever. Every recursive definition has exactly two parts: base case(s) that state the value(s) directly for the smallest inputs, and a recursive (inductive) step that builds the value for a larger input out of values for smaller ones. This structure is the definitional twin of mathematical induction: a base case anchors the definition, and a recursive step lets every larger case be reduced, step by step, back down to that anchor. Recursive definitions describe factorials, Fibonacci numbers, the natural numbers themselves (via the Peano axioms), and recursively defined sets like the set of well-formed arithmetic expressions.

Boolean algebra is a branch of algebra in which the values of the variables are the truth values true and false, usually written 1 and 0, rather than numbers. It differs from elementary algebra in its operators: instead of addition, multiplication, subtraction, and division, Boolean algebra uses the logical operators conjunction (∧, 'and'), disjunction (∨, 'or'), and negation (¬, 'not'). Boolean algebra is therefore a formal way of describing logical operations, the same way elementary algebra describes numerical operations — and it is the mathematical backbone of digital logic circuits.

A Boolean function is a function that takes n Boolean inputs (each either 0/false or 1/true) and produces a single Boolean output. Because each input is one of 2 values and there are n inputs, there are 2ⁿ possible input combinations, and because the output for each combination can independently be 0 or 1, there are 2^(2ⁿ) distinct Boolean functions of n variables — 4 functions of one variable, 16 of two variables, 256 of three, and so on. A logic gate is the physical (or circuit-diagram) realization of a Boolean function: an AND gate realizes the function x∧y, an OR gate realizes x∨y, a NOT gate (inverter) realizes ¬x. Every Boolean function, no matter how complicated, can be built by wiring together a small number of these primitive gates, which is exactly how digital computers implement arithmetic and logic in hardware.

The floor function ⌊x⌋ rounds a real number x down to the nearest integer, and the ceiling function ⌈x⌉ rounds it up to the nearest integer. Both take a continuous input and return a discrete integer output, which makes them the natural bridge between real-number arithmetic and integer-indexed structures like arrays, pages, and clock arithmetic. Unlike ordinary rounding (which rounds to the nearest integer in either direction), floor always moves toward negative infinity and ceiling always moves toward positive infinity, so for a non-integer x the two differ by exactly 1: ⌈x⌉ = ⌊x⌋ + 1. These functions appear constantly in discrete mathematics — counting multiples, computing array indices, expressing the number of bits needed to represent a number, and defining the mod operation itself.

A number representation (positional numeral system) writes an integer as a sequence of digits, where each digit's contribution to the total value depends on both the digit and its position — its place value is a power of the system's base (radix). The familiar decimal system uses base 10 with digits 0–9, but any integer b ≥ 2 works as a base: binary (base 2, digits 0–1) is the native language of digital circuits, since a bit's two states map directly onto 'off' and 'on'; hexadecimal (base 16, digits 0–9 then A–F for 10–15) is popular in computing because each hex digit corresponds to exactly 4 bits, making it a compact, human-readable stand-in for binary. The same integer has a different digit string in each base, but converting between bases is mechanical: repeated division by the target base (to convert to that base) or summing digit × base^position (to convert from that base to decimal).

Algorithm analysis is the study of how the resources an algorithm consumes — almost always running time, sometimes memory — scale as the input size n grows, independent of any particular machine or programming language. Rather than timing an implementation with a stopwatch, analysis counts the number of elementary operations (comparisons, arithmetic operations, array accesses) as a function of n, then classifies that function by its growth rate using big-O notation, which discards constant factors and lower-order terms because those become irrelevant for large n. This lets two very different algorithms for the same problem be compared abstractly: an O(n²) sort and an O(n log n) sort will eventually diverge no matter how the constants compare, because n log n grows strictly slower than n² once n is large enough. Analyzing algorithms that call themselves recursively (like merge sort or binary search) typically produces a recurrence relation for the running time, which is then solved — often via the Master Theorem — to obtain a closed-form growth rate.

The Boolean satisfiability problem (SAT) asks, given a propositional logic formula built from variables, ∧, ∨, and ¬, whether there is some assignment of true/false to the variables that makes the whole formula evaluate to true. A formula that has such an assignment is satisfiable; one that has none (it is false under every assignment) is unsatisfiable, i.e. a contradiction. SAT is the canonical NP-complete problem: the Cook–Levin theorem (1971) proved that SAT is NP-complete, meaning every problem in NP can be reduced to it in polynomial time, and no known algorithm solves SAT in the worst case faster than roughly checking all 2ⁿ assignments (though practical SAT solvers using techniques like DPLL and conflict-driven clause learning routinely solve huge industrial instances). SAT is almost always studied in conjunctive normal form (CNF): a conjunction (AND) of clauses, each clause a disjunction (OR) of literals (variables or their negations), because any propositional formula can be converted to an equisatisfiable CNF formula.

A graph G = (V, E) can be stored in a computer in several standard ways, and the choice of representation drives the running time of every graph algorithm built on top of it. The two workhorse representations are the adjacency matrix, an |V|×|V| grid of 0s and 1s (or edge weights) where entry (i, j) records whether an edge connects vertex i to vertex j, and the adjacency list, where each vertex keeps a list of only its neighbors. A graph, viewed set-theoretically, is exactly a binary relation on V (the edge relation), so adjacency matrices are literally the relation matrices of that relation, and the two representations trade off differently depending on how dense or sparse the edge set is: adjacency matrices give O(1) edge lookups but cost Θ(|V|²) space regardless of how many edges exist, while adjacency lists cost Θ(|V| + |E|) space and are far more efficient for the sparse graphs (|E| ≪ |V|²) that dominate real-world applications like road networks and social graphs.

Modular exponentiation computes bᵉ mod m — a base raised to an exponent, reduced modulo m — without ever forming the (potentially astronomically large) full number bᵉ. Naively multiplying b by itself e times and reducing mod m at the end would require storing a number with roughly e·log(b) digits, which is completely inferactable for the exponents used in real cryptography (hundreds or thousands of bits, as in RSA). The key trick, exponentiation by squaring (also called fast or binary exponentiation), reduces the number of multiplications from O(e) to O(log e) by writing e in binary and repeatedly squaring the base while reducing modulo m at every step, so intermediate values never grow larger than m². This single technique — squaring plus modular reduction at every step — is what makes RSA encryption, Diffie–Hellman key exchange, and the Miller–Rabin primality test computationally feasible: they all require raising numbers to exponents with hundreds of digits, modulo similarly huge numbers.

A combinatorial proof establishes an identity between two counting expressions by showing that both sides count the exact same finite set of objects — either by exhibiting a direct bijection between two sets, or by computing the size of one set in two different ways (double counting). This style of proof is often more illuminating than an algebraic derivation because it reveals *why* an identity is true rather than just confirming that symbol manipulation happens to work out. Pascal's rule C(n,k) = C(n-1,k-1) + C(n-1,k) is the classic first example: both sides count size-k subsets of an n-element set, split by whether a fixed element is included or excluded. Vandermonde's identity, the hockey-stick identity, and the identity that the sum of all binomial coefficients in a row of Pascal's triangle equals 2ⁿ are all provable the same way — find a set two counting arguments both describe, and the algebra follows for free.