Proofs

Structure: Assume P, derive Q through logical steps

"If n is even, then n^2 is even"

Proof:
  Assume n is even.
  Then n = 2k for some integer k.
  n^2 = (2k)^2 = 4k^2 = 2(2k^2).
  Since 2k^2 is an integer, n^2 is even.  □

Structure: Assume ¬Q, derive a contradiction

"sqrt(2) is irrational"

Proof:
  Assume sqrt(2) = p/q in lowest terms (gcd(p,q) = 1).
  Then 2 = p^2/q^2, so p^2 = 2q^2.
  Therefore p^2 is even, so p is even (p = 2k).
  Then (2k)^2 = 2q^2, so 4k^2 = 2q^2, so q^2 = 2k^2.
  Therefore q is even.
  But p and q both even contradicts gcd(p,q) = 1.
  Contradiction. So sqrt(2) is irrational.  □

Instead of proving P → Q, prove ¬Q → ¬P (logically equivalent)

"If n^2 is odd, then n is odd"
Contrapositive: "If n is even, then n^2 is even"  (easier!)

Proof:
  Assume n is even. Then n = 2k.
  n^2 = 4k^2 = 2(2k^2), which is even.  □

(See discrete-math.adoc for detailed treatment)

Structure:
  1. Base case: Prove P(n0)
  2. Inductive step: P(k) → P(k+1)
  Conclusion: P(n) for all n >= n0

To disprove "for all x, P(x)", find ONE x where P(x) is false.

"All primes are odd"
  Counterexample: 2 is prime and even.  □

"n^2 + n + 41 is prime for all n >= 0"
  Works for n = 0 through 39
  Counterexample: n = 40 → 40^2 + 40 + 41 = 1681 = 41^2  □

Strategy:
  Try small cases, boundary cases, zero, negatives
  Try n = 0, 1, -1, powers of 2, primes

Existence proof:
  Show something exists by constructing it or by contradiction
  Constructive: "There exists a prime > 100" → 101 is prime
  Non-constructive: "There exist irrational a, b where a^b is rational"

Proof by cases:
  Split into exhaustive cases, prove each separately
  "For all n, n^2 >= n when n >= 1 or n <= 0"
  Case 1: n >= 1 → n^2 = n × n >= 1 × n = n  ✓
  Case 2: n <= 0 → n^2 >= 0 >= n  ✓

Pigeonhole proofs:
  Show that n items in m < n containers forces a collision
  "In any 13 integers, two have the same remainder mod 12"

Counting two ways:
  Count the same set two different ways, equate the results
  Proves identities like C(n,k) = C(n, n-k)

Key phrases and what they mean:

  "WLOG" (without loss of generality)
    Reduce to one case when others are symmetric

  "Let ... be arbitrary"
    Universal quantifier — proof works for ANY choice

  "There exists ... such that"
    Existential claim — construct or derive the witness

  "Suppose for contradiction"
    About to assume the negation and derive absurdity

  "It suffices to show"
    Reducing the problem to a simpler claim

  "By the inductive hypothesis"
    Using the assumption from the inductive step

  □ or QED
    End of proof