Direct, contrapositive, contradiction
Most theorems are implications P ⇒ Q, and there are three standard ways to attack one. A direct [[ana-proof|proof]] assumes P and reasons forward to Q. A [[contrapositive|contrapositive]] proof instead proves ¬Q ⇒ ¬P, which is logically equivalent — pick it when ¬Q is easier to grasp than P. A proof by contradiction assumes P and ¬Q together and derives an impossibility, forcing Q. All three rest on the logic from Guide 1; choosing well is half the craft of [[rigor|rigor]].
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.
Mathematical induction
[[ana-mathematical-induction|Mathematical induction]] proves a statement P(n) for every natural number n at once. You verify two things: the base case P(0) (or P(1)), and the inductive step P(k) ⇒ P(k+1). Together they form an unbroken chain — base gives P(0), the step carries it to P(1), then P(2), and so on to every n. The assumption P(k) you use in the step is the inductive hypothesis; it is allowed precisely because the step is itself an implication.
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).That second example is a lesson worth keeping: sometimes a statement is too weak to prove by induction, and the cure is to prove something stronger, because the stronger inductive hypothesis gives the step more to work with. This counterintuitive move — strengthening the claim to make it provable — recurs throughout analysis, especially in estimates that lean on the [[role-of-inequalities|role of inequalities]] and the [[triangle-inequality|triangle inequality]].