Proof Techniques

A proof is a valid argument that establishes the truth of a mathematical statement. Mastering proof techniques is essential — proofs are the backbone of all theoretical computer science.

Terminology

• Axiom: A statement accepted as true without proof.
• Theorem: An important statement that has been proven true.
• Lemma: A "helper" theorem used to prove a larger result.
• Corollary: A result that follows directly from a theorem.
• Conjecture: A statement believed to be true but not yet proven.
• Proposition: A less important theorem (also used informally as a synonym for "statement").

Direct Proof

To prove p → q: Assume p is true, then show q must be true through a chain of logical deductions.

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

Proof: Assume n is odd. Then n = 2k + 1 for some integer k.

n² = (2k + 1)²
   = 4k² + 4k + 1
   = 2(2k² + 2k) + 1

Let m = 2k² + 2k. Then n² = 2m + 1, which is odd. ∎

Theorem: The sum of two even integers is even.

Proof: Let a and b be even integers. Then a = 2j and b = 2k for some integers j and k.

a + b = 2j + 2k = 2(j + k)

Since j + k is an integer, a + b is even. ∎

Proof by Contrapositive

To prove p → q: Prove the equivalent statement ¬q → ¬p.

This is often easier when proving q directly from p is difficult.

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

Proof (by contrapositive): We prove: if n is odd, then n² is odd.

Assume n is odd. Then n = 2k + 1 for some integer k.

