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

Source: https://skills101.in/learn/discrete-math/proofs-induction-pigeonhole — Skills101 free tutorial (Discrete Mathematics). Updated 2026-11-09.

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.

![Induction as dominoes: the base case knocks over the first domino, and the inductive step guarantees that whenever domino k falls, domino k plus 1 falls too, so all dominoes fall](https://skills101.in/learn-img/discrete-math/induction-dominoes.svg)

**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:

```python
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")
```

```text
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.

```python
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]))
```

```text
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⌉**.

![Pigeonhole principle: five pigeons and four holes, so at least one hole must contain two pigeons](https://skills101.in/learn-img/discrete-math/pigeonhole.svg)

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.

```python
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
```

```text
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⌉.


Practice quiz and free certificate: https://skills101.in/learn/discrete-math/proofs-induction-pigeonhole