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…

01 Opening
Strong-Induction Sten beat 1 of 5

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.

02 Strong-Induction Sten
Strong-Induction Sten beat 2 of 5

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?

03 Strong-Induction Sten
Strong-Induction Sten beat 3 of 5

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."

04 Strong-Induction Sten
Strong-Induction Sten beat 4 of 5

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.

05 Closing
Strong-Induction Sten beat 5 of 5

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.