Proof by Cases

Proof by cases is not a niche technique confined to introductory courses — it is load-bearing machinery across mathematics and its applications.

• Number theory: Countless divisibility and modular-arithmetic proofs (as in Example 1) split on residues mod $k$; Fermat's Little Theorem, quadratic reciprocity proofs, and classical Diophantine arguments all lean on exhaustive residue-class casework.
• Real analysis and inequalities: Absolute value arguments (Example 2), the triangle inequality, and epsilon-delta proofs frequently split on the sign or relative size of quantities.
• Geometry: Classical synthetic proofs split on whether points are collinear, whether angles are acute/right/obtuse, or whether a configuration is convex — genuinely different sub-arguments per case.
• Computer science and formal verification: Correctness proofs of algorithms routinely case-split on branches of an `if`/`else` statement or the outcome of a comparison; type-checking rules in programming language theory are proved sound by structural induction combined with case analysis on syntactic form.
• Discrete mathematics and combinatorics: The pigeonhole principle and many counting arguments proceed by exhaustively partitioning a finite set into cases and bounding or counting each separately.
• Cryptography: Security proofs for protocols frequently perform case analysis on adversarial strategies, showing that no matter which of finitely many attack patterns is attempted, a bound on success probability holds.
• Statistics and probability: The law of total probability, $P(A) = \sum_i P(A \mid C_i)P(C_i)$ for an exhaustive partition $\{C_i\}$ of the sample space, is the probabilistic incarnation of exactly the same exhaustiveness principle used here.

Ask the tutor: How does proof by cases combine with proving the two directions of a biconditional, as in Proof of Biconditionals?

Think of the hypothesis $P$ as describing a set of objects (all integers, all real numbers, all triangles) about which you want to prove $Q$. A case split $C_1, \dots, C_n$ partitions — or at least covers — this set into regions. Proof by cases says: if you can show the region boundary lines are drawn so that every object falls into at least one region, and if $Q$ holds throughout each region separately, then $Q$ holds everywhere. The picture below shows this as a covering of a number line: the integers are covered by "even" and "odd," two overlapping-free but jointly exhaustive regions, and separately one might instead cover the reals by three overlapping regions "negative," "zero," "positive" used in an inequality argument.

The essential logical content is a disjunction elimination pattern from propositional logic: if you know $A \lor B$, and you know both $A \Rightarrow Q$ and $B \Rightarrow Q$, then you may conclude $Q$ regardless of which of $A, B$ actually holds — because in either case $Q$ follows. This is exactly how "or" is used on the left-hand side of an implication, and it generalizes immediately from two cases to any finite number of cases.

Example 1 (asymmetric three-way split, number theory). Claim. For every integer $n$, the number $n^3 - n$ is divisible by $6$. Proof. Factor $n^3 - n = n(n-1)(n+1)$, a product of three consecutive integers $n-1, n, n+1$. We will show $6 \mid n(n-1)(n+1)$ by showing separately that $2$ divides this product and that $3$ divides it (and $2, 3$ are coprime, so their product $6$ divides it too — we justify this subordinate fact below). Divisibility by $2$. Among any two consecutive integers, one is even. Since $n-1$ and $n$ are consecutive, at least one of them is even, hence $2 \mid n(n-1)$, hence $2 \mid n(n-1)(n+1)$. Divisibility by $3$, by cases on $n \bmod 3$. Every integer $n$ leaves remainder $0$, $1$, or $2$ upon division by $3$; this is the exhaustiveness step, justified by the division algorithm ($n = 3q + r$ with $r \in \{0,1,2\}$ uniquely determined). We consider the three cases.