n² = (2k + 1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1

This is odd. Therefore, by contrapositive, if n² is even, then n is even. ∎

Theorem: If 3n + 2 is odd, then n is odd.

Proof (by contrapositive): We prove: if n is even, then 3n + 2 is even.

Assume n is even. Then n = 2k.

3n + 2 = 3(2k) + 2 = 6k + 2 = 2(3k + 1)

This is even. ∎

Proof by Contradiction

To prove a statement p: Assume ¬p is true, then derive a logical contradiction (something of the form q ∧ ¬q).

Since ¬p leads to a contradiction, p must be true.

Theorem: √2 is irrational.

Proof: Assume for contradiction that √2 is rational. Then √2 = a/b where a and b are integers with no common factors (i.e., the fraction is in lowest terms).

√2 = a/b
2 = a²/b²
a² = 2b²

So a² is even, which means a is even (proved above). Write a = 2c.

(2c)² = 2b²
4c² = 2b²
b² = 2c²

So b² is even, which means b is even.

But then both a and b are even, contradicting our assumption that they have no common factors. ∎

Theorem: There are infinitely many prime numbers.

Proof (Euclid): Assume for contradiction that there are finitely many primes: p₁, p₂, ..., pₙ.

Consider N = p₁ · p₂ · ... · pₙ + 1.

N > 1, so N has a prime factor p. But N is not divisible by any pᵢ (dividing N by pᵢ always leaves remainder 1). So p is not in our list, contradicting the assumption that we listed all primes. ∎

Proof by Induction

Used to prove statements about natural numbers (or any well-ordered set).

Weak Induction

To prove ∀n ≥ n₀, P(n):

1. Base case: Prove P(n₀).
2. Inductive step: Prove that for all k ≥ n₀, P(k) → P(k + 1).

Then P(n) holds for all n ≥ n₀.

Why it works: P(n₀) is true (base case). P(n₀) → P(n₀ + 1) (inductive step), so P(n₀ + 1) is true. P(n₀ + 1) → P(n₀ + 2), so P(n₀ + 2) is true. And so on, for all n ≥ n₀.

Theorem: For all n ≥ 1, 1 + 2 + ... + n = n(n + 1)/2.

Proof:

Base case (n = 1): LHS = 1. RHS = 1(2)/2 = 1. ✓

Inductive step: Assume 1 + 2 + ... + k = k(k + 1)/2 for some k ≥ 1. (This is the inductive hypothesis.)

Show: 1 + 2 + ... + k + (k + 1) = (k + 1)(k + 2)/2.

1 + 2 + ... + k + (k + 1) = k(k + 1)/2 + (k + 1)     (by inductive hypothesis)
                            = k(k + 1)/2 + 2(k + 1)/2
                            = (k + 1)(k + 2)/2           ✓

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

Theorem: For all n ≥ 1, n³ - n is divisible by 3.

Proof:

Base case (n = 1): 1 - 1 = 0, which is divisible by 3. ✓

Inductive step: Assume 3 | (k³ - k) for some k ≥ 1.

(k + 1)³ - (k + 1) = k³ + 3k² + 3k + 1 - k - 1
                     = (k³ - k) + 3k² + 3k
                     = (k³ - k) + 3(k² + k)

By inductive hypothesis, 3 | (k³ - k), and clearly 3 | 3(k² + k). So 3 | ((k + 1)³ - (k + 1)). ∎

Strong Induction

To prove ∀n ≥ n₀, P(n):

1. Base case: Prove P(n₀) (and possibly P(n₀ + 1), ..., P(n₀ + j) if needed).
2. Inductive step: Prove that for all k ≥ n₀, if P(n₀) ∧ P(n₀ + 1) ∧ ... ∧ P(k) are all true, then P(k + 1) is true.

The difference from weak induction: the inductive hypothesis assumes all previous cases, not just the immediately preceding one.

Theorem: Every integer n ≥ 2 can be written as a product of primes.

Proof:

Base case (n = 2): 2 is prime, so it is a product of primes (itself). ✓

Inductive step: Assume every integer from 2 to k can be written as a product of primes. Consider k + 1.

• If k + 1 is prime, it is a product of primes (itself). ✓
• If k + 1 is composite, then k + 1 = a · b where 2 ≤ a, b ≤ k. By the strong inductive hypothesis, both a and b can be written as products of primes. Therefore k + 1 = a · b is also a product of primes. ✓

By strong induction, the statement holds for all n ≥ 2. ∎

Structural Induction

Used to prove properties of recursively defined structures (trees, lists, formulas, etc.).

Principle: To prove P(x) for all elements x of a recursively defined structure:

1. Base case: Prove P for the base elements.
2. Inductive step: For each recursive rule, assume P holds for the sub-components and prove P holds for the constructed element.

Example: Prove that the number of nodes in a full binary tree is 2ℓ - 1, where ℓ is the number of leaves.

Proof:

Base case: A single node has 1 leaf and 1 node. 2(1) - 1 = 1. ✓

Inductive step: A full binary tree T consists of a root with two full binary subtrees T₁ and T₂.

By hypothesis: nodes(T₁) = 2ℓ₁ - 1 and nodes(T₂) = 2ℓ₂ - 1.

nodes(T) = 1 + nodes(T₁) + nodes(T₂)
         = 1 + (2ℓ₁ - 1) + (2ℓ₂ - 1)
         = 2(ℓ₁ + ℓ₂) - 1
         = 2ℓ - 1              (since ℓ = ℓ₁ + ℓ₂) ✓

∎

Proof by Construction

To prove that something exists: Explicitly construct or exhibit it.

Theorem: There exist irrational numbers a and b such that aᵇ is rational.

Proof: Consider √2^√2.

• If √2^√2 is rational, take a = b = √2. Done.
• If √2^√2 is irrational, take a = √2^√2 and b = √2. Then:

aᵇ = (√2^√2)^√2 = √2^(√2 · √2) = √2² = 2

which is rational. Done.

In either case, we have found irrational a, b with aᵇ rational. ∎

Note: This is also an example of a non-constructive proof — we don't know which case holds, but we know one of them does.

Proof by Exhaustion (Case Analysis)

Prove a statement by checking all possible cases.

Theorem: For all n, n² + n is even.

Proof:

Case 1: n is even. Then n = 2k, so n² + n = 4k² + 2k = 2(2k² + k), which is even.

Case 2: n is odd. Then n = 2k + 1, so n² + n = (2k + 1)² + (2k + 1) = 4k² + 4k + 1 + 2k + 1 = 4k² + 6k + 2 = 2(2k² + 3k + 1), which is even.

Since every integer is either even or odd, and both cases give an even result, n² + n is always even. ∎

Disproof by Counterexample

To disprove a universal statement ∀x P(x): Find a single x for which P(x) is false.

Claim (false): Every odd number is prime.

Disproof: 9 = 3 × 3 is odd but not prime. ∎

Claim (false): For all positive integers n, n² + n + 41 is prime.

Disproof: At n = 40: 40² + 40 + 41 = 1681 = 41². Not prime. ∎

(Interestingly, this formula gives primes for n = 0, 1, 2, ..., 39.)

Proof Strategies: When to Use What

| Technique | Use When | |---|---| | Direct proof | The implication p → q has a straightforward logical chain | | Contrapositive | Proving ¬q → ¬p is easier (e.g., "if n² is even then n is even") | | Contradiction | The statement is about non-existence or impossibility (e.g., "√2 is irrational") | | Weak induction | Proving a property for all natural numbers where P(k + 1) depends only on P(k) | | Strong induction | P(k + 1) depends on multiple earlier cases (e.g., factorization, Fibonacci properties) | | Structural induction | Proving properties of recursive data structures (trees, lists, formulas) | | Construction | Proving existence — "there exists an X with property Y" | | Exhaustion | Finitely many cases to check, or a natural case split | | Counterexample | Disproving a claim — only need one example where it fails |

Common Proof Pitfalls

1. Assuming what you want to prove (circular reasoning / begging the question).
2. Confusing "for all" with "there exists" — proving one example doesn't establish a universal claim.
3. Incorrect base case in induction — an induction proof is only as strong as its base case.
4. Forgetting to check the inductive step applies to the base — the step must be valid starting from the base case.
5. Using a specific value in a general proof — if you need to prove something for all n, don't substitute a particular n (unless doing case analysis).
6. Misapplying strong induction — you must still ensure the inductive step works for k + 1 using any/all of the preceding cases.

Real-World Applications

• Algorithm correctness: Loop invariants are proved by induction. Termination is proved by showing a decreasing measure.
• Data structure invariants: Red-black tree properties, heap properties, and BST ordering are maintained through structural induction arguments.
• Cryptography: Security proofs use contradiction — if an adversary could break the scheme, we could solve a hard problem, contradicting its assumed hardness.
• Compiler correctness: Proving that transformations preserve program semantics uses structural induction on the syntax tree.
• Complexity theory: Many lower bound proofs use contradiction (e.g., if P = NP, then ...).