Medium

The Principle of Mathematical Induction

Simple Explanation

To prove a statement P(n) is true for every integer n from some starting value onward, mathematical induction uses two steps: the BASE CASE, showing P(1) (or the actual starting value) is true directly, and the INDUCTIVE STEP, assuming P(k) is true for some arbitrary k (the "inductive hypothesis"), then using that assumption to prove P(k+1) is also true. If both steps succeed, P(n) is true for every n in the range.

Why Do We Need It?

Induction is the standard, rigorous way to prove a statement about every positive integer — there are infinitely many of them, so checking each one individually is simply impossible.

Formula

The Principle of Mathematical Induction

If P(1) is true, and P(k) true ⟹ P(k+1) true for every k, then P(n) is true for all n ≥ 1

A two-step method for proving a statement P(n) holds for every integer n from some starting value onward, without checking each one individually.

P(n): — the mathematical statement being proved, depending on the integer n
Base case: — the direct verification that P(1) (or the actual starting value) is true
Inductive step: — proving that IF P(k) is true, THEN P(k+1) must also be true

When to use it: Whenever a statement needs to be proved true for every integer in an infinite range, not just checked for a handful of examples.

Worked Example

Prove a simple inequality using induction

Prove that n < 2ⁿ for all positive integers n ≥ 1, using mathematical induction.

Why Does This Work?

This is often explained with a domino analogy: the base case is knocking over the very first domino, and the inductive step is the guarantee that "if any domino falls, it knocks over the next one." Together, these two facts guarantee every single domino in the entire line falls, no matter how long the line is — exactly mirroring how the two steps guarantee P(n) for every n.

Real-Life Example

Verifying a computer algorithm works for any input size

A computer scientist needs to prove an algorithm produces the correct result no matter how large the input size n is, not just for the few sizes that were tested.

Mathematical induction is exactly the tool used to rigorously prove such a claim holds for every possible input size, not merely the ones checked by hand.

Practice

What are the two required steps of a mathematical induction proof?

Medium

Common mistake

Skipping the base case, or not explicitly stating the inductive hypothesis (assuming P(k) is true) before trying to prove P(k+1) — both steps are required, and the inductive step must clearly make use of that assumption.

Quick Review

Base case: verify P(starting value) directly.
Inductive step: assume P(k) is true, then prove P(k+1) follows from it.
The domino analogy: the first domino falls, and each domino knocks over the next — so all of them fall.