Lecture · 15 min · advanced

Induction

The well-ordering principle in working clothes

Mathematical induction

Induction is not “it works for a few, so it works for all.” It is a two-step machine licensed by the well-ordering of the natural numbers: prove $P (1)$ (or $P (0)$ ), and prove that $P (k)$ implies $P (k + 1)$ . Then there is no smallest counterexample, hence no counterexample at all.

On the board today

—Write a complete induction proof with base and inductive step.
—See why the inductive hypothesis is an assumption, not a theft.
—Use induction for sums, inequalities, and divisibility.

The schema

P (1) and \forall k \geq 1 (P (k) \Rightarrow P (k + 1)) ⟹ \forall n \geq 1 P (n)

Worked example · The sum of the first $n$ integers

Prove $1 + 2 + \dots + n = \frac{n ( n + 1 )}{2}$ for every integer $n \geq 1$ .

1.Base: $n = 1$ gives $1 = 1$ .
2.Assume true for $k$ . Add $k + 1$ : $\frac{k ( k + 1 )}{2} + (k + 1) = \frac{( k + 1 ) ( k + 2 )}{2}$ .

The inductive step is algebra; the schema does the rest.

Pause the lecture

Where does an induction proof fail if the statement is false for $n = 1$ but true thereafter?

Common mistake. Using $P (k + 1)$ in the course of proving $P (k + 1)$ — circular. The inductive hypothesis is $P (k)$ , or, in strong induction, $P (1), \dots, P (k)$ . Not the thing you are currently proving.

Practice this lecture

Previous Next