Proof Strategies

What is a Mathematical Proof?

A mathematical proof is a logical argument that establishes the truth of a mathematical statement beyond any doubt. It uses axioms, definitions, previously proven theorems, and rules of inference.

Why Do We Need Proofs?

1. Verify Truth: Confirm that a statement is always true
2. Understand Why: Explain why something is true, not just that it is
3. Discover New Results: Lead to new theorems and insights
4. Build Foundation: Create a solid base for further mathematics
5. Develop Reasoning: Train logical thinking skills

Types of Theorems

1. Theorem

A mathematical statement that has been proven to be true.

Example: “The sum of two even numbers is even.”

2. Lemma

A helper theorem used to prove a larger theorem.

Example: Small results proven to help prove a bigger theorem.

3. Corollary

A theorem that follows easily from another theorem.

Example: “If a number is divisible by 4, it’s divisible by 2” (follows from divisibility properties)

4. Conjecture

A statement believed to be true but not yet proven.

Example: Goldbach’s Conjecture: “Every even number > 2 is the sum of two primes.”

Overview of Proof Strategies

There are several strategies for constructing proofs. Choosing the right one depends on the form of the statement you’re proving.

Statement Forms and Suitable Strategies

1. Direct Proof Strategy

When to use: Proving conditional statements “If p, then q” (p → q)

Steps:

1. Assume p is true
2. Using axioms, definitions, and previously proven theorems
3. Show that q must be true

Structure:

Assume p is true.
[Logical steps...]
Therefore, q is true.

Example 1: Sum of Even Numbers

Theorem: If m and n are even integers, then m + n is even.

Proof:

• Assume m and n are even integers (p)
• By definition of even, m = 2k for some integer k
• And n = 2j for some integer j
• Then m + n = 2k + 2j = 2(k + j)
• Since k + j is an integer, m + n = 2(k + j) is even (q) ✓

Example 2: Divisibility

Theorem: If n is an odd integer, then n² is odd.

Proof:

