Introduction
Successful mathematical reasoning requires more than knowing individual proof techniques. It requires understanding when to apply each technique, how to combine them, and how to recognize common patterns that appear across different problems.
In this article, we’ll explore common proof strategies and patterns that will help you become a more effective problem solver.
Proof Strategy Selection
Choosing the Right Technique
Different proof techniques are suited for different types of statements.
Universal Statements (∀x P(x)):
- Direct proof: Assume x is arbitrary, prove P(x)
- Proof by contradiction: Assume ∃x ¬P(x), derive contradiction
- Proof by induction: If P involves natural numbers
Existential Statements (∃x P(x)):
- Constructive proof: Find a specific x and show P(x)
- Proof by contradiction: Assume ¬∃x P(x), derive contradiction
Conditional Statements (P → Q):
- Direct proof: Assume P, prove Q
- Proof by contrapositive: Assume ¬Q, prove ¬P
- Proof by contradiction: Assume P ∧ ¬Q, derive contradiction
Biconditional Statements (P ↔ Q):
- Prove both directions: P → Q and Q → P
- Prove equivalence: Show P and Q have same truth value
Decision Tree for Proof Selection
Statement type?
├─ Universal (∀x P(x))
│ ├─ Involves natural numbers? → Try induction
│ ├─ Negative statement? → Try contradiction
│ └─ Otherwise → Try direct proof
├─ Existential (∃x P(x))
│ ├─ Can construct example? → Try constructive proof
│ └─ Otherwise → Try contradiction
├─ Conditional (P → Q)
│ ├─ Q is negative? → Try contrapositive
│ ├─ P is complex? → Try contradiction
│ └─ Otherwise → Try direct proof
└─ Biconditional (P ↔ Q)
└─ Prove both directions
Common Proof Patterns
Pattern 1: Proof by Cases
When a statement has multiple cases, prove each case separately.
Structure:
To prove: P(x) for all x
Case 1: If condition C₁ holds, then P(x)
Case 2: If condition C₂ holds, then P(x)
...
Case n: If condition Cₙ holds, then P(x)
Conclusion: P(x) holds in all cases
Example 1: Absolute Value
Theorem: |x| ≥ 0 for all real x
Proof:
Case 1: If x ≥ 0, then |x| = x ≥ 0 ✓
Case 2: If x < 0, then |x| = -x > 0 ✓
Therefore, |x| ≥ 0 for all x. ∎
Example 2: Divisibility
Theorem: For any integer n, n(n+1) is even
Proof:
Case 1: If n is even, then n = 2k for some k
n(n+1) = 2k(2k+1) = 2(k(2k+1)), which is even ✓
Case 2: If n is odd, then n = 2k+1 for some k
n(n+1) = (2k+1)(2k+2) = (2k+1)·2(k+1) = 2((2k+1)(k+1)), which is even ✓
Therefore, n(n+1) is even for all n. ∎
When to Use:
- Statement naturally divides into cases
- Each case is simpler than the whole
- Cases are exhaustive and mutually exclusive
Pattern 2: Proof by Exhaustion
A special case of proof by cases where all possibilities are enumerated.
Structure:
To prove: P(x) for x ∈ {a₁, a₂, ..., aₙ}
Check P(a₁), P(a₂), ..., P(aₙ)
Conclusion: P(x) holds for all x in the set
Example:
Theorem: For any integer n with 1 ≤ n ≤ 5, n² < 30
Proof:
n = 1: 1² = 1 < 30 ✓
n = 2: 2² = 4 < 30 ✓
n = 3: 3² = 9 < 30 ✓
n = 4: 4² = 16 < 30 ✓
n = 5: 5² = 25 < 30 ✓
Therefore, n² < 30 for all n ∈ {1,2,3,4,5}. ∎
When to Use:
- Finite set of possibilities
- Set is small enough to check all cases
- No general pattern is apparent
Pattern 3: Proof by Counterexample
To disprove a statement, find one counterexample.
Structure:
To disprove: ∀x P(x)
Find: x₀ such that ¬P(x₀)
Conclusion: The statement is false
Example 1:
Claim: All prime numbers are odd
Counterexample: 2 is prime and even
Therefore, the claim is false. ∎
Example 2:
Claim: If n is prime, then n+1 is composite
Counterexample: n = 2 is prime, but n+1 = 3 is also prime
Therefore, the claim is false. ∎
When to Use:
- Disproving universal statements
- One counterexample suffices
- Easier than proving the negation
Pattern 4: Proof by Analogy
Use a similar, proven result to guide the proof of a new statement.
Structure:
Known result: P(x) is true
Similar statement: Q(y) is true
Proof strategy: Use similar reasoning as for P(x)
Example:
Known: ∀x ∈ ℝ, x² ≥ 0
Analogous statement: ∀x ∈ ℝ, x⁴ ≥ 0
Proof: x⁴ = (x²)² ≥ 0 since x² ≥ 0 and squares are non-negative. ∎
When to Use:
- Similar problems have been solved
- Structure of new problem mirrors known result
- Provides intuition for proof strategy
Pattern 5: Proof by Reduction
Reduce a complex problem to a simpler, known problem.
Structure:
To prove: P
Reduce P to: Q (where Q is simpler or known)
Prove: Q
Conclude: P (by reduction)
Example:
Theorem: √6 is irrational
Proof:
Reduce to: If √6 is rational, then √2 is rational
Prove: If √6 = p/q (in lowest terms), then 6q² = p²
So p² is even, thus p is even: p = 2k
Then 6q² = 4k², so 3q² = 2k²
So q² is even, thus q is even
But this contradicts p/q being in lowest terms
Conclude: √6 is irrational. ∎
When to Use:
- Problem can be transformed to simpler form
- Simpler form is already solved
- Transformation preserves truth value
Pattern 6: Proof by Induction (Revisited)
Prove a statement for all natural numbers using base case and inductive step.
Structure:
Base case: Prove P(1) [or P(0)]
Inductive step: Assume P(k), prove P(k+1)
Conclusion: P(n) for all n ∈ ℕ
Example:
Theorem: 1 + 2 + ... + n = n(n+1)/2
Proof:
Base case (n=1): 1 = 1(2)/2 = 1 ✓
Inductive step:
Assume: 1 + 2 + ... + k = k(k+1)/2
Prove: 1 + 2 + ... + k + (k+1) = (k+1)(k+2)/2
1 + 2 + ... + k + (k+1) = k(k+1)/2 + (k+1)
= (k+1)(k/2 + 1)
= (k+1)(k+2)/2 ✓
Therefore, the formula holds for all n ∈ ℕ. ∎
When to Use:
- Statement involves natural numbers
- Pattern repeats for successive values
- Base case and inductive step are manageable
Pattern 7: Proof by Contradiction (Revisited)
Assume the negation and derive a contradiction.
Structure:
To prove: P
Assume: ¬P
Derive: Contradiction (Q ∧ ¬Q)
Conclude: P (by contradiction)
Example:
Theorem: There is no largest prime number
Proof:
Assume: There is a largest prime p
Let q = p! + 1 (p factorial plus 1)
Then q > p and q is not divisible by any prime ≤ p
So q is either prime or has a prime factor > p
Either way, there's a prime > p
This contradicts our assumption
Therefore, there is no largest prime. ∎
When to Use:
- Direct proof seems difficult
- Negation is easier to work with
- Contradiction is obvious once assumed
Advanced Proof Patterns
Pattern 8: Proof by Equivalence Chain
Show that a series of statements are equivalent.
Structure:
To prove: P ↔ Q ↔ R
Prove: P → Q, Q → R, R → P
Conclusion: All statements are equivalent
Example:
Theorem: For integer n, these are equivalent:
(1) n is even
(2) n² is even
(3) n² ≡ 0 (mod 4)
Proof:
(1) → (2): If n = 2k, then n² = 4k² = 2(2k²), so n² is even
(2) → (3): If n² is even, then n is even (contrapositive of odd→odd²)
So n = 2k, thus n² = 4k² ≡ 0 (mod 4)
(3) → (1): If n² ≡ 0 (mod 4), then n² is even, so n is even
Therefore, all three statements are equivalent. ∎
When to Use:
- Multiple statements to show equivalent
- Circular chain of implications
- Each implication is manageable
Pattern 9: Proof by Minimal Counterexample
Assume a counterexample exists and derive a contradiction using minimality.
Structure:
To prove: ∀x P(x)
Assume: ∃x ¬P(x)
Let: x₀ be the minimal counterexample
Derive: A smaller counterexample exists
Conclude: Contradiction, so P(x) for all x
Example:
Theorem: Every positive integer > 1 has a prime factor
Proof:
Assume: Some positive integer > 1 has no prime factor
Let n be the smallest such integer
Then n is not prime (else n is its own prime factor)
So n = ab where 1 < a, b < n
But a < n, so a has a prime factor p
Then p divides n, contradicting our assumption
Therefore, every positive integer > 1 has a prime factor. ∎
When to Use:
- Minimality argument is natural
- Smaller counterexample can be constructed
- Leads to clear contradiction
Pattern 10: Proof by Infinite Descent
Similar to minimal counterexample, but for infinite sequences.
Structure:
To prove: ∀x P(x)
Assume: ∃x ¬P(x)
Construct: Infinite descending sequence
Derive: Contradiction (can't descend infinitely)
Conclude: P(x) for all x
Example:
Theorem: √2 is irrational
Proof:
Assume: √2 = p/q in lowest terms
Then: 2q² = p², so p² is even, thus p = 2k
Then: 2q² = 4k², so q² = 2k², thus q is even
But: p and q are both even, contradicting lowest terms
Therefore, √2 is irrational. ∎
When to Use:
- Infinite descent is natural
- Leads to contradiction with finiteness
- Problem involves rational numbers or fractions
Combining Proof Strategies
Strategy 1: Proof by Cases + Induction
Use cases within an inductive proof.
Example:
Theorem: For all n ≥ 1, n³ + 2n is divisible by 3
Proof by induction:
Base case (n=1): 1³ + 2(1) = 3, divisible by 3 ✓
Inductive step:
Assume: k³ + 2k ≡ 0 (mod 3)
Prove: (k+1)³ + 2(k+1) ≡ 0 (mod 3)
(k+1)³ + 2(k+1) = k³ + 3k² + 3k + 1 + 2k + 2
= (k³ + 2k) + 3k² + 3k + 3
≡ 0 + 0 + 0 + 0 ≡ 0 (mod 3) ✓
Therefore, n³ + 2n is divisible by 3 for all n ≥ 1. ∎
Strategy 2: Proof by Contradiction + Induction
Use contradiction within an inductive proof.
Example:
Theorem: For all n ≥ 1, 2ⁿ > n
Proof by induction:
Base case (n=1): 2¹ = 2 > 1 ✓
Inductive step:
Assume: 2ᵏ > k
Prove: 2^(k+1) > k+1
2^(k+1) = 2·2ᵏ > 2k (by inductive hypothesis)
If 2k > k+1, then 2^(k+1) > k+1
2k > k+1 ⟺ k > 1, which is true for k ≥ 1
Therefore, 2ⁿ > n for all n ≥ 1. ∎
Common Mistakes to Avoid
Mistake 1: Circular Reasoning
Assuming what you’re trying to prove.
❌ Wrong: To prove n is even, assume n = 2k (already assuming even)
✓ Right: To prove n is even, show n = 2k for some integer k
Mistake 2: Incomplete Case Analysis
Missing cases or not covering all possibilities.
❌ Wrong: For integer n, if n > 0 then n² > 0 (missing n = 0)
✓ Right: For integer n, if n ≠ 0 then n² > 0
Mistake 3: Incorrect Induction
Forgetting base case or making unjustified inductive step.
❌ Wrong: Assume P(k), then P(k+1) follows (without showing how)
✓ Right: Assume P(k), then carefully derive P(k+1)
Mistake 4: Confusing Necessary and Sufficient
Proving the wrong direction.
❌ Wrong: To prove P → Q, prove Q → P instead
✓ Right: To prove P → Q, assume P and derive Q
Mistake 5: Overgeneralization
Concluding too much from limited evidence.
❌ Wrong: Checked n = 1,2,3 so it's true for all n
✓ Right: Use induction or other rigorous method
Glossary
- Proof strategy: Overall approach to proving a statement
- Proof pattern: Recurring structure in proofs
- Case analysis: Dividing proof into exhaustive cases
- Counterexample: Example showing a statement is false
- Reduction: Transforming problem to simpler form
- Equivalence chain: Series of equivalent statements
- Minimal counterexample: Smallest counterexample
- Infinite descent: Constructing infinite descending sequence
- Circular reasoning: Assuming what you’re trying to prove
- Inductive step: Proving P(k+1) from P(k)
Practice Problems
Problem 1: Selecting Proof Strategy
For each statement, suggest an appropriate proof strategy:
- “All even numbers are divisible by 2”
- “There exists a prime number greater than 100”
- “If n is odd, then n² is odd”
- “√3 is irrational”
Solution:
- Direct proof (definition of even)
- Constructive proof (find example: 101)
- Direct proof (assume n = 2k+1, show n² = 4k² + 4k + 1)
- Proof by contradiction (assume √3 = p/q)
Problem 2: Proof by Cases
Prove: For any integer n, n(n+1)(n+2) is divisible by 6
Solution: Case 1: n ≡ 0 (mod 3) → n is divisible by 3 Case 2: n ≡ 1 (mod 3) → n+2 ≡ 0 (mod 3) Case 3: n ≡ 2 (mod 3) → n+1 ≡ 0 (mod 3) Also, among n, n+1, n+2, at least one is even. Therefore, n(n+1)(n+2) is divisible by 6.
Problem 3: Proof by Induction
Prove: 1² + 2² + … + n² = n(n+1)(2n+1)/6
Solution: Base case: 1² = 1 = 1(2)(3)/6 ✓ Inductive step: Assume formula for k, prove for k+1 1² + … + k² + (k+1)² = k(k+1)(2k+1)/6 + (k+1)² = (k+1)[k(2k+1)/6 + (k+1)] = (k+1)(k+1)(2k+3)/6 ✓
Problem 4: Proof by Contradiction
Prove: There are infinitely many prime numbers
Solution: Assume: Finitely many primes p₁, p₂, …, pₙ Let: N = p₁·p₂·…·pₙ + 1 Then: N is not divisible by any pᵢ So: N is either prime or has a prime factor not in our list This contradicts our assumption. Therefore, there are infinitely many primes.
Related Resources
Online Platforms
- Stanford Encyclopedia of Philosophy - Logic articles
- Khan Academy Logic - Logic tutorials
- Coursera Logic Courses - Online courses
- MIT OpenCourseWare - University courses
- Brilliant.org Logic - Interactive lessons
Interactive Tools
- Proof Checker - Verify proofs
- Proof Assistant - Interactive proof development
- Logic Visualizer - Visualize logic
- Counterexample Finder - Find counterexamples
- Proof Planner - Plan proofs
Recommended Books
- “How to Prove It” by Velleman - Comprehensive proof strategies
- “Proofs and Refutations” by Lakatos - Philosophy of proof
- “The Art of Problem Solving” by Zeitz - Problem-solving strategies
- “Mathematical Proofs” by Chartrand, Polimeni, Zhang - Proof techniques
- “Introduction to Mathematical Reasoning” by Epp - Proof fundamentals
Academic Journals
- Journal of Symbolic Logic - Primary research
- Studia Logica - Logic research
- Mathematical Gazette - Teaching mathematics
- American Mathematical Monthly - Mathematics articles
- Mathematics Magazine - Mathematics education
Software Tools
- Coq - Theorem prover
- Isabelle - Proof assistant
- Lean - Theorem prover
- Z3 - SMT solver
- Prolog - Logic programming
Conclusion
Mastering proof strategies and patterns enables you to:
- Select appropriate techniques for different problems
- Recognize common proof structures
- Combine strategies effectively
- Avoid common mistakes
- Develop mathematical intuition
With practice, these strategies become intuitive, and you’ll develop the ability to recognize which approach works best for each problem.
Previous Article: Proof by Cases
Comments