Proof Methods and Strategy

Overview

This topic synthesizes all proof techniques and provides strategic guidance on when and how to apply each method. Mastering proof strategy is like learning chess - you need to know not just the moves, but when to use them.

The Proof Strategy Framework

Step 1: Understand the Statement

Questions to ask:

1. What is being claimed?
2. What are the hypotheses (givens)?
3. What is the conclusion (to prove)?
4. What is the domain (integers, real numbers, etc.)?
5. Are there hidden quantifiers?

Example: “Every even number greater than 2 can be expressed as the sum of two primes.”

• Hidden form: ∀n ((n is even) ∧ (n > 2) → ∃p,q (p, q are primes ∧ n = p + q))
• Domain: Natural numbers
• Hypothesis: n is even and n > 2
• Conclusion: n is sum of two primes

Step 2: Classify the Statement Type

Step 3: Choose Your Weapon (Proof Method)

Comprehensive Proof Methods Guide

Method 1: Direct Proof

When to use:

• Statement is p → q
• You can see a clear path from p to q
• Definitions and known facts naturally lead to conclusion

Structure:

1. State what you're proving
2. Assume p (the hypothesis)
3. Apply definitions, axioms, theorems
4. Conclude q

Example: Prove if n is even, then 3n + 2 is even.

Proof: Assume n is even. Then n = 2k for some integer k (definition). Thus 3n + 2 = 3(2k) + 2 = 6k + 2 = 2(3k + 1). Since 3k + 1 is an integer, 3n + 2 is even. ✓

Advantages:

• Most straightforward
• Easy to follow
• Builds intuition

Disadvantages:

• Sometimes the path isn’t clear
• Can get stuck in the middle

Method 2: Proof by Contrapositive

When to use:

• Proving p → q directly is difficult
• ¬q is easier to work with than q
• Proving “not” something is easier
• Statement involves uniqueness or irrationality

Remember: p → q ≡ ¬q → ¬p

Structure:

1. State you'll prove the contrapositive
2. Assume ¬q
3. Deduce ¬p
4. Conclude original statement

Example: Prove if 3n + 1 is even, then n is odd.

Contrapositive: If n is even, then 3n + 1 is odd.

Proof: Assume n is even. Then n = 2k, so 3n + 1 = 3(2k) + 1 = 6k + 1 = 2(3k) + 1. Thus 3n + 1 is odd. Therefore, if 3n + 1 is even, then n is odd. ✓

Advantages:

• Sometimes much easier than direct
• Equally valid as direct proof

Disadvantages:

• Need to recognize when it helps
• Can confuse beginners

Method 3: Proof by Contradiction

When to use:

• Proving a “not” statement (¬p)
• Proving irrationality
• Proving infinitude
• Proving uniqueness
• When direct and contrapositive don’t work
• Statement is “there is no…”

Structure:

1. State you'll use contradiction
2. Assume ¬p (opposite of what you want)
3. Derive a logical contradiction
4. Conclude p must be true

Example: Prove there is no largest even integer.

Proof: Suppose, for contradiction, there is a largest even integer N. Consider N + 2. N + 2 is even (sum of evens) and N + 2 > N. This contradicts that N is the largest even integer. Therefore, there is no largest even integer. ✓

Advantages:

• Very powerful
• Sometimes only viable method
• Can prove impossible things don’t exist

Disadvantages:

• Doesn’t provide constructive information
• Can be harder to find the contradiction
• Easy to make logical errors

Method 4: Proof by Cases

When to use:

• Statement naturally divides into categories
• Different situations require different reasoning
• Working with absolute values, piecewise functions
• Dealing with even/odd, positive/negative/zero
• “Either…or…” in hypothesis

Structure:

1. Identify exhaustive cases
2. Prove statement for Case 1
3. Prove statement for Case 2
...
n. Conclude statement holds in all cases

Example: Prove |n²| = n² for all integers n.

Proof: Case 1: n > 0 Then n² > 0, so |n²| = n². ✓

Case 2: n = 0 Then n² = 0, so |n²| = |0| = 0 = n². ✓

Case 3: n < 0 Then n² > 0 (negative times negative), so |n²| = n². ✓

In all cases, |n²| = n². ✓

Advantages:

• Breaks complex problem into simpler parts
• Each case may be easy
• Very systematic

Disadvantages:

