Numbers & Functions · 7 Functions as Objects

7.5 The proof that works like iteration: induction

Let me pause the machines to talk about something bigger. You’ve now watched iteration several times: each step refers back to the one before. There is a way of proving things with exactly this shape, and it’s one of the most powerful tools in all of mathematics — proof by induction. With it you can prove statements about infinitely many cases at once.

First, a word about what a proof even is. In every other field you gather evidence and reach a conclusion that’s probably right. Mathematics is the one human activity where you can be certain. A proof is a chain of reasons so tight that no exception can slip through — not “very likely true,” but true, forever. You’ve already met one kind: the proof by contradiction that cracked √ 2 open.

Induction is the second great technique.

The domino picture. Imagine an infinite row of dominoes. Will all of them fall? You can’t check infinitely many. But you only need two things: 1. The first domino falls. (The base case.)

2. Each domino, if it falls, knocks over the next. (The inductive step.) If both hold, all the dominoes fall — the wave runs forever.

Let’s actually do one. If you add up the first n whole numbers, is there a shortcut? The claim: 1 + 2 + 3 + · · · + n = n(n + 1) 2 .

Base case (n = 1): left side is 1; right side is 1·2 2 = 1. They match. The first domino falls. ✓ Inductive step: suppose it’s true for n = k — assume 1 + 2 + · · · + k = k(k+1) 2 .

Look at the next case, n = k + 1, which is the same sum plus one more term: 1 + 2 + · · · + k | {z } assumed +(k+1) = k(k + 1) 2 +(k+1) = (k+1) k 2 + 1  = (k + 1)(k + 2) 2 .

And that is exactly the original formula with k + 1 in place of n. So if it holds at k, it’s forced to hold at k + 1. The domino at k knocks over the one at k + 1. ✓ Both facts established, the formula is true for every whole number n. We just proved infinitely many statements with six lines of algebra.

(There’s a lovely legend that Gauss discovered this sum as a child, when a teacher told the class to add 1 through 100 to keep them busy, and Gauss had the answer — 5050 — almost instantly. Check: 100·101 2 = 5050.)

All 8 chapters of Numbers & Functions · Foundations · All courses