Mathematical Induction

Suppose you want to prove that compounding at rate $r$ for $n$ years multiplies your money by $(1+r)^n$, for every whole number of years — not just the five or six you happened to check on a spreadsheet. Checking $n = 1, 2, 3, \dots$ one at a time never finishes; there is always another year to test. Mathematical induction is a way of proving a claim for every single positive integer using only two finite checks, no matter how large "every" turns out to be.

The analogy: a row of dominoes

Line up an infinite row of dominoes, one for each year, and imagine each domino carries a claim: "domino $n$" says "the formula is true for year $n$." You want every domino to fall. You do not need to push each one by hand — you need two things: the first domino falls when pushed, and the dominoes are spaced so that any falling domino knocks over the next one. Given both, the whole infinite row falls, one after another, forever. That is the entire logic of induction; the algebra below is just how you check those two conditions precisely.

Writing it down

Let $P(n)$ be a statement depending on a positive integer $n$ — for instance, "$1 + 2 + \cdots + n = \tfrac{n(n+1)}{2}$." Induction has two steps.

Base case. Show $P(1)$ is true directly — push the first domino and check it falls.

Inductive step. Assume $P(k)$ is true for some arbitrary $k$ (this assumption is called the inductive hypothesis — it is not something you're proving, it's a temporary "suppose"), and use that assumption to show $P(k+1)$ must also be true. In words: show that whichever domino falls, the next one falls too.

$$P(1) \text{ true} \quad \text{and} \quad \big(P(k) \text{ true} \implies P(k+1) \text{ true}\big) \quad \implies \quad P(n) \text{ true for all } n \geq 1 .$$

Read left to right: if the first case holds, and truth always carries forward one step, then it holds for every case. Nothing here requires checking $n = 2$, $n=3$, and so on by hand — the inductive step proves the pattern of carrying forward, once, for a generic $k$, and that single proof covers infinitely many transitions.

Worked example 1: the sum of the first n integers

Claim: $1 + 2 + \cdots + n = \tfrac{n(n+1)}{2}$.

Base case, $n=1$. Left side: just $1$. Right side: $\tfrac{1 \times 2}{2} = 1$. They match, so $P(1)$ holds.

Inductive step. Assume $P(k)$: $1 + 2 + \cdots + k = \tfrac{k(k+1)}{2}$. Now look at the sum for $k+1$: it is the sum up to $k$, plus one more term:

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

using the inductive hypothesis to replace the first $k$ terms. Factor out $(k+1)$: $\tfrac{k(k+1)}{2} + (k+1) = (k+1)\left(\tfrac{k}{2} + 1\right) = (k+1) \cdot \tfrac{k+2}{2} = \tfrac{(k+1)(k+2)}{2}$. That is exactly the formula with $n$ replaced by $k+1$, so $P(k+1)$ holds. The domino chain is complete: true for every $n \geq 1$.

Worked example 2: compounding grows by exactly $(1+r)^n$

Claim: after $n$ years of compounding at rate $r$, $1 becomes $(1+r)^n$.

Base case, $n=1$. After one year, $1 grows by a factor $(1+r)$, which is $(1+r)^1$. Matches.

Inductive step. Assume after $k$ years $1 has become $(1+r)^k$ (the inductive hypothesis). Year $k+1$ multiplies whatever you have by $(1+r)$ one more time: $(1+r)^k \times (1+r) = (1+r)^{k+1}$. That is the claim for $n = k+1$. So for every $n$, one dollar becomes $(1+r)^n$ — the formula compounding calculators use is not an approximation, it is a proven identity for every whole year.

What this means in practice

Induction is how you certify that a recursive algorithm terminates correctly for every input size, not just the sizes you tested — the same logic that justifies "if the loop invariant holds before the loop and each iteration preserves it, it holds after the loop." It is also how closed-form formulas for sums, compounding, and recurrence relations get proved rather than merely observed on a few examples.