证明的四种方式：直接、逆否、反证、归纳

Three proofs of three small claims.

DIRECT  --  "if a and b are even, then a+b is even."
  a even => a = 2m,  b even => b = 2n  (the hypothesis P).
  a + b = 2m + 2n = 2(m+n), which is 2 times an integer.
  Hence a+b is even = Q.  Done.

CONTRAPOSITIVE  --  "if n^2 is even, then n is even."
  Direct is awkward; prove the contrapositive: n odd => n^2 odd.
  n odd => n = 2k+1 => n^2 = 4k^2+4k+1 = 2(2k^2+2k)+1, odd.
  So (n^2 even) => (n even).  Done.

CONTRADICTION  --  "sqrt(2) is irrational."
  Suppose sqrt(2) = p/q in lowest terms (P and not-Q).
  Then 2q^2 = p^2, so p^2 is even, so p is even (claim above), p = 2r.
  Then 2q^2 = 4r^2, so q^2 = 2r^2, so q is even too.
  But p and q both even contradicts "lowest terms."
  Contradiction => sqrt(2) is irrational.  Done.

Induction proof:  1 + 2 + ... + n = n(n+1)/2  for all n >= 1.

BASE  n = 1:  left side = 1,  right side = 1*2/2 = 1.  Holds.

STEP  assume P(k):  1 + 2 + ... + k = k(k+1)/2.  (inductive hypothesis)
  Add the next term k+1 to both sides:
     1 + ... + k + (k+1) = k(k+1)/2 + (k+1)
                         = (k+1) * [ k/2 + 1 ]
                         = (k+1)(k+2)/2.
  That is exactly P(k+1).  So P(k) => P(k+1).

Base + step => P(n) holds for every n >= 1.  Done.


When the plain hypothesis is too weak: STRENGTHEN it.
Claim P(n):  1 + 1/4 + 1/9 + ... + 1/n^2  <  2.
The step stalls -- assuming sum < 2 does not control the new term.
Prove the STRONGER Q(n):  sum_{j=1}^n 1/j^2  <=  2 - 1/n.
  Base n=1: 1 <= 2 - 1 = 1. OK.
  Step: sum to k+1 <= (2 - 1/k) + 1/(k+1)^2.
     Since 1/(k+1)^2 < 1/(k(k+1)) = 1/k - 1/(k+1),
     the right side < 2 - 1/k + 1/k - 1/(k+1) = 2 - 1/(k+1).
  So Q(k) => Q(k+1). The bound 2 - 1/n < 2 gives the original P(n).