A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
Mathematical induction is a proof technique for statements about all natural numbers (or all integers from some starting point). It works in two steps. The base case verifies the statement for the first value (usually n = 1 or n = 0). The inductive step proves that if the statement holds for any integer k, then it also holds for k + 1. Together, these two steps create a chain reaction: the base case triggers k = 1 → k = 2 → k = 3 → ... , covering every natural number. Despite its name, mathematical induction is a deductive proof technique — it proves the statement with certainty for all cases.
Use the domino analogy: if the first domino falls (base case) and each domino knocks down the next (inductive step), then all dominoes fall. Then work through a concrete proof: prove 1 + 2 + 3 + ... + n = n(n+1)/2. Base case: n = 1, 1 = 1(2)/2 = 1. Inductive step: assume the formula holds for k, then show it holds for k + 1 by adding (k+1) to both sides. Have students write the proof themselves before seeing the full version.
Imagine an infinite line of dominoes. You know two things: the first domino falls, and every domino, when it falls, knocks down the one after it. From these two facts, you can conclude that every domino in the line will fall. Mathematical induction works exactly like this — it proves a statement for every natural number by establishing a base case (the first domino) and an inductive step (each domino triggers the next).
The base case is straightforward: verify that the statement is true for the starting value, usually n = 1. For example, if you want to prove that 1 + 2 + ... + n = n(n+1)/2 for all n ≥ 1, the base case checks n = 1: the left side is 1, the right side is 1(2)/2 = 1. They match, so the base case holds.
The inductive step is the heart of the proof. You assume the statement is true for some arbitrary integer k (this assumption is called the inductive hypothesis), and then you prove it must also be true for k + 1. For the sum formula: assume 1 + 2 + ... + k = k(k+1)/2. Now add (k+1) to both sides. The left side becomes 1 + 2 + ... + k + (k+1). The right side becomes k(k+1)/2 + (k+1) = k(k+1)/2 + 2(k+1)/2 = (k+1)(k+2)/2. This is exactly the formula with n = k + 1. The inductive step is complete.
Students often feel uneasy about the inductive hypothesis: "Aren't we assuming what we want to prove?" No — and this is crucial. You are not assuming the statement is true for all n. You are assuming it for one particular k and proving it for k + 1. The base case establishes truth at n = 1. The inductive step then extends it: since it is true for 1, it must be true for 2 (by the inductive step with k = 1). Since it is true for 2, it must be true for 3 (with k = 2). And so on, forever. The chain of implications is valid because each link is proven, and the chain starts from a proven base case.
One important note about naming: despite the word "induction," mathematical induction is a deductive proof technique. It proves a statement with absolute certainty for all natural numbers. This contrasts with inductive reasoning (observing 1 + 3 = 4, 1 + 3 + 5 = 9, 1 + 3 + 5 + 7 = 16 and guessing the pattern is n²), which provides evidence but not proof. Inductive reasoning helps you discover the conjecture; mathematical induction proves it.