• Must ensure cases are exhaustive
• Can be tedious with many cases
• Each case still needs proof

Method 5: Proof by Biconditional (Iff)

When to use:

• Statement is “p if and only if q”
• Proving equivalence
• Definition proofs

Remember: p ↔ q means both p → q AND q → p

Structure:

1. Prove p → q (forward direction)
2. Prove q → p (backward direction)
3. Conclude p ↔ q

Example: Prove n is even if and only if n² is divisible by 4.

Proof:

(⇒) If n is even, then n² is divisible by 4: Let n = 2k. Then n² = 4k² = 4(k²), so 4 | n². ✓

(⇐) If n² is divisible by 4, then n is even: Prove contrapositive: if n is odd, then n² is not divisible by 4. Let n = 2k + 1. Then n² = 4k² + 4k + 1 = 4(k² + k) + 1. Since n² = 4m + 1, we have 4 ∤ n². ✓

Therefore, n is even ↔ n² is divisible by 4. ✓

Advantages:

• Proves two-way relationship
• Systematic approach

Disadvantages:

• Two proofs required
• Both directions may have different difficulties

Method 6: Mathematical Induction

When to use:

• Proving statements about natural numbers: ∀n ∈ ℕ, P(n)
• Formulas for sums, products, inequalities
• Divisibility for all n
• Recursive definitions

Structure:

1. Base Case: Prove P(1) (or P(0))
2. Inductive Hypothesis: Assume P(k) for arbitrary k
3. Inductive Step: Prove P(k) → P(k+1)
4. Conclusion: By induction, P(n) for all n

Example: Prove 1 + 2 + 3 + … + n = n(n+1)/2 for all n ≥ 1.

Proof:

Base Case (n = 1): LHS = 1, RHS = 1(1+1)/2 = 1. ✓

Inductive Hypothesis: Assume 1 + 2 + … + k = k(k+1)/2 for some k.

Inductive Step: We prove the statement for k + 1: 1 + 2 + … + k + (k+1) = [1 + 2 + … + k] + (k+1) = k(k+1)/2 + (k+1) [by hypothesis] = (k+1)[k/2 + 1] = (k+1)(k+2)/2 = (k+1)((k+1)+1)/2. ✓

By induction, the formula holds for all n ≥ 1. ✓

Advantages:

• Powerful for sequences and series
• Very systematic
• Proves infinite cases

Disadvantages:

• Only works for natural numbers
• Doesn’t explain why formula is true
• Inductive step can be tricky

Method 7: Constructive Existence Proof

When to use:

• Proving ∃x P(x)
• Finding explicit examples
• Algorithm design

Structure:

1. Find or construct specific x₀
2. Verify P(x₀) is true
3. Conclude ∃x P(x)

Example: Prove there exists an integer n such that n² - n = 6.

Proof: Consider n = 3. Then n² - n = 9 - 3 = 6. ✓ Therefore, such an n exists. ✓

Advantages:

• Provides actual example
• Constructive (useful in CS)
• Usually straightforward

Disadvantages:

• Finding the example may be hard
• Doesn’t work if we can’t find example

Method 8: Non-Constructive Existence Proof

When to use:

• Proving ∃x P(x) when explicit example is hard to find
• Using contradiction or pigeonhole principle

Example: Prove there exist irrational numbers a and b such that a^b is rational.

Proof: Consider a = √2, b = √2. If √2^(√2) is rational, we’re done. If √2^(√2) is irrational, let a = √2^(√2), b = √2. Then a^b = (√2^(√2))^(√2) = √2^2 = 2 (rational). ✓

Advantages:

• Can prove existence without finding the object
• Sometimes easier than constructive

Disadvantages:

• Doesn’t tell us what the object is
• Less useful for computation

Decision Tree for Proof Method Selection

START
│
├─ Is it "∀n ∈ ℕ, P(n)"?
│   └─ YES → Try MATHEMATICAL INDUCTION
│
├─ Is it "∃x P(x)"?
│   └─ YES → Try CONSTRUCTIVE PROOF (find example)
│
├─ Is it "p ↔ q"?
│   └─ YES → BICONDITIONAL (prove both directions)
│
├─ Is it "p → q"?
│   ├─ Can you see clear path p → q?
│   │   └─ YES → DIRECT PROOF
│   │
│   ├─ Is ¬q easier to work with?
│   │   └─ YES → CONTRAPOSITIVE
│   │
│   └─ Still stuck?
│       └─ Try CONTRADICTION
│
├─ Are there natural cases (even/odd, +/-/0)?
│   └─ YES → PROOF BY CASES
│
└─ Is it a "not" statement or impossibility?
    └─ YES → CONTRADICTION

