Proof by induction and contradiction

Proof by induction proves a statement for every positive integer, like knocking over an infinite line of dominoes: show the first falls, and that each one knocks over the next.

Key facts

  • Base case: show it’s true for n = 1.
  • Assume it’s true for n = k.
  • Show it’s then true for n = k + 1.
  • Conclude it’s true for all n ≥ 1.
  • Other methods: contradiction (assume the opposite) and counterexample (to disprove).

Worked examples

Example 1

Prove that 1 + 2 + … + n = n(n + 1)/2.

  1. n = 1: both sides are 1.
  2. Assume 1 + … + k = k(k + 1)/2.
  3. Add k + 1: k(k + 1)/2 + (k + 1) = (k + 1)(k + 2)/2, the formula for n = k + 1.
  4. So it’s true for all positive integers n.

Answer: True for all n ≥ 1

Example 2

Prove that √2 is irrational.

  1. Suppose √2 = a/b in lowest terms. Then a² = 2b², so a is even: a = 2c.
  2. Then 4c² = 2b², so b² = 2c² and b is even too.
  3. But a/b was in lowest terms: contradiction. So √2 is irrational.

Answer: Contradiction