The principle of induction

When we want to prove that a property $P(n)$ holds for all natural numbers $n\ge n_0$ we cannot check it one by one: the naturals are infinite. The principle of induction provides a two-step scheme that “closes” the proof in one stroke.

Theorem — Principle of mathematical induction

Let $P(n)$ be a statement defined for every $n\in\mathbb{N}$, $n\ge n_0$. If:

• (base) $P(n_0)$ is true;
• (inductive step) for every $k\ge n_0$, $P(k)\Rightarrow P(k+1)$,

then $P(n)$ is true for every $n\ge n_0$.

Links

Topics: Set theory
Concepts: Natural numbers · Principle of induction
Methods: Induction
Skills: Proving