Day 32 — Strong induction & invariants
Day 32 — Strong induction & invariants
Stage III · concept day
Goal: Use strong induction; prove Fibonacci-style recurrences; solve postage stamp / Frobenius-lite problems; perform structural induction on lists and trees; apply the full loop-invariant pattern (init / maintain / terminate); sketch algorithm correctness without coding labs.
Why this matters
Weak induction assumes only the previous integer; many recurrences need all smaller values (Fibonacci, divide-and-conquer sizes, prime factor existence). Programs induct on structure (list tail, tree children) and on time (loop iterations). Loop invariants are how you prove while loops correct—the industry-adjacent face of induction.
Theory
Strong induction principle
Let \(P(n)\) be a predicate for \(n \ge n_0\).
If:
- Base: \(P(n_0)\) (sometimes several bases \(P(n_0),\ldots,P(n_0+r)\)), and
- Strong step: for every \(m \ge n_0\),
\(\bigl(\forall j\in\{n_0,\ldots,m\}\, P(j)\bigr) \rightarrow P(m+1)\)
(equivalently: assume all \(P(j)\) for \(n_0 \le j \le m\), prove \(P(m+1)\)),
then \(\forall n \ge n_0\, P(n)\).
Equivalent to weak induction in strength for \(\mathbb{N}\) (each can simulate the other), but form differs: you may use \(P(m), P(m-1), \ldots\) in the step.
When to use strong
- Recurrences \(a_{n} = a_{n-1} + a_{n-2}\).
- “Every \(n \ge 2\) has a prime factor.”
- Postage: amounts from some point onward using stamp denominations.
- Algorithms that reduce \(n\) to a strictly smaller instance not necessarily \(n-1\) (e.g. \(n//2\)).
Fibonacci example setup
\(F_0 = 0\), \(F_1 = 1\), \(F_{n} = F_{n-1}+F_{n-2}\) for \(n\ge 2\).
(Or \(F_1=F_2=1\)—fix your convention.)
Postage stamp / Frobenius lite
With stamps of sizes \(a,b\) coprime, all sufficiently large integers are postage-representable (Frobenius number \(ab-a-b\)). Course level: fix denominations (e.g. \(4\) and \(7\), or \(3\) and \(5\)) and prove by strong induction that all \(n \ge N\) work, with explicit bases.
Structural induction
Define a set of structures inductively, then prove \(\forall\) structures \(P\) by:
- Base structures (empty list, nil tree).
- Constructor step: if \(P\) holds for parts, then \(P\) holds for the compound.
Lists over \(X\): \(\mathrm{nil}\) | \(\mathrm{cons}(h,t)\).
Binary trees: \(\mathrm{Leaf}\) | \(\mathrm{Node}(L,v,R)\).
Examples: length laws, \(\mathrm{height}\), size \(= 1 + \mathrm{size}(L)+\mathrm{size}(R)\), inorder traversal length.
Loop invariants (full pattern)
For a loop with guard \(G\) and body \(B\):
- Initialization: \(I\) true before the loop.
- Maintenance: \(\{I \wedge G\}\; B\; \{I\}\) (if \(I\) and \(G\) hold, after \(B\), \(I\) holds).
- Termination: loop ends (e.g. variant decreases); then \(I \wedge \neg G\) holds.
- Use: \(I \wedge \neg G\) implies the desired postcondition.
Induction: \(P(t) =\) “after \(t\) successful iterations, \(I\) holds and any variant bounds.”
Algorithm correctness sketches (no labs)
- Linear search: invariant “\(x\) not in \(a[0..i)\)”; at end either found or not in array.
- Binary search (sorted): invariant “if \(x\) present, it lies in \(a[lo..hi]\)”; width decreases.
- Euclidean algorithm: invariant \(\gcd(a,b)=\gcd(a_0,b_0)\); \(b\) decreases.
State invariants in math; do not require running code.
Strong induction write-up tips
- State “assume \(P(j)\) for all \(j\) with \(n_0 \le j \le m\)” (or \(< n\) when proving \(P(n)\)).
- Identify which smaller instances you call.
- Provide enough bases for the recurrence depth.
Worked examples
Example 1 — Fibonacci closed identity
\(P(n): F_{n+1} F_{n-1} - F_n^2 = (-1)^n\) (Cassini) for \(n\ge 1\) with standard \(F\)—optional challenge. Simpler:
Claim. \(F_1 + \cdots + F_n = F_{n+2} - 1\) (with \(F_1=1,F_2=1\)).
Weak induction works; uses \(F_{n+1}=F_n+F_{n-1}\) carefully—standard textbook induction.
Example 2 — Strong: every \(n\ge 2\) has a prime factor
Base \(n=2\): prime.
Assume every \(j\) with \(2\le j < n\) has a prime factor. If \(n\) prime, done. If \(n=ab\) with \(1<a,b<n\), then \(a\) has a prime factor, which divides \(n\). \(\square\)
Example 3 — Postage \(3\) and \(5\)
Claim. Every \(n \ge 8\) is \(3x+5y\) for some \(x,y\ge 0\).
Bases: \(8=1\cdot 3+1\cdot 5\), \(9=3\cdot 3\), \(10=2\cdot 5\).
Strong step: for \(n>10\), \(n-3 \ge 8\) is representable by IH; add one \(3\)-stamp. \(\square\)
(Bases of three consecutive needed because step subtracts \(3\).)
Example 4 — Weak fails form for \(F_n\) property needing two
Any identity relating \(F_{n+1}\) to \(F_n\) and \(F_{n-1}\) needs two previous—strong or double base weak with IH on \(k\) and lemma.
Example 5 — List length
\(\mathrm{len}(\mathrm{nil})=0\), \(\mathrm{len}(\mathrm{cons}(h,t))=1+\mathrm{len}(t)\).
Claim. \(\mathrm{len}(xs)+\mathrm{len}(ys)=\mathrm{len}(xs{+\!\!+}ys)\) (concatenate).
Structural induction on \(xs\): nil base; cons step.
Example 6 — Tree size
\(size(\mathrm{Leaf})=1\), \(size(\mathrm{Node}(L,v,R))=1+size(L)+size(R)\).
Claim. \(size(T) \ge 1\). Structural induction.
Example 7 — Tree height
\(height(\mathrm{Leaf})=0\), \(height(\mathrm{Node})=1+\max(height(L),height(R))\).
Claim. \(size(T) \le 2^{height(T)+1}-1\) for binary trees. Strong/structural on \(T\).
Example 8 — Loop invariant: sum
s = 0; i = 1
while i <= n:
s = s + i
i = i + 1Invariant \(I\): \(s = \sum_{j=1}^{i-1} j\) and \(1 \le i \le n+1\).
Init: \(s=0\), \(i=1\). Maintain: add \(i\), increment. Exit: \(i=n+1\), \(s=\sum_{j=1}^n j\).
Example 9 — Linear search invariant
i from \(0\); \(I\): \(\forall j < i,\; a[j] \neq x\). If exit with \(i=n\), \(x\) not present; if find, return index.
Example 10 — Binary search invariant (sketch)
Sorted array; \(I\): \(x\) in \(a[0..n)\) implies \(x\) in \(a[lo..hi]\) (closed or half-open—fix bounds). Mid update preserves \(I\); interval shrinks ⇒ termination.
Example 11 — Euclidean algorithm
While \(b \neq 0\): \((a,b) \leftarrow (b, a \bmod b)\).
Invariant: \(\gcd(a,b)=\gcd(a_0,b_0)\). Maintenance from \(\gcd(a,b)=\gcd(b,a\bmod b)\). Exit \(b=0\) ⇒ \(\gcd=a\).
Example 12 — Strong induction on \(n//2\)
Mergesort correctness: assume recursive calls on smaller lengths correct; merge preserves sortedness. Size decreases by half—strong induction on array length.
Example 13 — Multiple bases Fibonacci inequality
\(F_n \le 2^{n-1}\) for \(n\ge 1\): bases \(n=1,2\); step \(F_{m+1}=F_m+F_{m-1}\le 2^{m-1}+2^{m-2}\le 2^m\).
Example 14 — Structural vs weak
Inducting on \(\mathrm{len}(xs)\) is weak induction on \(\mathbb{N}\); structural induction packages the same idea with constructors—preferred for ADTs.
Exercises
- Prove by strong induction: every integer \(n\ge 2\) has a prime divisor.
- Postage: denominations \(4\) and \(7\)—find \(N\) such that all \(n\ge N\) work; prove with enough bases.
- Prove \(F_n \le 2^{n-1}\) with your \(F\) indexing.
- Prove \(\sum_{i=1}^n F_i = F_{n+2}-1\) (standard indexing \(F_1=F_2=1\)).
- Structural: \(\mathrm{len}(reverse(xs))=\mathrm{len}(xs)\) (assume recursive reverse definition you write).
- Structural: height bounds size as in Example 7.
- Write init/maintain/exit for factorial loop.
- Write invariant for “find max in nonempty array” loop.
- Prove by strong induction: any amount \(n\ge 12\) using \(4\) and \(5\) cent stamps? Check and adjust \(N\).
- Show weak induction can prove the strong-induction schema by defining \(Q(n)=\forall j\le n\, P(j)\) (outline).
- Binary search: argue termination using \(hi-lo\) decreases.
- Euclid: prove \(b\) strictly decreases and stays nonnegative.
- Tree: prove number of leaves related to number of degree-\(2\) nodes in full binary trees (standard relation).
- Strong induction: \(a_n = a_{\lfloor n/2\rfloor} + n\) with \(a_1=1\)—prove \(a_n \le 2n\) or similar bound you choose and verify.
- Loop invariant for reversing an array in place (two pointers)—state \(I\).
- Why does Example 3 need three bases?
- Prove Cassini for small \(n\) by hand; optional full induction.
- Structural induction: \(\mathrm{map}(f, xs{+\!\!+}ys)=\mathrm{map}(f,xs){+\!\!+}\mathrm{map}(f,ys)\).
- Correctness sketch: insertion into sorted list preserves sortedness (induct on list).
- Give a false algorithm “proof” that forgets init of invariant; explain the hole.
- Prove every positive integer is a product of primes (existence, strong induction)—fundamental theorem’s existence half.
- Frobenius awareness: for \(3,5\) largest impossible is \(7=3\cdot 5-3-5\); verify \(7\) impossible, \(8+\) possible.
- Induct on rounds: after \(r\) doublings, size \(\ge 2^r\) from \(1\).
- Write \(P(n)\) for mergesort and state strong step dependencies.
- Compare: prove \(2^n > n\) by weak induction vs by strong—do both.
CS connection
- Recursion correctness = structural / strong induction on input size.
- Loop invariants in Hoare logic; industrial use in critical code reviews.
- Binary search bugs are almost always invariant/bound errors (off-by-one).
- GCD / crypto depend on Euclid’s invariant.
- Distributed rounds use induction on round number.
- Compilers: instruction selection/optimizations proved by structural induction on IR.
Common pitfalls
| Pitfall | What to do instead |
|---|---|
| Too few bases for recurrence order | Provide order-many consecutive bases |
| Claiming strong but only using \(P(k)\) | Still OK, but don’t skip needed \(P(k-1)\) |
| Invariant too weak | Strengthen so postcondition follows |
| Invariant too strong | Cannot prove maintenance |
| No termination argument | Need variant or finite measure |
| Structural induction without base constructor | Handle nil/leaf |
| Off-by-one in loop bounds | State inclusive/exclusive ranges in \(I\) |
Checkpoint
- State strong induction
- Prove prime-factor existence
- Complete one postage proof
- Structural induction on lists or trees
- Full loop invariant (init/maintain/exit/use)
- Sketch binary search or Euclid invariant
- Exercises done or logged
Two takeaways:
- …
- …
Deep dive — strong induction schema in practice
When proving \(P(n)\), open with:
“Fix \(n > n_0\) and assume \(P(j)\) for all \(j\) with \(n_0 \le j < n\) (strong IH). …”
Then reduce \(n\) to one or more strictly smaller instances.
Fibonacci toolkit
With \(F_1=1,F_2=1,F_{n}=F_{n-1}+F_{n-2}\):
- \(\sum_{i=1}^n F_i = F_{n+2}-1\)
- \(F_n\) counts tilings of an \((n-1)\)-board with tiles of size 1 and 2 (combinatorial story)
- Growth \(\varphi^n/\sqrt{5}\) awareness (Binet)—not required to prove fully here
Loop invariant quality checklist
| Question | Good invariant answers |
|---|---|
| What’s true about the prefix processed? | Precise predicate on indices |
| Does init hold? | Check before loop |
| Does body preserve? | Symbolic one iteration |
| At exit, enough for post? | \(I\wedge\neg G\Rightarrow\) post |
| Does it terminate? | Variant decreases |
Structural induction = induction on derivation of the object
Lists/trees are built by rules; proofs follow the same rules. This matches how compilers recurse on ASTs.
More worked examples
Example 15 — Strong: complete binary tree node count
At most \(2^{h+1}-1\) nodes at height \(h\): use IH on both subtrees.
Example 16 — Postage 4 and 5
Bases \(4,5,6=4+...,7=...,8=2\cdot4\); step \(n\mapsto n-4\) for \(n\ge 8\) carefully with enough bases.
Example 17 — Euclid variant
\(a+b\) decreases as a variant if you prefer sum to single \(b\).
Example 18 — Binary search invariant bug
Off-by-one: \(lo\le hi\) vs \(lo<hi\); write both and see which postcondition works.
Additional exercises
- Prove \(F_n\) is even iff \(3\mid n\) (strong or pattern + induction).
- Structural: prove \(\mathrm{size}(T)=1+\mathrm{leaves}(T)+\mathrm{internal}(T)\) with your definitions.
- Write full invariant proof for “max in array” loop.
- Strong induction: any amount \(\ge 12\) with stamps \(4\) and \(5\)—or find exact Frobenius.
- Explain why mergesort needs strong induction on length rather than weak \(n-1\) only.
Extended practice workshop
Strong induction proofs
- Every \(n\ge 2\) has a prime factor.
- Postage with \(3\) and \(5\) from \(N=8\).
- Postage with \(4\) and \(7\)—find \(N\) and prove.
- \(F_n \le 2^{n-1}\) with stated indexing.
- \(\sum_{i=1}^n F_i = F_{n+2}-1\).
- Existence of prime factorization (product of primes) for \(n\ge 2\).
Structural induction
- \(\mathrm{len}(xs{+\!\!+}ys)=\mathrm{len}(xs)+\mathrm{len}(ys)\).
- \(\mathrm{len}(\mathrm{rev}(xs))=\mathrm{len}(xs)\) with your rev definition.
- \(size(T)\le 2^{h(T)+1}-1\) for binary trees.
- \(\mathrm{map}(f,xs{+\!\!+}ys)=\mathrm{map}(f,xs){+\!\!+}\mathrm{map}(f,ys)\).
Loop invariants (write init/maintain/exit/use)
- Sum \(1..n\).
- Linear search.
- Euclid GCD.
- Binary search on sorted array (bounds careful).
- Reverse array two-pointer.
Meta
- Why three consecutive bases when step subtracts \(3\).
- Convert strong proof idea to \(Q(n)=\forall j\le n\, P(j)\) weak form (outline).
- Compare structural induction on lists vs weak induction on length.
Invariant quality score (0–2 each)
| Criterion | Score |
|---|---|
| Precise predicate | |
| Init true | |
| Maintained | |
| Implies post | |
| Termination |
Tomorrow
Day 33 — Fallacies. Affirming the consequent, illicit quantifier shifts, bad induction, circular reasoning; debug broken proofs.