Mathematical Proof Techniques: Induction, Contradiction, and Logical Reasoning
Introduction
Mathematical proof is the foundation of all mathematical knowledge. Unlike the sciences, which test hypotheses through experiment and observation, mathematics establishes truth through logical deduction from axioms. A proof is a sequence of logical steps that leads from known truths to a desired conclusion, with each step justified by previously established results or the rules of logic.
The concept of proof has evolved throughout history. Greek mathematicians like Euclid formalized deductive reasoning in the Elements. The development of symbolic logic in the nineteenth and twentieth centuries, through the work of Frege, Russell, Hilbert, and Gödel, made the notion of proof precise enough to be studied mathematically. Today, proofs can be checked by computers, and the search for proofs drives mathematical research.
Direct Proof
A direct proof proceeds by assuming the hypotheses and applying logical deductions to reach the conclusion. It is the most straightforward and common proof technique. To prove a statement of the form “if P then Q,” assume P is true and show that Q necessarily follows.
Example: Sum of Even Numbers
To prove that the sum of two even numbers is even, assume a and b are even. Then a = 2m and b = 2n for some integers m, n. The sum a + b = 2m + 2n = 2(m + n), which is even. This simple direct proof illustrates the essence of mathematical reasoning: using definitions to transform the problem into a form that directly yields the conclusion.
Direct proofs often involve unpacking definitions and applying known theorems. The success of a direct proof depends on choosing the right sequence of logical steps, each justified by prior knowledge. Building skill in direct proof is essential before tackling more complex techniques.
Proof by Induction
Mathematical induction proves statements about natural numbers. The principle states: if a statement P(n) is true for n = 0 (or n = 1), and if P(k) implies P(k + 1) for all k, then P(n) is true for all natural numbers n.
Strong Induction
Strong induction allows the induction hypothesis to assume the truth of P(j) for all j ≤ k, not just for j = k. This variant is essential when the inductive step depends on earlier values beyond the immediate predecessor. The Fibonacci sequence Fₙ = F_{n-1} + F_{n-2} requires strong induction because the step uses two previous values.
Induction is intimately connected to the structure of the natural numbers and to the concept of recursion. The technique extends beyond numbers to any well-founded structure, such as trees in graph theory or formulas in logic. Transfinite induction extends induction to the ordinal numbers studied in set theory.
Proof by Contradiction
Proof by contradiction assumes the negation of the desired conclusion and derives a logical contradiction. This technique is surprisingly powerful and often yields proofs that would be difficult or impossible to construct directly.
The Classic Example
The classic proof that √2 is irrational uses contradiction. Assume √2 = a/b in lowest terms. Then 2 = a²/b², so 2b² = a². Thus a² is even, so a is even, and a = 2k. Substituting gives 2b² = 4k², so b² = 2k², and b is also even. This contradicts the assumption that a/b was in lowest terms.
The power of contradiction comes from the additional assumption — the negation of the conclusion — that can be used in the proof. This extra hypothesis often provides the leverage needed to derive a contradiction. The technique is particularly useful for proving negative statements — that something does not exist or cannot happen.
Proof by Contrapositive
The contrapositive of “if P then Q” is “if not Q then not P.” These two statements are logically equivalent: proving one proves the other. Sometimes the contrapositive is easier to prove than the original implication.
When to Use Contrapositive
Proof by contrapositive is particularly effective when the negation of Q provides a more convenient starting point than P itself. For example, to prove that if n² is odd then n is odd, the contrapositive “if n is even then n² is even” is straightforward: n = 2k implies n² = 4k² = 2(2k²) which is even.
The relationship between direct proof, contrapositive, and contradiction is worth understanding. Any proof by contrapositive can be rephrased as a proof by contradiction, but the contrapositive version is often more elegant and revealing.
Existence and Uniqueness Proofs
Existence proofs show that something exists. Constructive existence proofs produce an explicit example. Nonconstructive existence proofs show that existence is necessary without providing an example, often using the pigeonhole principle or the intermediate value theorem.
Constructive vs Nonconstructive
A constructive proof that there exists an even prime is simply to exhibit 2. A nonconstructive proof might show that a polynomial of odd degree has a real root without finding it — the intermediate value theorem guarantees existence.
Uniqueness proofs show that at most one object satisfies a given property. The standard approach is to assume two objects satisfy the property and then prove they are equal. Combining existence and uniqueness gives the most satisfying type of result: there is exactly one object with the given property.
Combinatorial Proofs
Combinatorial proofs establish identities by counting the same set in two different ways. These proofs are often elegant and revealing, providing insight into why an identity holds rather than merely verifying it algebraically.
Double Counting
The identity C(n, k) = C(n, n-k) can be proved combinatorially: choosing k elements from n is the same as choosing which n-k elements to exclude. The identity C(m+n, k) = Σ C(m, i)C(n, k-i) counts the number of ways to choose k elements from a set partitioned into two groups of sizes m and n.
Combinatorial proofs connect counting arguments to deeper mathematics. The connection between graph theory and linear algebra is illuminated by combinatorial proofs of matrix-tree theorems and spectral graph theory results.
Proofs in Number Theory
Number theory provides particularly instructive examples of proof techniques. The proof that there are infinitely many primes uses contradiction: assume finitely many primes p₁, …, pₙ, then consider N = p₁p₂…pₙ + 1. Either N is prime or has a prime factor not in the original list, contradicting the assumption.
Euclid’s proof is a masterpiece of economy — a few lines that settle a question that might otherwise seem open-ended. The technique of constructing a new object that avoids a finite set of obstructions appears throughout mathematics.
The Pigeonhole Principle
The pigeonhole principle states that if n items are placed into m boxes and n > m, then some box contains at least two items. Despite its simplicity, the pigeonhole principle is surprisingly powerful. It proves that in any set of 13 integers, two have a difference divisible by 12. It shows that any sequence of n² + 1 distinct real numbers contains a monotonic subsequence of length n + 1.
The pigeonhole principle is a combinatorial proof technique that does not rely on algebra or analysis. Its applications range from number theory to graph theory to computer science.
Advanced Techniques
The probabilistic method, pioneered by Erdős, proves existence by showing that a randomly chosen object has a positive probability of having the desired property. This method has revolutionized combinatorics and number theory.
The Diagonal Argument
Cantor’s diagonal argument shows that the real numbers are uncountable. This technique — constructing an element different from every element of a countable list — has been generalized throughout logic and computability theory. Turing used it to prove the undecidability of the halting problem, and Gödel used it in his incompleteness theorems.
Learning to recognize when to apply each proof technique is a skill developed through practice. The best mathematicians maintain a mental toolbox of techniques and draw on the appropriate one for each problem. For the logical foundations underlying all proof techniques, see logic foundations.
Proofs in Analysis
Analysis proofs often involve epsilon-delta arguments and approximation. The proof that the limit of a sum is the sum of limits requires splitting epsilon into two halves: given ε > 0, find N₁ such that |aₙ - A| < ε/2 for n > N₁ and N₂ such that |bₙ - B| < ε/2 for n > N₂. Then for n > max(N₁, N₂), |(aₙ + bₙ) - (A + B)| ≤ |aₙ - A| + |bₙ - B| < ε.
The technique of using ε/2 is a standard pattern in analysis proofs. The generalization to ε/2^k appears in proofs of the Weierstrass M-test and other convergence theorems. Mastering these epsilon-management techniques is essential for rigorous analysis.
The Nested Intervals Theorem
The nested intervals theorem states that a decreasing sequence of closed bounded intervals with lengths approaching zero contains a unique real number. The proof constructs a sequence of left endpoints and uses completeness to find their supremum, then shows this supremum belongs to all intervals.
This theorem is equivalent to the completeness of the real numbers and can be used to prove the Bolzano-Weierstrass theorem, the Heine-Borel theorem, and the intermediate value theorem. Understanding these equivalences reveals the logical structure of real analysis.
Formal Proof Verification
Modern proof assistants allow mathematicians to formalize proofs in a computer-checkable format. Systems like Coq, Lean, Isabelle, and HOL Light have been used to verify major theorems including the Feit-Thompson theorem, the Kepler conjecture, and the Four Color Theorem.
The formalization of mathematics in proof assistants is transforming mathematical practice. Libraries like Mathlib for Lean and the Archive of Formal Proofs for Isabelle contain thousands of formalized theorems. The goal of the formal proof community is to create a comprehensive library of formal mathematics.
What is the difference between a theorem and a lemma? A theorem is an important result. A lemma is a auxiliary result used in proving a theorem. A corollary follows directly from a theorem.
What makes a proof rigorous? A rigorous proof has every step justified by definitions, axioms, or previously established theorems. There are no gaps in the logical reasoning.
Can a proof be wrong? Yes. Mathematical history contains many published proofs that were later found to contain errors. Peer review and independent verification are essential.
How do mathematicians find proofs? Proof discovery is a creative process involving intuition, experimentation, analogy, and persistence. There is no algorithm for finding proofs.