Chapter 7 — Key Takeaways

Strong Induction, Well-Ordering, and Recursive Definitions — the one-page reference.

The three induction principles (all equivalent — §7.6)

Equivalence cycle: ordinary $\Rightarrow$ strong $\Rightarrow$ well-ordering $\Rightarrow$ ordinary. None is more powerful; "strong" = more convenient hypothesis, not more theorems.

Counting base cases — the #1 strong-induction error

Number of base cases = the largest reach of the inductive step.

If the step is only valid for $n \ge n_0 + j$, then $n_0, \dots, n_0+j-1$ must all be base cases.

Strong induction template

1. State $P(n)$.
2. Base cases: verify $P(n_0), \dots, P(n_0 + j)$ — one per step-reach.
3. Strong step: fix $k$; assume $P(n_0) \land \dots \land P(k)$; prove $P(k+1)$, using whichever earlier cases you need.
4. Conclude $P(n)$ for all $n \ge n_0$. $\blacksquare$

Well-ordering principle

Every non-empty subset of $\mathbb{N} = \{0,1,2,\dots\}$ has a least element.

• False for $\mathbb{Z}$ (no floor) and $\mathbb{Q}_{>0}$ (halve any candidate). A distinguishing property of $\mathbb{N}$.
• Requires non-empty.
• It is the bedrock under all induction and the basis of termination arguments (a strictly decreasing sequence of naturals must stop).

Smallest-counterexample pattern (= proof by contradiction): assume C = {n : P(n) false} ≠ ∅ → let m = min C (well-ordering) → m ≠ base (checked) → all j < m have P(j) → force P(m) ⇒ contradiction → C = ∅.

Recursive definitions

A recursively defined collection = three clauses:

Examples: - Fibonacci: basis $F_0=0, F_1=1$; recursive $F_n = F_{n-1}+F_{n-2}$. - Factorial: basis $0!=1$; recursive $n! = n\cdot(n-1)!$. - Lists: basis Nil; recursive Cons(x, L). - Full binary tree: basis = single leaf; recursive = root over two full subtrees.

⚠️ Drop the exclusion clause and the set could contain anything; "smallest" is what makes structural induction sound.

Structural induction

Prove $P$ for every element of a recursively defined set $S$:

• Valid because of the exclusion clause: every element is built in finitely many steps (it is ordinary induction on the number of build steps).
• One proof case per clause of the definition; it mirrors the code's branches (if base … else recurse).
• No counter "$n$" appears — induct on structure, not on a number.

Results proved this chapter (cite-ready)

Decision aid: which technique?

Does the step use only the ONE preceding case?      → ordinary induction
Does it use SEVERAL / ALL smaller cases?            → strong induction
                                                       (base cases = step's reach)
Is "take the smallest bad case" the natural move?   → well-ordering
                                                       (contradiction)
Are the objects built by a recursive DEFINITION
   (lists, trees, expressions, recursive sets)?     → structural induction
                                                       (one case per clause)

Common pitfalls

• Too few base cases. Reach back $j$ steps ⇒ need $j$ base cases. (Strong-induction analogue of the horses fallacy.)
• Forgetting the exclusion clause ("smallest set such that…") — breaks the validity of structural induction.
• Thinking "strong" = more powerful. It proves the same theorems; only the hypothesis is roomier.
• Inducting on "+1 node" for full binary trees — you can't add one node and stay full; induct on the clause instead.
• Well-ordering on the wrong set — it holds for $\mathbb{N}$, not $\mathbb{Z}$ or the positive rationals.

Toolkit additions (dmtoolkit/recurrences.py)

(Joins check_identity and fib from Ch. 6; module completed in Ch. 18–19.)