Proof Techniques — Direct Proof, Contradiction, Contrapositive, Mathematical Induction and the Pigeonhole Principle

Tests show code works for the inputs you tried. A proof shows it works for all inputs. You won't write formal proofs daily, but the same reasoning is how you argue an algorithm is correct, find edge cases, and answer "why does this work?" in interviews.

1. Direct proof

Assume the premise, reason step by step to the conclusion.

Claim: the sum of two even numbers is even. Proof: let a = 2m, b = 2n. Then a + b = 2(m + n), which is even. ∎

2. Proof by contrapositive

To prove p → q, prove ¬q → ¬p (equivalent — lesson 2).

Claim: if n² is even, then n is even. Proof (contrapositive): suppose n is odd: n = 2k + 1. Then n² = 4k² + 4k + 1 = 2(2k² + 2k) + 1, which is odd. So "n odd ⇒ n² odd", which is the contrapositive. ∎

3. Proof by contradiction

Assume the claim is false and derive something impossible.

Claim: √2 is irrational. Proof: suppose √2 = a/b in lowest terms. Then 2b² = a², so a² is even, so a is even (section 2): a = 2c. Then 2b² = 4c², so b² = 2c², so b is even too. Both even contradicts "lowest terms". ∎

Claim (Euclid): there are infinitely many primes. Proof: suppose p₁ … pₖ are all the primes. Let N = p₁p₂…pₖ + 1. N leaves remainder 1 when divided by each pᵢ, so its prime factors aren't in the list — contradiction. ∎

4. Mathematical induction

To prove P(n) for all n ≥ n₀:

1. Base case: prove P(n₀).
2. Inductive step: assume P(k) (the inductive hypothesis) and prove P(k + 1).

Like dominoes: the first falls, and each one knocks over the next.

Claim: 1 + 2 + … + n = n(n + 1)/2.

• Base: n = 1: 1 = 1·2/2. ✓
• Step: assume 1 + … + k = k(k + 1)/2. Then 1 + … + k + (k + 1) = k(k + 1)/2 + (k + 1) = (k + 1)(k + 2)/2, which is the formula for k + 1. ∎

A computer can't prove it for all n, but it can quickly check thousands of cases — a good sanity check before (or after) a proof:

print(all(sum(range(1, n + 1)) == n * (n + 1) // 2 for n in range(1, 2001)), "for n = 1..2000")

# another classic: 2^n > n^2 for n >= 5 (fails for n = 2, 3, 4!)
print([n for n in range(1, 11) if not 2 ** n > n ** 2], "<- n where 2^n > n^2 is false")

True for n = 1..2000
[2, 3, 4] <- n where 2^n > n^2 is false

The second check shows why the base case matters: the claim 2ⁿ > n² is false for n = 2, 3, 4, and an induction proof must start at n = 5.

5. Strong induction

Assume P(n₀), …, P(k) all hold, then prove P(k + 1). Useful when a case depends on earlier ones, not just the previous one.

Claim: every integer ≥ 2 is a product of primes. Proof: if k + 1 is prime, done. Otherwise k + 1 = a·b with 2 ≤ a, b ≤ k; by the strong hypothesis both are products of primes, so k + 1 is too. ∎

6. Induction in code: loop invariants

A loop invariant is a statement true before and after every iteration — induction applied to loops. Proving a loop correct:

1. Initialisation (base): true before the loop.
2. Maintenance (step): if true before an iteration, still true after.
3. Termination: when the loop ends, the invariant gives the result.

def find_max(nums):
    best = nums[0]
    for i in range(1, len(nums)):
        # invariant: best == max(nums[0:i])
        assert best == max(nums[:i])
        if nums[i] > best:
            best = nums[i]
    return best   # at the end i == len(nums), so best == max(nums)

print(find_max([31, 7, 58, 22, 58, 4]))

58

Binary search, sorting algorithms and graph algorithms are all proved correct this way in textbooks and interviews.

7. The pigeonhole principle

If n + 1 pigeons go into n holes, some hole has at least 2 pigeons. Generalised: N objects into k boxes → some box has at least ⌈N/k⌉.

Examples:

• In any group of 367 people, two share a birthday (366 possible days).
• In a class of 50 students, at least ⌈50/12⌉ = 5 were born in the same month.
• Any 6 integers include two whose difference is divisible by 5 (only 5 possible remainders).
• Lossless compression can't shrink every file: there are more files of n bits than files shorter than n bits.

import math, random

print("50 students, 12 months -> at least", math.ceil(50 / 12), "in some month")

random.seed(3)
nums = random.sample(range(1, 1000), 6)
rem = {}
for x in nums:
    r = x % 5
    if r in rem:
        print(f"{nums}: {rem[r]} and {x} differ by {abs(x - rem[r])}, divisible by 5")
        break
    rem[r] = x

50 students, 12 months -> at least 5 in some month
[244, 607, 558, 134, 379, 938]: 244 and 134 differ by 110, divisible by 5

Common mistakes

• Skipping or getting the base case wrong in induction.
• Using the inductive hypothesis for k + 1 itself (circular).
• In contradiction proofs, assuming something that isn't the exact negation of the claim.
• Using pigeonhole with ⌊N/k⌋ instead of ⌈N/k⌉.

Quick recap

• Direct proof; contrapositive (prove ¬q → ¬p); contradiction (assume false, reach impossibility).
• Induction: base case + (P(k) ⇒ P(k+1)); strong induction assumes all earlier cases.
• Loop invariants = induction for code: initialise, maintain, terminate.
• Pigeonhole: N objects in k boxes ⇒ some box has ≥ ⌈N/k⌉.