Proof by Induction, Contradiction, and Counterexample

Proof by induction

To prove P(n) for all integers n ≥ 1:

1. Basis: show P(1) is true.
2. Assumption: assume P(k) is true for some k ≥ 1.
3. Inductive step: show that P(k) implies P(k + 1).
4. Conclusion: since P(1) is true and P(k) ⇒ P(k + 1), P(n) is true for all n ≥ 1 by induction.

Example. Prove 1 + 2 + ... + n = n(n + 1)/2.

• n = 1: 1 = 1(2)/2. ✓
• Assume 1 + ... + k = k(k + 1)/2.
• Then 1 + ... + k + (k + 1) = k(k + 1)/2 + (k + 1) = (k + 1)(k + 2)/2, which is P(k + 1).

Induction also proves divisibility (for example 7ⁿ − 1 is divisible by 6) and derivative formulas.

Proof by contradiction

Assume the statement is false and show this leads to an impossibility.

Example. √2 is irrational. Suppose √2 = p/q in lowest terms. Then p² = 2q², so p is even; write p = 2m, then q² = 2m², so q is even too. Both even contradicts lowest terms.

Counterexample

One example where the statement fails disproves it. All primes are odd is false: 2.

Quick summary

• Induction: basis, assumption, step, conclusion (write the conclusion sentence).
• Contradiction: assume the opposite, reach an impossibility.
• One counterexample disproves a universal statement.