Through many births I have wandered on and on,
Searching for, but never finding, the builder of this house.Siddhārtha Gautama
While doing the coursera course Introduction to Mathematical Thinking I was exposed to the following proof, which is the first I’ve understood fully. The argument is elegant and, as it turns out, over 2000 years old! Euclid’s Elements first outlines this proof.
Theorem: Every natural number greater than 1 is either prime or a product of primes (composite).
Proof: Using a proof of induction, starting from n = 2
The base step, for n = 2:
For the induction step, we must assume the precedent and deduce the antecedent.
The theorem follows by induction
- Which proofs do you consider beautiful?
- What did you think was proved but learned isn’t?
- Which proofs are you currently trying to grasp?