Advanced Strategies

Strategy 1: Working Backwards

Start from what you want to prove and work back to what you know.

Example: Prove if n² is even, then n is even.

Thinking:

• Want: n is even (n = 2k)
• Have: n² is even (n² = 2m)
• Bridge: If n = 2k, then n² = 4k² = 2(2k²) ✓

But this is backwards! So use contrapositive:

• If n is odd, then n² is odd (this direction is easier)

Strategy 2: Look for Patterns

Test small cases to see the pattern.

Example: Prove 1³ + 2³ + … + n³ = [n(n+1)/2]²

Test:

• n=1: 1³ = 1, [1×2/2]² = 1 ✓
• n=2: 1³+2³ = 9, [2×3/2]² = 9 ✓
• n=3: 1³+2³+3³ = 36, [3×4/2]² = 36 ✓

Now prove by induction!

Strategy 3: Strengthen the Hypothesis

Sometimes proving a stronger statement is easier.

Example: Instead of proving “n² is even”, prove “n² is divisible by 4” (stronger, may be easier path)

Strategy 4: Use Equivalent Forms

Rewrite the statement in an equivalent but easier form.

Example:

• Instead of proving p → q
• Prove ¬p ∨ q (equivalent)

Common Proof Pitfalls

Pitfall 1: Circular Reasoning

Wrong: Assume what you’re trying to prove.

Example:

Prove: n² is even if n is even
Wrong: Assume n² is even... [circular!]

Pitfall 2: Proof by Example

Wrong: Showing it’s true for specific cases doesn’t prove “for all”.

Example:

Wrong: 2²=4 is even, 4²=16 is even, so all even squares are even.
Right: Let n=2k, then n²=4k²=2(2k²) is even.

Pitfall 3: Assuming the Converse

Wrong: Proving q → p instead of p → q.

Pitfall 4: Incomplete Cases

Wrong: Forgetting case n=0 or negative cases.

Pitfall 5: False Contradiction

Wrong: Claiming contradiction when statements aren’t actually contradictory.

Exam Strategy Tips

Before the Exam

1. Memorize key definitions (even, odd, prime, divisibility, etc.)
2. Practice standard proofs (sum of evens, √2 irrational, etc.)
3. Know all proof methods and when to use each
4. Do many practice problems - variety is key

During the Exam

1. Read carefully - understand what’s being asked
2. Identify the statement type - this guides method choice
3. Start with what you know - write down definitions
4. Try the easiest method first (usually direct)
5. If stuck, try contrapositive - often much easier
6. Show all steps - partial credit!
7. Use clear language - “assume”, “therefore”, “thus”
8. Check your logic - does each step really follow?
9. End with a conclusion - restate what you proved

Time Management

1. Easy proofs first - build confidence and secure points
2. Skip and return - don’t get stuck on one proof
3. Partial proofs count - show your thinking even if incomplete

Key Takeaways

1. No single method works for everything - be flexible
2. Practice is essential - proofs are a skill, not just knowledge
3. Understand, don’t memorize - memorized proofs don’t help new problems
4. Start simple - master easy proofs before hard ones
5. Learn from mistakes - understanding errors builds skill
6. Read others’ proofs - see different approaches
7. Write clearly - proof is communication
8. Be patient - proof skill develops over time

Mega Practice Set

1. Prove by direct: If n is odd, then n² - 1 is divisible by 8.

2. Prove by contrapositive: If n² + 3 is odd, then n is even.

3. Prove by contradiction: log₂(3) is irrational.

4. Prove by cases: For all real x, x|x| = |x²|.

5. Prove biconditional: n³ is even ↔ n is even.

6. Prove by induction: 2ⁿ > n² for all n ≥ 5.

7. Prove existence: There exist integers a, b, c such that a² + b² = c².

8. Disprove: For all positive integers n, n² + n + 41 is prime.

9. Prove: The product of three consecutive integers is divisible by 6.

10. Prove: There is no rational number r such that r² = 3.