The First Principle of Induction

In one sentence

To prove that a whole sequence of statements $P(1),P(2),P(3),\dots$ is all true, you only need two things:

1. Base case: check that $P(1)$ is true. This knocks over the first domino.
2. Inductive step: assume $P(k)$ is true (the induction hypothesis) and use it to prove $P(k+1)$. This shows that every falling domino knocks over the next one.

Do both and $P(n)$ holds for every positive integer $n$. This is the first principle of mathematical induction. It rests on a basic property of the positive integers (the axiom of induction): a set of positive integers that contains $1$, and that contains $n+1$ whenever it contains $n$, is the set of all positive integers.

Notice that step 2 proves an implication, “if $P(k)$, then $P(k+1)$”, not $P(k+1)$ itself. We do not need to know whether domino $k$ has fallen yet. We only need to be sure that if it falls, the next one falls too.

Induction does not have to start at $1$. A base case at $n_0$ and an inductive step for $k\ge n_0$ give the conclusion “true for every $n\ge n_0$”.

Stop 1 · Divisibility

For every positive integer $n$, $3\mid n^3+2n$.

Stop 2 · Counting

A set with $n$ elements has exactly $2^n$ subsets. Here the inductive step is a construction: going from $k$ elements to $k+1$, how do the subsets multiply?

“Add one new element and see what it adds” is the most common kind of inductive step in combinatorics.

Stop 3 · Inequalities: match the base case to the step

Bernoulli's inequality: if $x>-1$, then $(1+x{)}^n\ge 1+nx$ for every positive integer $n$.

Without $x>-1$, the second step might multiply by a negative number and flip the inequality: the chain breaks right there. Take $x=-3$. For $n=3$: $(1-3{)}^3=-8$ and $1+3\cdot (-3)=-8$, still equal. For $n=2$: $(-2{)}^2=4\ge -5$, also fine. But for $x=-3$, $n=5$: $(-2{)}^5=-32<1-15=-14$, and the inequality is false.

If the first domino is not pushed

Practice