Proof Techniques

The Art of Mathematical Proof

Mathematics is built on proofs — rigorous arguments that a statement is true. The main proof strategies are:

Direct proof: Assume $P$, deduce $Q$ step by step.

Proof by contrapositive: To prove $P \Rightarrow Q$, prove instead $\neg Q \Rightarrow \neg P$ (logically equivalent).

Proof by contradiction: Assume the negation of what you want to prove, derive a contradiction.

Proof by induction: Prove a base case $P(1)$, then prove $P(k) \Rightarrow P(k+1)$.

Example: Direct Proof

Claim: $1 + 2 + \cdots + n = \dfrac{n(n+1)}{2}$

We verify this computationally and use it:

def sum_formula(n):
    return n * (n + 1) // 2

print(sum_formula(100))  # 5050

Example: Proof by Contradiction — Infinitely Many Primes

Euclid's proof: if only finitely many primes $p_1, \ldots, p_k$ exist, then $N = p_1 \cdots p_k + 1$ is not divisible by any of them — a contradiction, since every integer $> 1$ has a prime factor.

def euclid_contradiction(primes):
    product = 1
    for p in primes:
        product *= p
    candidate = product + 1
    return all(candidate % p != 0 for p in primes)

print(euclid_contradiction([2, 3, 5]))  # True — 31 is not divisible by 2, 3, or 5

Your Task

Implement sum_formula(n) and euclid_contradiction(primes) as shown above.