Principle of Mathematical Induction — The Statement

Many results in business mathematics and statistics — such as summation formulas or divisibility properties — are claimed to hold for every natural number $n$. Checking such a claim for a few values of $n$ is never a proof, because there could always be some larger $n$ where it fails. The Principle of Mathematical Induction (PMI) proves a statement for all natural numbers $n$ (from some starting point, usually $1$) using only two finite checks.

Let $P(n)$ be a statement involving the natural number $n$. The principle states:

1. Basis step. Show that $P(1)$ is true.
2. Inductive step. Assume $P(k)$ is true for some arbitrary natural number $k \geq 1$ (the inductive hypothesis), and use it to show that $P(k+1)$ must also be true.

If both steps are established, then $P(n)$ is true for every natural number $n \geq 1$.

Why this is a valid proof. The basis step establishes $P(1)$. The inductive step, applied with $k=1$, then guarantees $P(2)$; applied again with $k=2$, it guarantees $P(3)$; and so on indefinitely — like a row of dominoes where knocking over the first one, combined with the guarantee that every domino knocks over the next, topples the entire row, however long it is. …