6.1 The Proof Toolkit

A proof is a finite chain of statements, each an axiom, a premise, or a consequence of earlier statements by a valid inference rule. For a claim of the form p → q:

Definitions used below: n is even iff n = 2k for some integer k; odd iff n = 2k + 1; rational iff n = a/b with integers a, b, b ≠ 0.

6.2 Worked Example 1 — Direct and Contrapositive

(a) Direct: if n is odd, then n^2 is odd. Let n = 2k + 1. Then n^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1, which is 2·(integer) + 1, hence odd. ∎

(b) Contrapositive: if 3n + 2 is odd, then n is odd. A direct attempt ("3n + 2 = 2k + 1, so n = (2k − 1)/3...") stalls. Instead prove the contrapositive: if n is even, then 3n + 2 is even. Let n = 2k. Then 3n + 2 = 6k + 2 = 2(3k + 1), even. ∎ The contrapositive is logically identical to the original claim — choosing it is a matter of algebraic convenience.

6.3 Worked Example 2 — Contradiction: √2 is Irrational

1. Suppose, for contradiction, √2 = a/b where a, b ∈ Z, b ≠ 0, and the fraction is in lowest terms (gcd(a, b) = 1).
2. Squaring: 2 = a^2/b^2, so a^2 = 2b^2. Thus a^2 is even, and since odd² is odd (proved in 6.2a), a is even: a = 2c.
3. Substitute: (2c)^2 = 2b^2 → 4c^2 = 2b^2 → b^2 = 2c^2. So b^2 is even, hence b is even.
4. Now 2 divides both a and b, contradicting gcd(a, b) = 1. The assumption was false, so √2 is irrational. ∎

The same skeleton proves there are infinitely many primes: assume p1, ..., pk are all of them, form N = p1·p2···pk + 1; no pi divides N (remainder 1), so N has a prime factor outside the list — contradiction.

6.4 Mathematical Induction

To prove ∀n ≥ n0: P(n):

1. Base case: verify P(n0).
2. Inductive step: assume P(k) for an arbitrary k ≥ n0 (inductive hypothesis, IH) and derive P(k + 1).

Worked proof (the classic sum): P(n): 1 + 2 + ... + n = n(n + 1)/2.

• Base (n = 1): LHS = 1, RHS = 1·2/2 = 1. ✔
• Step: assume 1 + ... + k = k(k + 1)/2. Then

1 + ... + k + (k + 1) = k(k + 1)/2 + (k + 1) = (k + 1)(k/2 + 1) = (k + 1)(k + 2)/2, which is P(k + 1). ∎

Worked proof (an inequality): P(n): 2^n < n! for all n ≥ 4.

• Base (n = 4): 2^4 = 16 < 24 = 4!. ✔
• Step: assume 2^k < k! with k ≥ 4. Then 2^(k+1) = 2·2^k < 2·k! < (k + 1)·k! = (k + 1)! (using 2 < k + 1 since k ≥ 4). ∎

6.5 Strong Induction

Strong induction lets the step use all earlier cases: assume P(n0), ..., P(k) to prove P(k + 1). It is equivalent in power to ordinary induction but often more natural.

Worked proof: every integer n ≥ 2 is a product of primes.

• Base (n = 2): 2 is itself prime. ✔
• Step: assume every integer from 2 through k is a product of primes. Consider k + 1. If k + 1 is prime, done. Otherwise k + 1 = a·b with 2 ≤ a, b ≤ k; by the strong IH both a and b are products of primes, so their product k + 1 is too. ∎ (Ordinary induction fails here: knowing only P(k) says nothing about the factors a and b.)

6.6 Common Mistakes & CS Applications

• Skipping the base case: the step for "n = n + 1 for all n" goes through vacuously; only the missing base stops the nonsense.
• Assuming what is to be proved (circular reasoning), or proving P(k + 1) → P(k) in the wrong direction.
• Proving a ∀-statement by checking three examples — examples never prove, they only disprove.
• Applications: induction is the standard tool for proving loop invariants (base = before the loop, step = one iteration preserves the invariant) and correctness of recursive algorithms (merge sort's proof is strong induction on array length); structural induction verifies properties of trees and grammars.

🎯 Exam Focus

1. Prove directly: the sum of two rational numbers is rational.
2. Prove by contrapositive: if n^2 is even, then n is even.
3. Prove by contradiction: there is no smallest positive rational number.
4. Prove by induction: 1^2 + 2^2 + ... + n^2 = n(n + 1)(2n + 1)/6 for all n ≥ 1.
5. Prove by induction: 6 divides n^3 − n for every integer n ≥ 0.
6. Using strong induction, show every amount of postage ≥ 12 rupees can be formed with 4-rupee and 5-rupee stamps.