• Case $C_1$: $n \equiv 0 \pmod 3$. Then $3 \mid n$, so $3 \mid n(n-1)(n+1)$.
• Case $C_2$: $n \equiv 1 \pmod 3$. Then $n - 1 \equiv 0 \pmod 3$, so $3 \mid (n-1)$, so $3 \mid n(n-1)(n+1)$.
• Case $C_3$: $n \equiv 2 \pmod 3$. Then $n + 1 \equiv 3 \equiv 0 \pmod 3$, so $3 \mid (n+1)$, so $3 \mid n(n-1)(n+1)$.

In every case $3 \mid n(n-1)(n+1)$, and since $C_1 \lor C_2 \lor C_3$ is guaranteed for every integer $n$, we conclude $3 \mid n(n-1)(n+1)$ always, by Proof by Cases (the theorem proved above). Combining. We now have $2 \mid n(n-1)(n+1)$ and $3\mid n(n-1)(n+1)$ for every integer $n$. Since $\gcd(2,3)=1$, whenever two coprime integers $a,b$ both divide an integer $m$, their product $ab$ divides $m$ (this is a standard consequence of unique factorization / Bézout's identity, itself provable by direct proof and not requiring proof by cases). Hence $6 = 2\cdot 3$ divides $n(n-1)(n+1) = n^3-n$ for every integer $n$. $\blacksquare$ Notice the case split here was over remainders mod $3$ — a genuinely three-way, non-symmetric split — nested inside a divisibility argument that itself used a two-way parity split. This illustrates that cases can be nested: a case-by-case proof of one sub-claim ($3\mid \cdots$) sits inside a larger direct argument.

Example 2 (asymmetric split driven by absolute values, inequalities). Claim. For all real numbers $x$ and $y$,

Proof. We use the case split on the sign of $x$ and the sign of $y$ separately, but exploit an asymmetric shortcut rather than checking all $4$ sign-combinations symmetrically, to show the method does not require a mechanically uniform grid of cases. First, a preliminary fact used repeatedly: for any real $t$, we have $-|t| \le t \le |t|$. Indeed, if $t \ge 0$ then $|t| = t$, so $t \le |t|$ holds with equality, and $-|t| = -t \le 0 \le t$ since $t\ge 0$. If $t < 0$ then $|t| = -t > 0$, so $t < 0 < |t|$, giving $t \le |t|$; and $-|t| = t \le t$, giving $-|t| \le t$. Either way $-|t|\le t\le |t|$. (This itself was a two-case proof of a lemma.) Applying this lemma to $t = x$ and $t = y$ and adding the inequalities:

So $x+y$ lies between $-(|x|+|y|)$ and $|x|+|y|$. Now we split into cases on the sign of $x+y$ — an exhaustive two-case split since every real number is $\ge 0$ or $< 0$.

• Case $C_1$: $x + y \ge 0$. Then $|x+y| = x+y$, and we showed $x + y \le |x|+|y|$ directly above, so $|x+y| \le |x|+|y|$.
• Case $C_2$: $x+y < 0$. Then $|x+y| = -(x+y)$. From $-(|x|+|y|) \le x+y$ we get, multiplying both sides by $-1$ (which reverses the inequality), $-(x+y) \le |x|+|y|$. Hence $|x+y| = -(x+y) \le |x|+|y|$.

Since $C_1 \lor C_2$ is guaranteed (every real number is nonnegative or negative — exhaustive by trichotomy of the reals) and $Q: |x+y|\le|x|+|y|$ follows in each case, we conclude $|x+y|\le|x|+|y|$ for all real $x,y$. $\blacksquare$ This example shows a case split reduced from a naive "four cases on signs of $x$ and $y$" to a leaner two-case split on the sign of the sum $x+y$, after a shared computation (the lemma) did the common work up front — a typical and desirable feature of well-organized casework: push shared reasoning before the split, and split only on what actually differs.

Proof by cases has no single inventor — it is as old as deductive argument itself, embedded already in Euclid's Elements, where geometric configurations are routinely split according to whether a point lies inside, on, or outside a given figure. Its formal logical justification, however, crystallizes with the development of propositional logic.