Mathematical Induction: Principle Explained Simply

Mathematical induction is a method of proof used to show that a statement is true for every natural number: 1, 2, 3, and so on. It works like a line of falling dominoes — if you can knock down the first domino, and you can prove that any falling domino always knocks down the next one, then every domino in the line must eventually fall.

This matters because many facts in mathematics are claims about all numbers at once, such as the claim that 1 + 2 + … + n equals n(n+1)/2 for every natural number n. Checking a million cases never proves such a claim, but induction gives a complete and airtight proof in just two short steps.

Key Concepts

• Statement P(n): the claim being proved, written as a sentence that depends on the natural number n.
• Base case: the starting step — proving that P(1) (sometimes P(0)) is true by direct calculation.
• Inductive hypothesis: the assumption that P(k) is true for one particular but arbitrary natural number k.
• Inductive step: using the inductive hypothesis to prove that P(k + 1) must also be true.
• Principle of mathematical induction: if the base case holds and the inductive step holds, then P(n) is true for every natural number n.

How It Works

1. Write down the statement P(n) clearly so there is no ambiguity about what is being proved.
2. Prove the base case: substitute n = 1 (or the smallest relevant value) and check that both sides match.
3. Assume P(k) is true for some arbitrary natural number k. This assumption is the inductive hypothesis.
4. Starting from that assumption, prove P(k + 1). This usually means rewriting the (k + 1) case so the hypothesis can be used inside it.
5. Conclude: by the principle of mathematical induction, P(n) holds for all natural numbers n.

Worked Example

Prove P(n): 1 + 2 + … + n = n(n + 1)/2. Base case n = 1: left side 1, right side 1(2)/2 = 1 — they match, so P(1) holds. Assume P(k) is true: 1 + 2 + … + k = k(k + 1)/2. For n = k + 1, the left side is (1 + 2 + … + k) + (k + 1) = k(k + 1)/2 + (k + 1) = (k + 1)(k + 2)/2 by the hypothesis. The right side for n = k + 1 is exactly (k + 1)(k + 2)/2, so P(k + 1) is true. Hence, by induction, P(n) holds for every natural number n.

Common Misconceptions

• "The base case is optional." Wrong — without the base case the chain never starts. Both the base case and the inductive step are needed.
• "Induction assumes what it tries to prove." Wrong — we assume P(k) for one fixed k and then deduce P(k + 1). We never assume P(n) for all n at once.
• "Checking a few values proves the formula." Wrong — verifying n = 1, 2, 3 is only evidence. The inductive step is what covers every natural number.

Real-World Applications

• Proving closed-form formulas for sums of sequences, which are used in the analysis of algorithms.
• Proving divisibility facts, for example that 3^n − 1 is divisible by 2 for every n ≥ 1.
• Proving inequalities such as 2^n > n for all n ≥ 1.
• Verifying the correctness of recursive algorithms in computer science.

Induction compresses infinitely many claims into two steps: verify the first case, then show each case forces the next. Master the base case, the hypothesis, and the inductive step, and any pattern about natural numbers becomes provable.