Prerequisites: ch001-ch014
You will learn:
What a mathematical proof actually is and what it guarantees
The four main proof strategies: direct, contrapositive, contradiction, induction
How to read an existing proof and identify its structure
How to begin writing a proof from a conjecture
Environment: Python 3.x, numpy, matplotlib
1. Concept¶
A proof is a finite sequence of logical steps, each following from the previous by rules of inference, that establishes a statement is true for all cases in the claimed domain.
This is the fundamental difference between computation and mathematics. A computer program can test a conjecture on ten million cases. A proof establishes it for all cases, including the infinitely many untested ones.
Four standard proof strategies:
Direct proof: Assume P is true. Use definitions and known facts to derive Q.
Proof by contrapositive: Prove NOT-Q implies NOT-P instead of P implies Q (logically equivalent per ch014).
Proof by contradiction: Assume P and NOT-Q are both true. Derive a contradiction. Conclude Q must hold.
Mathematical induction: Prove P(1) (base case). Prove P(k) implies P(k+1). Conclude P(n) for all n >= 1.
Common misconception: A proof is just a very careful argument.
A proof is a formal argument -- every step must follow from a named rule or previously established fact. The role of computation: we use it to find the proof strategy, check intermediate steps, and verify once written.
2. Intuition & Mental Models¶
Physical analogy: Engineering certification. You can test a bridge by driving trucks over it thousands of times, but you cannot certify it safe for all loads by testing alone. Structural analysis certifies safety analytically. A mathematical proof is the analytical certification.
Computational analogy: Type checking vs testing. Unit tests check specific inputs. A type checker verifies a structural property of all inputs simultaneously. Mathematical proof is to theorem what type checking is to correctness.
Recall from ch004 (Mathematical Curiosity and Exploration): we tested that sum_of_cubes held for 500 random cases. This chapter explains how to move from that evidence to a proof.
# --- Visualization: Four proof strategies ---
import matplotlib.pyplot as plt
import matplotlib.patches as mpatches
plt.style.use('seaborn-v0_8-whitegrid')
fig, ax = plt.subplots(figsize=(13, 6))
ax.set_xlim(0, 13); ax.set_ylim(0, 6)
ax.axis('off')
def box(ax, x, y, w, h, text, color='steelblue', fontsize=9):
rect = mpatches.FancyBboxPatch((x, y), w, h, boxstyle='round,pad=0.1',
facecolor=color, edgecolor='black', alpha=0.85)
ax.add_patch(rect)
ax.text(x+w/2, y+h/2, text, ha='center', va='center',
fontsize=fontsize, fontweight='bold', color='white', multialignment='center')
box(ax, 4.5, 5.2, 4.0, 0.7, 'Goal: Prove P implies Q', color='#2c3e50', fontsize=11)
strategies = [
(0.2, 3.5, 2.8, 1.1, 'Direct Proof\nAssume P.\nDerive Q directly.', '#2980b9'),
(3.3, 3.5, 2.8, 1.1, 'Contrapositive\nAssume NOT-Q.\nDerive NOT-P.', '#27ae60'),
(6.4, 3.5, 2.8, 1.1, 'Contradiction\nAssume P AND NOT-Q.\nDerive false.', '#8e44ad'),
(9.5, 3.5, 2.8, 1.1, 'Induction\nBase: P(1).\nStep: P(k) -> P(k+1).', '#e67e22'),
]
for x,y,w,h,txt,col in strategies:
box(ax, x, y, w, h, txt, color=col)
ax.annotate('', xy=(x+w/2, y+h), xytext=(6.5, 5.2),
arrowprops=dict(arrowstyle='->', color='black', lw=1.5))
examples = [
(0.2, 1.8, 2.8, 1.0, 'Example:\nsqrt(2) irrational\n(algebra)', '#d6eaf8'),
(3.3, 1.8, 2.8, 1.0, 'Example:\nPrime > 2 is odd\n(contrapositive)', '#d5f5e3'),
(6.4, 1.8, 2.8, 1.0, 'Example:\nInfinitely many primes\n(contradiction)', '#e8daef'),
(9.5, 1.8, 2.8, 1.0, 'Example:\nSum formula\n(induction)', '#fde8d8'),
]
for x,y,w,h,txt,col in examples:
box(ax, x, y, w, h, txt, color=col, fontsize=8)
ax.set_title('Mathematical Proof Strategies', fontsize=13, pad=10)
plt.tight_layout()
plt.show()4. Mathematical Formulation¶
Mathematical induction:
To prove P(n) for all n >= 1:
Base case: Prove P(1).
Inductive step: Assume P(k). Prove P(k+1).
Conclusion: P(n) holds for all n >= 1.
Example: Prove sum_{k=1}^n k = n(n+1)/2.
Base: n=1: sum=1, formula=1. Matches.
Step: Assume sum_{k=1}^m k = m(m+1)/2. Then:
sum_{k=1}^{m+1} k = m(m+1)/2 + (m+1) = (m+1)(m+2)/2. This is the formula for m+1. QED.
# --- Implementation: Inductive proof verifier ---
import numpy as np
def verify_identity(summand, closed_form, n_range, name):
"""Verify sum_{k=1}^n summand(k) == closed_form(n) for all n in n_range."""
print(f"Verifying: {name}")
failures = []
for n in n_range:
lhs = sum(summand(k) for k in range(1, n+1))
rhs = closed_form(n)
if abs(lhs - rhs) > 1e-9:
failures.append((n, lhs, rhs))
if failures:
print(f" FAILS: {failures[:3]}")
else:
print(f" VERIFIED for n=1..{max(n_range)}")
return len(failures) == 0
identities = [
('Sum of integers: k = n(n+1)/2',
lambda k: k, lambda n: n*(n+1)//2),
('Sum of squares: k^2 = n(n+1)(2n+1)/6',
lambda k: k**2, lambda n: n*(n+1)*(2*n+1)//6),
('Sum of cubes: k^3 = [n(n+1)/2]^2',
lambda k: k**3, lambda n: (n*(n+1)//2)**2),
('Geometric series: 2^(k-1) = 2^n - 1',
lambda k: 2**(k-1), lambda n: 2**n - 1),
]
for name, f, g in identities:
verify_identity(f, g, range(1, 201), name)Verifying: Sum of integers: k = n(n+1)/2
VERIFIED for n=1..200
Verifying: Sum of squares: k^2 = n(n+1)(2n+1)/6
VERIFIED for n=1..200
Verifying: Sum of cubes: k^3 = [n(n+1)/2]^2
VERIFIED for n=1..200
Verifying: Geometric series: 2^(k-1) = 2^n - 1
VERIFIED for n=1..200
# --- Experiment: Discovering closed forms by polynomial fitting ---
import numpy as np
def discover_closed_form(summand_fn, max_degree=5, n_points=30):
ns = np.arange(1, n_points+1)
sums = np.array([sum(summand_fn(k) for k in range(1, n+1)) for n in ns])
for degree in range(1, max_degree+1):
coeffs = np.polyfit(ns, sums, degree)
predicted = np.polyval(coeffs, ns)
if np.max(np.abs(sums - predicted)) < 1e-6:
terms = []
for i, c in enumerate(coeffs):
power = degree - i
c_r = round(c, 4)
if abs(c_r) > 1e-6:
if power == 0: terms.append(f'{c_r:+g}')
elif power == 1: terms.append(f'{c_r:+g}n')
else: terms.append(f'{c_r:+g}n^{power}')
return degree, ' '.join(terms)
return None, 'not found'
print("Discovering closed forms by polynomial fitting:")
for name, fn in [
('Sum k', lambda k: k),
('Sum k^2', lambda k: k**2),
('Sum k^3', lambda k: k**3),
('Sum (2k-1)', lambda k: 2*k-1),
('Sum k(k+1)', lambda k: k*(k+1)),
]:
deg, formula = discover_closed_form(fn)
print(f" {name:<15} -> degree {deg}: S(n) = {formula}")Discovering closed forms by polynomial fitting:
Sum k -> degree 2: S(n) = +0.5n^2 +0.5n
Sum k^2 -> degree 3: S(n) = +0.3333n^3 +0.5n^2 +0.1667n
Sum k^3 -> degree 4: S(n) = +0.25n^4 +0.5n^3 +0.25n^2
Sum (2k-1) -> degree 2: S(n) = +1n^2
Sum k(k+1) -> degree 3: S(n) = +0.3333n^3 +1n^2 +0.6667n
7. Exercises¶
Easy 1. Verify by induction that sum_{k=1}^n (2k-1) = n^2 for n=1 to 50. Write the algebraic inductive step in a comment, then confirm with code.
Easy 2. Use discover_closed_form on sum_{k=1}^n k^4. What polynomial does it find?
Medium 1. Write a direct proof (in markdown cells) that the square of an even integer is divisible by 4. Then verify the contrapositive computationally for all integers -100 to 100.
Medium 2. Proof by contradiction: the product of first k primes plus 1 is not divisible by any of those k primes. Verify this for k=1..15 by computing the product, adding 1, and checking divisibility.
Hard. Strong induction: prove every integer n >= 2 has a prime factorization. Write the proof sketch, then verify computationally: for every n from 2 to 10000, factor n using trial division and confirm all factors are prime.
# --- Mini Project: Proof structure recorder ---
class ProofStep:
def __init__(self, statement, justification, check_fn=None):
self.statement = statement
self.justification = justification
self.check_fn = check_fn
def verify(self):
if self.check_fn is None: return True, 'assumed'
try: return bool(self.check_fn()), 'computed'
except Exception as e: return False, str(e)
class Proof:
def __init__(self, theorem, strategy):
self.theorem = theorem; self.strategy = strategy; self.steps = []
def add_step(self, statement, justification, check_fn=None):
self.steps.append(ProofStep(statement, justification, check_fn)); return self
def verify(self):
print(f"Theorem: {self.theorem}")
print(f"Strategy: {self.strategy}\n")
all_ok = True
for i, step in enumerate(self.steps, 1):
ok, method = step.verify()
status = 'OK' if ok else 'FAIL'
print(f" Step {i} [{method}]: {status}")
print(f" {step.statement}")
print(f" Justification: {step.justification}")
if not ok: all_ok = False
print(f"\nProof {'verified' if all_ok else 'HAS ERRORS'}: {self.theorem}")
return all_ok
proof = Proof("For all n >= 1: sum(k, k=1..n) = n(n+1)/2", "Mathematical induction")
proof.add_step("Base n=1: LHS=1, RHS=1*(1+1)/2=1.", "Direct computation",
lambda: sum(range(1,2)) == 1*(1+1)//2)
proof.add_step("Inductive hypothesis: assume sum(k, k=1..m) = m(m+1)/2.", "Assumption", None)
proof.add_step("Step: sum(k=1..m+1) = m(m+1)/2 + (m+1) = (m+1)(m+2)/2.", "Algebra",
lambda: all(sum(range(1,m+2)) == (m+1)*(m+2)//2 for m in range(1, 100)))
proof.add_step("By induction, formula holds for all n >= 1.", "Principle of induction",
lambda: all(sum(range(1,n+1)) == n*(n+1)//2 for n in range(1, 201)))
proof.verify()Theorem: For all n >= 1: sum(k, k=1..n) = n(n+1)/2
Strategy: Mathematical induction
Step 1 [computed]: OK
Base n=1: LHS=1, RHS=1*(1+1)/2=1.
Justification: Direct computation
Step 2 [assumed]: OK
Inductive hypothesis: assume sum(k, k=1..m) = m(m+1)/2.
Justification: Assumption
Step 3 [computed]: OK
Step: sum(k=1..m+1) = m(m+1)/2 + (m+1) = (m+1)(m+2)/2.
Justification: Algebra
Step 4 [computed]: OK
By induction, formula holds for all n >= 1.
Justification: Principle of induction
Proof verified: For all n >= 1: sum(k, k=1..n) = n(n+1)/2
True9. Chapter Summary & Connections¶
A proof certifies a statement for all cases -- not just tested ones; categorically different from computational verification
Four main strategies: direct, contrapositive, contradiction, induction
Induction is the most computationally tractable: both base case and step can be verified by code
Polynomial fitting of partial sums is a practical technique for discovering closed forms to prove inductively
Forward: Inductive proofs reappear throughout the book. The closed-form sum identities here appear in ch154 -- Matrix Multiplication. The contradiction proof technique is used in ch025 -- Irrational Numbers to prove sqrt(2) is irrational.
Backward: This chapter operationalizes conditional structure from ch014 (Conditional Statements and Logic). The conjecture-testing from ch004 (Mathematical Curiosity and Exploration) becomes the empirical prelude to formal proof.