Proof by cases

Break the domain into cases!

A proof by cases is a direct proof that proves a theorem is true by breaking its domain into a finite number of classes that are each handled separately in different mini-proofs called cases. For this kind of proof, every element in the domain must be a member of at least one of the classes. That way, the cases cover the entire domain.

Every case should be numbered and begin with "Case \(n\): " where \(n\) is the number of the case.

If the theorem you're trying to prove involves the absolute value of an expression, test it under two cases: one where the inner expression is negative, and one where it's non-negative. If the inner expression is negative, taking its absolute value will reverse its sign, and if it's non-negative, taking its absolute value will result in the same expression. The reasoning behind all this is that taking the absolute value of a number has a different effect based on if that number is negative or not, so you must consider both cases.

Also, for theorems about integers that are not explicitly stated as being even or odd, you can consider every combination of even and odd integers as separate cases. This will likely only be useful if the theorem is a statement about parity.

When two cases essentially prove the same thing, and are different only in variable names, they can be consolidated into one case "without loss of generality." (abbreviated as WLOG or w.l.o.g.) This allows you to save some time by avoiding redundant cases.

Logic & Proofs

Integer • Rational number • Inequality • Real number • Theorem • Proof • Statement • Proof by exhaustion • Universal generalization • Counterexample • Existence proof • Existential instantiation • Axiom • Logic • Truth • Proposition • Compound proposition • Logical operation • Logical equivalence • Tautology • Contradiction • Logic law • Predicate • Domain • Quantifier • Argument • Rule of inference • Logical proof • Direct proof • Proof by contrapositive • Irrational number • Proof by contradiction • Proof by cases • Summation • Disjunctive normal form

Set Theory

Set • Element • Empty set • Universal set • Subset • Power set • Cartesian product • String • Binary string • Empty string • Set operation • Set identity • Set proof

Functions

Function • Floor function • Ceiling function • Inverse function

Algorithms

Algorithm • Pseudocode • Command • Asymptotic notation • Time complexity • Atomic operation • Brute-force algorithm

Relations

Relation • Reflexive relation • Symmetric relation • Transitive relation • Relation composition • Equivalence relation • Equivalence class

Number Theory

Integer division • Linear combination • Division algorithm • Modular arithmetic • Prime factorization • Greatest common divisor • Least common multiple • Primality test • Factoring algorithm • Euclid's theorem • Prime number theorem • Euclidean algorithm

Induction

Proof by induction • Fibonacci sequence • Proof by strong induction • Well-ordering principle • Sequence • Factorial • Recursive definition

Combinatorics

Rule of product • Rule of sum • Bijection rule • Permutation • Combination • Complement rule • Experiment • Outcome • Sample space • Event • Probability • Probability distribution • Uniform distribution • Multiset • Sixfold way • Inclusion-exclusion principle • Pigeonhole principle

Graph Theory

Graph • Walk • Subgraph • Regular graph • Complete graph • Empty graph • Cycle graph • Hypercube graph • Bipartite graph • Component • Eulerian circuit • Eulerian trail • Hamiltonian cycle • Hamiltonian path • Tree • Huffman tree • Substring • Forest • Path graph • Star • Spanning tree • Weighted graph • Minimum spanning tree • Greedy algorithm • Prim's algorithm

Recursion

Recursion • Recursive algorithm • Correctness proof • Divide-and-conquer algorithm • Sorting algorithm • Merge sort