Induction

The domino principle, made rigorous

You want to prove $P(n)$ is true for every natural number $n \ge 1$ (or $\ge 0$). Induction says you only need two things:

1. Base case. Prove $P(1)$ — the first domino falls.
2. Inductive step. Prove that for every $k$, if $P(k)$ holds then $P(k+1)$ holds — each domino knocks over the next.

If you establish both, the principle of mathematical induction guarantees $P(n)$ holds for all $n \ge 1$. Why? Because $P(1)$ is true (base case), and the step carries it forward: $P(1) \Rightarrow P(2) \Rightarrow P(3) \Rightarrow \cdots$, reaching every natural number in finitely many hops. The reasoning bottoms out in the successor structure of $\mathbb{N}$ from the very first lesson — every natural is $0$ wearing finitely many $S$'s, so induction catches every one of them.

The two parts are a package deal. The base case alone proves one thing, exactly one thing. The step alone proves "if any domino falls, the rest do" — useless if none of them falls. Together they're infinity-conquering. Apart they're nothing. Worse than nothing, actually, because they look plausible.

Anatomy of the inductive step: the hypothesis is free loot

The inductive step is where everyone freezes, so slow down. You are proving an implication: "if $P(k)$, then $P(k+1)$." By everything you learned in Direct Proof, you prove an implication by assuming the hypothesis — here, assume $P(k)$ is true. That assumption has a name: the inductive hypothesis (IH).

Students panic: "isn't assuming $P(k)$ assuming what I'm trying to prove?!" No, and this confusion will haunt you if you don't kill it right now. You're not assuming $P(k+1)$, the thing you actually want. You're assuming $P(k)$ — one specific, earlier domino — and using it to reach the next one. The IH is free loot: a gift you get to spend, handed to you by the logic of implication. The whole art of the inductive step is finding where to spend it — algebraically connecting $P(k+1)$ back to $P(k)$ so the IH can do its work.

Worked: 1 + 2 + ⋯ + n = n(n+1)/2

Claim. For all $n \ge 1$: $\displaystyle 1 + 2 + \cdots + n = \frac{n(n+1)}{2}$.

Proof (by induction on $n$).

Base case ($n = 1$): The left side is $1$. The right side is $\frac{1 \cdot 2}{2} = 1$. Equal. ✓

Inductive step: Fix $k \ge 1$ and assume the IH: $1 + 2 + \cdots + k = \frac{k(k+1)}{2}$. We must show $P(k+1)$, i.e. $1 + 2 + \cdots + (k+1) = \frac{(k+1)(k+2)}{2}$.

Start from the left side of $P(k+1)$ and split off the last term to expose the IH: $\underbrace{1 + 2 + \cdots + k}_{\text{this is the IH}} + (k+1) = \frac{k(k+1)}{2} + (k+1).$ That substitution — replacing the first $k$ terms with $\frac{k(k+1)}{2}$ — is exactly where we spent the free loot. Now just algebra: $\frac{k(k+1)}{2} + (k+1) = \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2}.$ That's precisely the right side of $P(k+1)$. So $P(k) \Rightarrow P(k+1)$. By induction, the formula holds for all $n \ge 1$. $\blacksquare$

The Gauss story, for contrast. Legend has it a child Carl Friedrich Gauss, told to add $1$ through $100$, instantly answered $5050$. His teacher probably wanted to die. He paired the terms: $1 + 100 = 101$, $2 + 99 = 101$, …, $50$ pairs each summing to $101$, giving $50 \times 101 = 5050 = \frac{100 \cdot 101}{2}$. Same formula, totally different proof — pairing gives insight into why; induction gives a guarantee that it holds for every $n$. Keep both in your kit: insight finds the formula, induction certifies it.

Worked: the sum of the first n odd numbers is n²

Claim. For all $n \ge 1$: $1 + 3 + 5 + \cdots + (2n - 1) = n^2$.

Proof (by induction). Base ($n=1$): left side $= 1$, right side $= 1^2 = 1$. ✓

Step: Assume the IH: $1 + 3 + \cdots + (2k - 1) = k^2$. The $(k+1)$-th odd number is $2(k+1) - 1 = 2k + 1$. So $\underbrace{1 + 3 + \cdots + (2k-1)}_{\text{IH} = k^2} + (2k + 1) = k^2 + (2k + 1) = (k+1)^2.$ That's $P(k+1)$. By induction, the sum of the first $n$ odd numbers is $n^2$ for all $n \ge 1$. $\blacksquare$

Worked: a divisibility example — 6 divides n³ − n

Claim. For all $n \ge 0$: $6 \mid (n^3 - n)$.

Proof (by induction). Base ($n = 0$): $0^3 - 0 = 0$, and $6 \mid 0$. ✓

Step: Assume the IH: $6 \mid (k^3 - k)$, i.e. $k^3 - k = 6m$ for some integer $m$. Consider $(k+1)^3 - (k+1)$ and expand: $(k+1)^3 - (k+1) = (k^3 + 3k^2 + 3k + 1) - (k + 1) = (k^3 - k) + 3k^2 + 3k.$ The first chunk is $6m$ by the IH. For the rest, $3k^2 + 3k = 3k(k+1)$, and $k(k+1)$ is a product of two consecutive integers, hence even — so $3k(k+1)$ is divisible by $6$. Thus $(k+1)^3 - (k+1) = 6m + 3k(k+1) = 6m + 6t = 6(m + t)$ for some integer $t$, which is divisible by $6$. So $P(k) \Rightarrow P(k+1)$, and by induction $6 \mid (n^3 - n)$ for all $n \ge 0$. $\blacksquare$

The pattern in every inductive step is the same: carve $P(k+1)$ open until the $P(k)$ piece appears, slot in the IH, clean up. That is the entire goddamn technique. There is no secret beyond that.

Where induction fails: skip the base case and lose your mind

Both parts are mandatory, and skipping the base case produces disasters that are hilarious only if they're not yours. Behold the "all horses are the same color" non-theorem — a specimen I keep preserved in the lab as a warning:

Claim: in any group of $n$ horses, all are the same color. "Step": given $k+1$ horses, remove one — by IH the remaining $k$ match; put it back, remove a different one — those $k$ match too; overlap them and all $k+1$ match.

The inductive step looks fine for large $k$ — but it secretly fails at the very first transition, $k=1 \to k=2$: two horses, remove one (the other is "all the same color," trivially), remove the other — but the two groups of one don't overlap, so nothing forces the two horses to match. The chain never gets off the ground. A broken or missing base case means dominoes that never start falling — and you can "prove" any insane damn thing. Always nail the base case. This is not optional. This is not a style choice. Now go conquer some infinities.