Proof by Cases - Discrete Math

SECTION 1

Historical Context & Motivation

The strategy of splitting a problem into distinct scenarios and reasoning about each one independently is among the oldest logical maneuvers in mathematics. Ancient Greek geometers routinely divided geometric constructions into separate configurations—positive angle versus negative, acute versus obtuse—long before modern proof methodology was codified. Proof by cases (sometimes called proof by exhaustion when the cases are finite and enumerated) formalises this intuition: if a universe of discourse can be partitioned into subcases that together cover every possibility, and the desired conclusion holds in each subcase, then it holds universally.

Historically, this technique has appeared in number-theoretic arguments (Euclid's classification of primes and composites), in algebra (analysis of polynomial roots by sign), and in modern computer science (verifying program correctness over different input classes). Its logical foundation rests on the tautology of constructive dilemma: if P₁ ∨ P₂ ∨ … ∨ Pₙ is true and each Pᵢ → Q, then Q follows. Below is a brief timeline showing how case analysis matured from informal reasoning into a rigorous proof strategy.

~300 BCE • Euclid's Elements

Euclid employs case distinctions throughout the Elements, dividing geometric propositions by whether a point lies inside, on, or outside a circle—an early exhaustive case analysis.

1637 • Fermat's Descent Arguments

Pierre de Fermat uses case splits based on residue classes modulo small primes to prove results in number theory, notably his method of infinite descent which relies on partitioning integers by divisibility.

1879 • Frege's Begriffsschrift

Gottlob Frege formalises propositional logic, giving proof by cases an explicit logical foundation via the disjunction elimination rule in a formal deductive system.

1976 • Four Color Theorem

Appel and Haken prove the Four Color Theorem by reducing it to 1,936 cases verified by computer—the most famous large-scale proof by exhaustion in mathematics.

2005 • Formal Verification Era

Proof assistants like Coq and Isabelle/HOL mechanise case analysis, enabling machine-checked proofs that systematically enumerate and verify thousands of subcases in software and hardware verification.

The central question proof by cases answers is deceptively simple: when a direct or contrapositive argument is not forthcoming, can we still prove a statement by ensuring every possible scenario leads to the same conclusion? The answer, grounded in the logical completeness of an exhaustive partition, is a resounding yes—provided the partition truly covers every case.

SECTION 2

Core Principles & Definitions

A proof by cases succeeds when three conditions are met: the cases must be exhaustive (they cover every element in the domain), each case must independently imply the conclusion, and the logic connecting them must be valid. The cases need not be mutually exclusive—overlap is harmless—but missing even one scenario invalidates the proof entirely. The following concept cards formalise these ideas.

Exhaustive Partition

The disjunction P₁ ∨ P₂ ∨ … ∨ Pₙ must be a tautology relative to the domain. Every element, value, or scenario must fall into at least one case. For example, partitioning integers as even or odd is exhaustive; partitioning by 'divisible by 3' alone is not.

Case Implication

Within each case Pᵢ, you must prove Pᵢ → Q using any valid proof technique—direct proof, contradiction, contrapositive, or even nested case analysis. The key is that Q is the same conclusion in every case.

Disjunction Elimination

The logical backbone is the rule: from (P₁ ∨ P₂ ∨ … ∨ Pₙ), (P₁ → Q), (P₂ → Q), …, (Pₙ → Q), conclude Q. This is valid in classical, intuitionistic, and constructive logics alike.

Without Loss of Generality (WLOG)

When cases are symmetric, we may prove only one and invoke symmetry for the rest. The phrase 'without loss of generality' signals that a symmetry argument reduces the number of cases. This must always be justified, not merely asserted.

✦

KEY TAKEAWAY

Think of proof by cases like a security team clearing a building: they divide the structure into zones, search each zone independently, and once every zone is confirmed safe, the entire building is declared secure. If a single zone is left unchecked, the conclusion fails—the partition must be exhaustive. Similarly, if even one zone reveals a threat (a case where the conclusion doesn't hold), the universal claim collapses.

SECTION 3

Visual Explanation

The diagram below illustrates the logical architecture of a proof by cases. The domain of discourse (represented by the large outer rectangle) is partitioned into subcases. Each subcase independently implies the conclusion Q. The disjunction elimination rule then combines these partial results into the final conclusion.

Each colored box represents an individual case (P₁, P₂, …, Pₖ). The dashed amber box confirms that the cases are exhaustive. Arrows converge at the green conclusion box, which is reached via disjunction elimination.

Notice that the arrows from each case box to the exhaustive-check layer are independent: the proof within Case 1 need not reference the argument in Case 2. This modularity is one of the technique's great strengths. Each subproof can employ a different method—direct reasoning in one case, contradiction in another—yet the overall structure remains unified by the disjunction elimination step at the bottom.

SECTION 4

Mathematical Framework

The logical validity of proof by cases rests on a well-known tautology in propositional logic. We formalise the technique below, starting with the two-case version and generalising to an arbitrary finite number of cases.

TWO-CASE VERSION

[(P₁ ∨ P₂) ∧ (P₁ → Q) ∧ (P₂ → Q)] → Q

P₁, P₂ are the two cases (their disjunction must be a tautology over the domain). Q is the conclusion to be established. This is the constructive dilemma in classical logic.

GENERAL k-CASE VERSION

[(P₁ ∨ P₂ ∨ … ∨ Pₖ) ∧ ⋀ᵢ(Pᵢ → Q)] → Q

Here ⋀ᵢ denotes the conjunction over all i from 1 to k. The disjunction P₁ ∨ … ∨ Pₖ must evaluate to true for every element under consideration—this is the exhaustiveness requirement.

In natural deduction systems, the corresponding inference rule is typically called ∨-elimination (or disjunction elimination). Given a proof of P₁ ∨ P₂, together with a subproof deriving Q from the assumption P₁ and a subproof deriving Q from the assumption P₂, one may discharge both assumptions and conclude Q. The rule extends straightforwardly to any finite disjunction by iterated application.

PROOF TEMPLATE (SCHEMATIC)

Goal: ∀x ∈ D, R(x). Split: D = D₁ ∪ D₂ ∪ … ∪ Dₖ. Prove: x ∈ Dᵢ ⟹ R(x) for each i.

D is the domain, Dᵢ are the subsets forming the partition (or cover), and R(x) is the property to be proved. The union D₁ ∪ … ∪ Dₖ = D ensures exhaustiveness.

⚠

Overlap is Harmless

The cases need not be mutually exclusive. If some element x belongs to both D₁ and D₂, the conclusion R(x) is proved by Case 1 alone (or by Case 2 alone)—no contradiction arises. However, gaps are fatal: if some x belongs to no Dᵢ, the proof fails.

SECTION 5

Common Case-Splitting Strategies

Choosing the right partition is an art as much as a science. The most effective case splits exploit the algebraic or structural properties of the objects involved, reducing a complex universal statement to manageable subclaims. Below is a classification of the most frequently encountered case-splitting strategies in discrete mathematics and adjacent fields.

Five canonical strategies for case-splitting. Parity and modular residues are especially common in number theory, while structural splits dominate graph theory and algebra.

When selecting a splitting strategy, the guiding heuristic is to choose cases that simplify the algebraic or logical structure of the proposition. For instance, splitting an integer n by parity lets you write n = 2k or n = 2k + 1, converting an arbitrary integer into a linear function of k—an enormous simplification when the conclusion involves n². Similarly, modular residue classes modulo 3 are ideal when the conclusion involves n³ or divisibility by 3, because cubing a residue class produces predictable remainders.

💡

When to Use Proof by Cases

Proof by cases is most useful when: (1) a hypothesis is explicitly a disjunction (e.g., 'x is rational or x is irrational'); (2) an absolute value or piecewise-defined function creates natural branches; (3) a direct proof for the general case is obstructed but the specialised subcases yield to direct argument; or (4) a classification theorem partitions objects into types.

SECTION 6

Worked Example

We now apply proof by cases to a classic number-theoretic statement. The result is elementary but perfectly illustrates the technique's mechanics, including the choice of cases, the independent subproofs, and the final assembly.

Theorem: For every integer n, n² + n is even.

Proof by Cases — n² + n Is Even

1
Step 1 — Identify the Goal and Domain

We wish to prove that for every integer n, the expression n² + n is even. Equivalently, we must show that 2 divides n² + n. Observe that n² + n = n(n + 1), but we shall proceed via case analysis on the parity of n to demonstrate the technique explicitly.
2
Step 2 — Choose an Exhaustive Partition

Every integer is either even or odd. This gives us two cases:

Case 1: n is even | Case 2: n is odd
3
Step 3 — Prove Case 1 (n is even)

Assume n is even, so n = 2k for some integer k. Then n² + n = (2k)² + 2k = 4k² + 2k = 2(2k² + k). Since 2k² + k is an integer, n² + n is divisible by 2.

n² + n = 2(2k² + k) is even. ✓
4
Step 4 — Prove Case 2 (n is odd)

Assume n is odd, so n = 2k + 1 for some integer k. Then n² + n = (2k + 1)² + (2k + 1) = 4k² + 4k + 1 + 2k + 1 = 4k² + 6k + 2 = 2(2k² + 3k + 1). Since 2k² + 3k + 1 is an integer, n² + n is divisible by 2.

n² + n = 2(2k² + 3k + 1) is even. ✓
5
Step 5 — Conclude by Disjunction Elimination

Since every integer is either even or odd (the cases are exhaustive), and in both cases n² + n is even, we conclude that n² + n is even for all integers n.

∴ For every integer n, n² + n is even. □

📝

Observation

A slicker proof factors n² + n = n(n + 1), noting that consecutive integers always include one even factor. Proof by cases achieves the same result more mechanically. In practice, the elegance of the factorisation is preferable, but the case-analysis approach generalises to situations where no clean factorisation exists.

SECTION 7

Strengths, Limitations & Comparisons

Proof by cases is a versatile but not universally optimal strategy. Understanding when it excels and when other techniques are superior is crucial for effective mathematical writing. The table below contrasts proof by cases with other major proof methods.

Criterion	Proof by Cases	Direct Proof	Proof by Contradiction
When to use	Domain splits naturally into subcases; hypothesis is a disjunction; piecewise-defined functions	Hypothesis leads naturally to conclusion via a chain of implications	Negation of conclusion yields useful information; existence/uniqueness results
Strengths	Modular; each case is simpler than the whole; tolerates asymmetric structures	Most transparent and intuitive; preferred when available	Powerful for impossibility results; works when constructive path is unclear
Limitations	Can produce lengthy proofs; must verify exhaustiveness; less insightful if many cases	Not always available; requires a clear implication chain	Non-constructive; may feel indirect; harder to extract computational content
Typical # of steps	Proportional to k (number of cases) × subproof length	Usually shortest when applicable	Variable; may involve deep auxiliary reasoning
Common pitfall	Non-exhaustive partition (missing a case)	Unjustified leap in the implication chain	Assuming what you want to prove (circular reasoning)

Comparison of proof by cases with direct proof and proof by contradiction

✦

KEY TAKEAWAY

Proof by cases is like a doctor running a differential diagnosis: when a single test cannot pinpoint the answer, you enumerate the possible conditions, rule each one in or out independently, and the combination of all sub-analyses yields the definitive conclusion. The method is reliable but sometimes expensive—if a single elegant test (direct proof) is available, it is usually preferable. But when the domain resists a unified approach, case analysis is the mathematically guaranteed fallback.

SECTION 8

Connection to Advanced Theory

Proof by cases, though elementary in concept, connects deeply to several areas of advanced mathematics and theoretical computer science. The table below maps its relationship to more sophisticated proof paradigms.

Proof by Cases (This Lesson)	Advanced Extension
Finitely many cases, each proved by hand	Computer-assisted proof by exhaustion: thousands of cases verified algorithmically (e.g., Four Color Theorem, Kepler Conjecture)
Case split on integers (parity, mod m)	Structural induction: case analysis on recursive data structures (trees, lists, formulas) combined with an inductive hypothesis
Disjunction elimination in propositional logic	Pattern matching in type theory: in Curry–Howard correspondence, case analysis on a sum type A + B mirrors disjunction elimination
WLOG (symmetry reduction)	Group actions and Burnside's lemma: symmetry groups formally reduce the number of distinct cases in combinatorial enumeration
Exhaustive verification over a finite domain	Model checking: automated exhaustive state-space exploration in hardware/software verification

From proof by cases to advanced techniques

In courses on automata theory and programming languages, you will encounter structural induction as the natural marriage of case analysis with mathematical induction: the base cases of an inductive proof are themselves a case split, and the inductive step often requires further sub-case analysis on the form of a recursive structure. Mastery of proof by cases is therefore foundational—it is the atomic operation from which more complex proof architectures are assembled.

ℹ

Looking Ahead

If you continue to courses in formal methods or type theory, you will see proof by cases reappear as case expressions and match statements in functional programming languages (Haskell, OCaml, Coq). The compiler's exhaustiveness checker is precisely the formal analogue of verifying that your cases cover the entire domain.

SECTION 9

Practice Problems

The following five problems progress from conceptual understanding to critical analysis. Attempt each problem before reading the answer; active struggle is the primary mechanism by which proof technique becomes internalised.

Question 1: CONCEPTUAL

A student claims to prove that every real number x satisfies |x| ≥ 0 by considering two cases: x > 0 and x < 0. Is this proof by cases valid? If not, identify the flaw.

Show answer

The proof is invalid because the cases are not exhaustive: the student has omitted the case x = 0. Since every real number is positive, negative, or zero (by the trichotomy law), a correct proof by cases requires three subcases. In the missing case, |0| = 0 ≥ 0, which holds trivially. The logical flaw is a non-exhaustive partition: the disjunction (x > 0) ∨ (x < 0) is not a tautology over ℝ.

Question 2: BASIC CALCULATION

Prove by cases that for every integer n, 3 divides n³ − n.

Show answer

Partition the integers by residue modulo 3. Case 1: n ≡ 0 (mod 3), so n = 3k, giving n³ − n = 27k³ − 3k = 3(9k³ − k), divisible by 3. Case 2: n ≡ 1 (mod 3), so n = 3k + 1, giving n³ − n = (3k+1)³ − (3k+1) = 27k³ + 27k² + 9k + 1 − 3k − 1 = 27k³ + 27k² + 6k = 3(9k³ + 9k² + 2k), divisible by 3. Case 3: n ≡ 2 (mod 3), so n = 3k + 2, giving n³ − n = (3k+2)³ − (3k+2) = 27k³ + 54k² + 36k + 8 − 3k − 2 = 27k³ + 54k² + 33k + 6 = 3(9k³ + 18k² + 11k + 2), divisible by 3. Since every integer falls into exactly one residue class mod 3, the proof is complete.

Question 3: INTERMEDIATE

Prove: for all integers m and n, if mn is even, then m is even or n is even. (Hint: use proof by cases on the parity of m.)

Show answer

Assume mn is even. We consider two cases based on the parity of m. Case 1: m is even. Then 'm is even or n is even' is immediately true (the first disjunct holds). Case 2: m is odd, so m = 2k + 1 for some integer k. Since mn is even, mn = 2j for some integer j. Then (2k+1)n = 2j, so n = 2j/(2k+1). However, since 2k+1 divides 2j and gcd(2k+1, 2) = 1 (as 2k+1 is odd), we conclude 2k+1 divides j. Write j = (2k+1)q, giving n = 2q, which is even. Hence 'm is even or n is even' holds. Since every integer is either even or odd, the two cases are exhaustive, and the proof is complete. Note that the contrapositive ('if m and n are both odd, then mn is odd') would also work cleanly, but the case-based approach demonstrates the technique.

Question 4: APPLIED

A program receives an integer input n and must compute f(n) = n² − 1. A programmer claims the output is always non-negative for |n| ≥ 1. Prove this claim using proof by cases, splitting on the sign of n.

Show answer

We must show that if |n| ≥ 1 (i.e., n ≥ 1 or n ≤ −1), then n² − 1 ≥ 0. Case 1: n ≥ 1. Then n² ≥ 1² = 1, so n² − 1 ≥ 0. Case 2: n ≤ −1. Then n² = (−|n|)² = |n|² ≥ 1² = 1, so n² − 1 ≥ 0. The partition |n| ≥ 1 is equivalent to n ≥ 1 ∨ n ≤ −1, which exhausts all integers with |n| ≥ 1 (the case n = 0 falls outside the stated precondition). In both cases, n² − 1 ≥ 0, so the programmer's claim is correct. This mirrors how software verification partitions input domains to confirm correctness across all branches.

Question 5: CRITICAL THINKING

Prove or disprove: for every integer n, the expression n⁴ − n² is divisible by 12. If it is true, construct a proof by cases using an appropriate modular partition. If false, provide a counterexample and determine the largest integer that always divides n⁴ − n².

Show answer

The statement is false. Consider n = 1: n⁴ − n² = 1 − 1 = 0, which is divisible by 12. But n = 2: n⁴ − n² = 16 − 4 = 12, divisible by 12. And n = 3: 81 − 9 = 72, divisible by 12. One might suspect it is true, but n = 5: 625 − 25 = 600, also divisible by 12. In fact, n⁴ − n² = n²(n² − 1) = n²(n−1)(n+1). Among three consecutive integers (n−1, n, n+1), one is divisible by 3, and at least one is even. Moreover, n² contributes an additional factor of 2 if n is even (giving 4 from n²), or (n−1)(n+1) are both even if n is odd, giving another 4. A careful case analysis modulo 12 (or modulo 4 and modulo 3 separately, then combining via CRT) reveals that 12 always divides n⁴ − n². In fact the claim is true for all integers. The proof by cases on n mod 12 (or more efficiently on n mod 4 combined with n mod 3) confirms universal divisibility by 12. The critical insight is to factor and track prime-power divisibility across the cases.

SUMMARY

Lesson Summary

Summary

Proof by cases is a proof technique in which the domain of discourse is partitioned into an exhaustive set of subcases, and the desired conclusion is established independently within each subcase. Its logical foundation is the disjunction elimination rule: given P₁ ∨ P₂ ∨ … ∨ Pₖ and proofs that each Pᵢ → Q, one concludes Q. The cases may overlap without harm, but non-exhaustive partitions invalidate the proof. Common splitting strategies include parity, modular residues, sign/ordering, and structural type analysis.

While proof by cases can produce longer proofs than a direct argument, it offers modularity (each subcase is self-contained), flexibility (different proof techniques may be used in different cases), and is the foundational mechanism behind structural induction, computer-assisted proofs by exhaustion, and pattern matching in type theory. Mastering this technique equips you with a reliable strategy for any proposition that resists a single unified argument.