Proof by Mathematical Induction

Why do we need a special proof technique for "all natural numbers"? Because the natural numbers are infinite: you cannot check $P(0), P(1), P(2), \ldots$ one by one. Mathematical induction turns that infinite checklist into two finite tasks. Picture an unending row of dominoes. Show the first domino falls. Show that whenever one domino falls it knocks over the next. Together, every domino falls — no matter how far down the line you look. The principle is so basic that programmers, combinatorialists, and theorem provers reach for it before any other tool. Whenever a statement is indexed by $n$ and one case clearly leads to the next, induction is the natural weapon.

The principle, stated precisely

Mathematical induction proves $\forall n \geq n_0,;P(n)$ by establishing two facts:

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

The assumption "$P(k)$ is true" inside the inductive step is the inductive hypothesis. You are not assuming what you want to prove; you are proving the implication $P(k) \Rightarrow P(k+1)$. The principle is justified by the well-ordering principle: every non-empty subset of $\mathbb{N}$ has a least element. If some $P(n)$ failed, the smallest such $n$ would either contradict the base case or contradict the inductive step.

The domino model

The two halves are necessary and sufficient. Knock down the first domino and the cascade begins. Place the dominoes close enough together (the inductive step) and the cascade never stops. Remove either ingredient and the chain breaks. The widget below makes this concrete: you can toggle the base case off, snap any link, and watch where the cascade halts.

A worked example

Prove that $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$ for all $n \geq 1$.

Base ($n = 1$): $\sum_{i=1}^{1} i = 1 = \frac{1 \cdot 2}{2}$. $\checkmark$

Inductive step: fix $k \geq 1$ and assume $\sum_{i=1}^{k} i = \frac{k(k+1)}{2}$ (inductive hypothesis). Add $k+1$ to both sides:

That is the formula with $n = k+1$. By induction the identity holds for every $n \geq 1$. $\blacksquare$

Pause and think: in the inductive step you write "assume $P(k)$." A beginner often objects — aren't we just assuming what we want? Why is that not circular? (Hint: look carefully at what is being proved — an implication, not the conclusion $P(k+1)$ standing alone.)

Try it

• Before stepping the widget: predict the value of $\sum_{k=1}^{n} k$ at $n = 10$ using the closed form. Now step the widget to $n = 10$ and check.
• Toggle the base case off in the widget, press play, and confirm the cascade never starts. Use this to explain in one sentence why the base case is essential.
• Break the link at $k = 4$. Predict how many dominoes fall before play. Run it and count.
• Write out, on paper, the base case for $\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$ at $n = 1$. Verify by hand.

A trap to watch for

Three induction traps catch almost every beginner. (1) Forgetting the base case. If the inductive step works but $P(n_0)$ was never checked, the chain has no first domino. The classic counterexample: "all positive integers are greater than $10^{100}$." The inductive step $k > 10^{100} \Rightarrow k+1 > 10^{100}$ is correct, yet the conclusion is absurd. (2) Assuming $P(k+1)$ to prove $P(k+1)$ — the dreaded circular argument. You may only assume $P(k)$. (3) Reading $P(k) \Rightarrow P(k+1)$ as "$P(k)$ and $P(k+1)$ are both true." The inductive step is a conditional, not a joint assertion. Spot the conditional and you keep the proof rigorous.

What you now know

You can state the principle of mathematical induction, identify the base case and inductive step of any induction proof, and write a complete induction proof for a simple summation identity. In the next section you will see induction applied beyond summations — to divisibility, inequalities, and product formulas — and in §6.4 you will meet a sharper version, strong induction, that lets you reach back to all previous cases at once.

References

• Velleman, D. J. (2019). How to Prove It: A Structured Approach (3rd ed.). Cambridge University Press, §6.1.
• Knuth, D. E. (1997). The Art of Computer Programming, Vol. 1: Fundamental Algorithms (3rd ed.). Addison-Wesley, §1.2.1.
• Graham, R. L., Knuth, D. E., Patashnik, O. (1994). Concrete Mathematics (2nd ed.). Addison-Wesley, ch. 1.
• Hammack, R. H. (2018). Book of Proof (3rd ed.). Virginia Commonwealth University, ch. 10.
• Aigner, M., Ziegler, G. M. (2018). Proofs from THE BOOK (6th ed.). Springer.