The Principle of Mathematical Induction

You want to prove a statement for infinitely many numbers. Direct verification will never finish, you cannot check $n = 1, 2, 3, \ldots$ forever. So mathematicians invented a clever shortcut: prove just two small things, and you get the entire infinite chain for free. That shortcut is induction, and the picture behind it is a row of dominoes.

The two halves

Let $P(n)$ stand for some statement about a positive integer $n$, for example, "$1 + 2 + \cdots + n = \frac{n(n+1)}{2}$". The principle of mathematical induction says: if you can prove both

• Base case: $P(1)$ is true, and
• Inductive step: for every $k \geq 1$, if $P(k)$ is true then $P(k+1)$ is true,

then $P(n)$ holds for every positive integer $n$. The base case is the first domino tipping over. The inductive step is the guarantee that each domino is close enough to the next to knock it down. Together: every domino falls.

What you really assume

The trickiest line in any induction proof is the inductive hypothesis. You write "assume $P(k)$ is true" and a beginner panics: am I just assuming what I want? No. You are assuming the statement holds for a fixed but arbitrary $k$, then proving the next case. That is a conditional, the implication "$P(k) \Rightarrow P(k+1)$", not the conclusion itself.

• Computer Science: Recursion and induction are duals: every recursive function with a base case and a smaller recursive call is implicitly using induction to guarantee correctness; merge sort, quicksort, and tree traversals all rely on this.
• Combinatorics: Counting arguments for binomial coefficients, Catalan numbers, and Stirling numbers are virtually always inductive: prove the identity for small $n$, then show the next case follows from the previous.
• Formal Verification: Coq, Lean, and Isabelle/HOL prove software-correctness theorems by structural induction; every verified cryptographic library (e.g., Project Everest) contains thousands of induction proofs.

(Press Start to release the first domino. Toggle the base case off and the chain never begins. Break the link at $k = 5$ and the cascade stops there. The algebra below the canvas walks through the same step on the identity $1 + 2 + \cdots + n = \frac{n(n+1)}{2}$.)

A worked proof

Prove $1 + 2 + \cdots + n = \frac{n(n+1)}{2}$ for all $n \geq 1$. Base: $n=1$ gives $1 = \frac{1 \cdot 2}{2} = 1$. True. Step: assume the identity for $k$, that is $1 + 2 + \cdots + k = \frac{k(k+1)}{2}$. Add $k+1$ to both sides:

$1 + 2 + \cdots + k + (k+1) = \frac{k(k+1)}{2} + (k+1) = \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2}.$

That is the identity with $n = k+1$. The implication holds, so the formula is true for every positive integer.

Strong induction

Sometimes proving $P(k+1)$ requires knowing not just $P(k)$ but several earlier values. Strong induction lets you assume $P(1), P(2), \ldots, P(k)$ all at once. It is logically equivalent to the ordinary form, but it is the natural fit for divisibility arguments and recursive definitions, for example, proving every integer $n \geq 2$ has a prime factorisation.

Try it

• Predict first: in an induction proof, if the base case is missing, does the inductive step alone prove anything? Use the stepper, toggle the base case off, press Start, and confirm nothing moves.
• Predict first: if the inductive step fails at exactly $k = 5$, how many dominoes will fall before the cascade stops? Break the link at $k = 5$ and confirm only the first few fall.
• On paper: verify the base case of $\sum_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}$