Strong-Induction Sten
STRONG INDUCTION — assume the claim holds for *all* values up to k (not just k), then prove it for k+1. The induction that gets to use everything already proved.
A story read by Strong-Induction Sten
Press play to listen along. The line being read lights up as you go.
Show full transcript
Loading transcript…
Strong-Induction Sten is, as the chapter title suggests, the kind of person who inherits things.
He inherited his nose from his father. He inherited his height from his mother. He inherited his love of festival biscuits from his grandfather. He inherited his belief that you should use everything you already have from a series of older cousins who pointed out, repeatedly, throughout his childhood, that there was a perfectly good library at the end of the street.
This is a chapter about why Sten became the kind of mathematician he is.
Sten was, as the previous chapter mentioned, three years younger than his sister Ida. He grew up in the same town (Lattice), in the same family (Latticeford), in the same domino-festival tradition. He helped set up the Cascade every year. He pushed the first domino at fifteen, which was a great honour, and he too watched the whole chain fall, and he too noticed that he had only pushed one piece.
He thought: Yes. I see why Ida likes this.
But Sten also noticed, that day and other days, that his sister's domino technique had a particular shape. She only used the previous one. She knocked down domino k, and domino k knocked down domino k+1, and the rest happened by itself.
Sten thought, watching her work: That's fine. But what about the dominoes she already knocked down?
This will sound like a small thought. It was not small.
What Sten realised — and he realised it slowly, over the course of several years — was that when you are proving things about, say, the natural numbers, by the time you are trying to prove the case for n=10, you have already proved n=1, n=2, n=3, ..., n=9. They are already established. You are allowed to use them. All of them.
Ida's technique used the previous one. Sten thought: Why not use all of them?
He brought this up at the dinner table when he was sixteen.
Ida (who was nineteen and home from her first year at the academy) said: "You can. It's allowed. It's just a different version of the technique. It's called strong induction."
Sten said: "How is that different?"
Ida said: "In ordinary induction, you only assume the case for k. In strong induction, you assume the cases for everything up to k. It's still valid. Some proofs need it. Most don't."
Sten said: "Why would anyone NOT use the strong version?"
Ida said: "Because it isn't always necessary."
Sten said: "It isn't always necessary, but it's never wrong. So I'd just use it."
Ida said: "You're allowed to. Most mathematicians don't, because it feels heavier."
Sten said: "It only feels heavier."
Their mother (who was excellent at deflecting domino arguments at the dinner table) suggested they pass the bread.
Sten went on to study mathematics, like his sister. He arrived at the ProofQuest academy three years after Ida did. He introduced himself by saying, "Hello. I am the dominoes-but-also-everything-already-fallen person." The academy master said, "Oh. We have your sister. Are you also the dominoes person?" Sten said, "Yes. But I assume more." The academy master, who had been at the academy for a long time, immediately understood and hired him.
Sten teaches strong induction. He is the cast member who, when proving something about case k+1, gets to use every previously-proven case. This is occasionally exactly what a proof requires. There are theorems — about the structure of prime numbers, about the depth of certain trees, about the way certain recursive algorithms terminate — that cannot be proved by ordinary induction at all. They need strong induction. Sten teaches all of them.
He is, in person, mildly relaxed. He says "obviously" a lot, which is sometimes annoying but is usually accurate. He believes — and has said, more than once, in front of his sister — that strong induction is just induction, but with more friends in the room.
Ida finds this analogy slightly grumpy.
She finds it more grumpy because it is correct.
Sten and Ida are very close. They write letters when they are at different academies. (Sten now teaches at the southern branch; Ida at the central.) Their letters are warm and full of next case discussions. They send each other interesting recursion problems. They argue about whose technique is more elegant (Ida says ordinary; Sten says strong; neither has changed her or his mind). Their mother, who is now seventy-two and still runs the family domino business in Lattice, considers this argument the only thing her children ever fight about.
At the next Cascade festival, both of them will be home. They will set up their share of the chain — Ida's careful, Sten's slightly faster — and they will help the youngest cousin push the first domino, and they will watch the chain fall, and afterward they will go to the bakery and eat festival biscuits and continue arguing about which kind of induction is the real one.
Their mother has, by now, learned to bring earplugs.
The ProofQuest ensemble
Strong-Induction Sten is part of ProofQuest's distributed-narrative cast. Each character embodies a different curricular primitive; together they teach the full subject.
-
Direct-Proof Dora
Direct proof: assume premises, derive conclusion by straightforward logical steps
-
Induction Ida
Weak / standard mathematical induction: base case + inductive step
-
Contradiction Cassius
Proof by contradiction (reductio ad absurdum): assume the negation, derive a contradiction
-
Construction Cole
Proof by construction: prove existence by explicit construction of an example
-
Pigeonhole Perch
Pigeonhole principle: if n+1 items are placed in n bins, at least one bin contains 2+ items
-
Exhaustion Edda
Proof by exhaustion / cases: enumerate every case and verify each
-
Counterexample Cricket
Disproof by counterexample — one exception topples a universal claim
-
Biconditional Bex
Biconditional proof — proving 'if and only if' in both directions
-
Uniqueness Una
Proof of uniqueness — suppose two, show they must be the same one
-
QED
Closing-mark mentor — the ∎ at the end of every proof; the gentle voice that names completion + invites the next problem