• Assume n is odd
• By definition, n = 2k + 1 for some integer k
• Then n² = (2k + 1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1
• Since 2k² + 2k is an integer, n² is odd ✓

2. Proof by Contrapositive

When to use: When proving p → q directly is difficult, prove ¬q → ¬p instead

Why it works: p → q ≡ ¬q → ¬p (logically equivalent)

Steps:

1. Assume ¬q is true
2. Show that ¬p must be true
3. Conclude p → q is true

Structure:

To prove: If p, then q
Equivalently, we prove: If not q, then not p
Assume not q.
[Logical steps...]
Therefore, not p.

Example 1: Integer Squares

Theorem: If n² is even, then n is even.

Contrapositive: If n is odd, then n² is odd.

Proof:

• Assume n is odd (¬q)
• Then n = 2k + 1 for some integer k
• n² = (2k + 1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1
• So n² is odd (¬p) ✓
• Therefore, if n² is even, then n is even (original statement)

Example 2: Divisibility Property

Theorem: If 3 doesn’t divide n², then 3 doesn’t divide n.

Contrapositive: If 3 divides n, then 3 divides n².

Proof:

• Assume 3 divides n
• Then n = 3k for some integer k
• n² = (3k)² = 9k² = 3(3k²)
• So 3 divides n² ✓

3. Proof by Contradiction

When to use: To prove a statement p, especially when proving “not” statements or existence of irrationals

Steps:

1. Assume ¬p (the opposite of what we want to prove)
2. Show this leads to a contradiction (something that’s impossible)
3. Conclude that our assumption was wrong, so p must be true

Structure:

Suppose, for the sake of contradiction, that not p.
[Logical steps...]
This leads to a contradiction.
Therefore, p must be true.

Example 1: Irrationality of √2

Theorem: √2 is irrational.

Proof:

• Assume, for contradiction, that √2 is rational
• Then √2 = a/b where a, b are integers with no common factors (reduced form)
• Squaring both sides: 2 = a²/b²
• So a² = 2b²
• This means a² is even, so a is even (from previous theorem)
• Let a = 2k, then (2k)² = 2b²
• 4k² = 2b², so b² = 2k²
• This means b² is even, so b is even
• But if both a and b are even, they have a common factor of 2
• Contradiction! We said they had no common factors
• Therefore, √2 is irrational ✓

Example 2: Infinitely Many Primes

Theorem: There are infinitely many prime numbers.

Proof:

• Assume, for contradiction, that there are finitely many primes
• Let them be p₁, p₂, …, pₙ
• Consider N = (p₁ × p₂ × … × pₙ) + 1
• N is not divisible by any of p₁, p₂, …, pₙ (remainder is always 1)
• Either N is prime, or N has a prime factor not in our list
• Either way, we found a prime not in our “complete” list
• Contradiction!
• Therefore, there are infinitely many primes ✓

4. Proof by Cases

When to use: When the statement naturally divides into different cases

Steps:

1. Identify all possible cases
2. Prove the statement for each case separately
3. Conclude the statement is true in all cases

Structure:

We consider all possible cases:
Case 1: [condition]
  [Proof for case 1]
Case 2: [condition]
  [Proof for case 2]
...
In all cases, the statement holds.

Example 1: Absolute Value

Theorem: For any integer n, n² ≥ n.

Proof: We consider three cases:

Case 1: n > 1

• Then n² = n × n > n × 1 = n
• So n² > n ✓

Case 2: n = 0 or n = 1

• If n = 0: n² = 0 = n ✓
• If n = 1: n² = 1 = n ✓

Case 3: n < 0

• Then n² > 0 (square is always positive)
• And n < 0
• So n² > 0 > n ✓

In all cases, n² ≥ n.

Example 2: Product of Consecutive Integers

Theorem: The product of two consecutive integers is even.

Proof: Let the integers be n and n+1.

Case 1: n is even

• Then n = 2k for some integer k
• Product = n(n+1) = 2k(n+1) = 2(k(n+1))
• So the product is even ✓

Case 2: n is odd

• Then n+1 is even
• So n+1 = 2k for some integer k
• Product = n(n+1) = n(2k) = 2(nk)
• So the product is even ✓

In both cases, the product is even.

5. Proof by Biconditional (If and Only If)

When to use: Proving p ↔ q (p if and only if q)

Steps:

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

Structure:

To prove p ↔ q, we prove both directions.
(⇒) First, assume p and prove q.
  [Proof of p → q]
(⇐) Now, assume q and prove p.
  [Proof of q → p]
Therefore, p ↔ q.

Example: Even Number Characterization

Theorem: n is even if and only if n² is even.

Proof:

(⇒) If n is even, then n² is even:

• Assume n is even
• Then n = 2k for some integer k
• n² = (2k)² = 4k² = 2(2k²)
• So n² is even ✓

(⇐) If n² is even, then n is even:

• We’ll prove the contrapositive: if n is odd, then n² is odd
• Assume n is odd, so n = 2k + 1
• n² = (2k+1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1
• So n² is odd ✓

Therefore, n is even ↔ n² is even.

6. Constructive vs. Non-Constructive Proofs

Constructive Existence Proof

When to use: Proving ∃x P(x) by actually finding such an x

Example: “There exists an even prime number.”

Proof: 2 is an even prime number. ✓

Non-Constructive Existence Proof

When to use: Proving ∃x P(x) without explicitly finding x

Example: “There exist irrational numbers a and b such that a^b is rational.”

Proof:

• Consider a = √2 and b = √2
• Either a^b = √2^(√2) is rational or irrational
• If rational, we’re done (a = √2, b = √2)
• If irrational, let c = √2^(√2) and consider c^(√2)
• c^(√2) = (√2^(√2))^(√2) = √2^(√2 × √2) = √2^2 = 2 (rational!)
• So either √2^(√2) or (√2^(√2))^(√2) is rational
• Either way, such irrational a, b exist ✓

7. Uniqueness Proofs

When to use: Proving there is exactly one object with a property

Steps:

1. Existence: Show at least one such object exists
2. Uniqueness: Show there cannot be two different such objects

Structure:

Existence: [Show x exists with property P]
Uniqueness: Suppose x and y both have property P.
  [Show x = y]
Therefore, there is exactly one object with property P.

Example: Additive Identity

Theorem: There is exactly one additive identity for integers.

Proof:

Existence: 0 is an additive identity because n + 0 = n for all n.

Uniqueness:

• Suppose e₁ and e₂ are both additive identities
• Then n + e₁ = n for all n, and n + e₂ = n for all n
• Let n = e₂: e₂ + e₁ = e₂
• Let n = e₁: e₁ + e₂ = e₁
• By commutativity: e₁ + e₂ = e₂ + e₁
• So e₂ = e₁ + e₂ = e₁
• Therefore e₁ = e₂ ✓

There is exactly one additive identity.

Choosing the Right Strategy

Decision Guide

1. Is it p → q?

   • Try direct proof first
   • If stuck, try contrapositive
   • If still stuck, try contradiction

2. Is it p ↔ q?

   • Prove both p → q and q → p

3. Is it ∃x P(x)?

   • Try to construct an example (constructive proof)
   • Or use contradiction/other methods (non-constructive)

4. Is it ∀x P(x)?

   • Try direct proof for arbitrary x
   • Or use induction if it’s about natural numbers

5. Are there natural cases?

   • Use proof by cases

6. Is it a “not” statement?

   • Try proof by contradiction

Common Mistakes to Avoid

1. Assuming what you want to prove (circular reasoning)
2. Proving the converse instead of the statement
3. Using specific examples instead of general proof
4. Not covering all cases in case-by-case proof
5. Incorrect negation in contradiction proofs
6. Mixing up p → q with q → p

Key Points for Exams

1. Direct proof: Assume p, deduce q
2. Contrapositive: Prove ¬q → ¬p instead of p → q
3. Contradiction: Assume ¬p, derive contradiction
4. Cases: Divide into exhaustive cases, prove each
5. Biconditional: Prove both directions
6. Always state your strategy at the beginning
7. Each step should follow logically from previous steps
8. Use definitions precisely

Practice Problems

1. Prove directly: If n is odd, then n + 11 is even.

2. Prove by contrapositive: If n² is not divisible by 4, then n is odd.

3. Prove by contradiction: There is no largest even integer.

4. Prove by cases: |n²| = |n|² for all integers n.

5. Prove: n is divisible by 3 if and only if n² is divisible by 3.

6. Prove there exists a rational number between any two distinct rational numbers.

7. Which proof method would you use for: “If x² - 5x + 6 = 0, then x = 2 or x = 3”?

8. Prove: The product of a rational and an irrational number (not zero) is irrational.