Day 31 — Weak induction

Day 31 — Weak induction

Stage III · concept day
Goal: State the principle of mathematical induction; connect it to well-ordering; prove sum, divisibility, inequality, and counting identities by weak induction; preview loop invariants; recognize common failures (including the “all horses the same color” fallacy); internalize the write-up template.

Why this matters

Induction is the mathematician’s for loop: prove \(P(n_0)\), then prove each step preserves truth. Closed forms for sums, tree size formulas, and the inductive step of algorithm correctness all use this spine. If you skip the base or smuggle the conclusion into the step, you get the horses fallacy—or a “proof” of a false claim.

Theory

Principle of mathematical induction (weak)

Let \(P(n)\) be a predicate on integers \(n \ge n_0\).

If:

1. Base case: \(P(n_0)\) is true, and
   
2. Inductive step: \(\forall k \ge n_0,\; \bigl(P(k) \rightarrow P(k+1)\bigr)\),

then \(\forall n \ge n_0,\; P(n)\).

Well-ordering link

Well-ordering principle: every nonempty subset of \(\mathbb{N} = \{0,1,2,\ldots\}\) (or \(\{1,2,\ldots\}\)) has a least element.

Sketch why induction holds. Suppose base and step, but \(C = \{n \ge n_0 : \neg P(n)\}\) nonempty. Let \(m = \min C\). Then \(m \neq n_0\) (base), so \(m-1 \ge n_0\) and \(P(m-1)\) holds, so step gives \(P(m)\), contradiction. \(\square\)

Conversely, induction can prove well-ordering-style results; treat both as foundational.

Writing discipline (always)

1. Define \(P(n)\) precisely (full claim for that \(n\)).
   
2. Base: prove \(P(n_0)\) by direct computation.
   
3. IH: assume \(P(k)\) for fixed arbitrary \(k \ge n_0\).
   
4. Step: prove \(P(k+1)\) using IH + algebra/definitions.
   
5. Conclude by induction.

What “weak” means

You may assume only \(P(k)\) when proving \(P(k+1)\)—not \(P(k-1),\ldots\). Strong induction (Day 32) assumes all smaller values.

Domains and shifted bases

• Sums often start at \(n=1\) or \(n=0\) (empty sum \(0\)).
  
• Inequality \(2^n \ge n+1\) for \(n\ge 0\).
  
• If step fails for small \(k\), start \(n_0\) higher and check intermediate bases manually.

Template for sum identities

\(P(n): \sum_{i=1}^n a_i = f(n)\).
Base \(n=1\) (or \(0\)).
Step: \(\sum_{i=1}^{k+1} a_i = \bigl(\sum_{i=1}^k a_i\bigr) + a_{k+1} = f(k) + a_{k+1}\) by IH; algebra to \(f(k+1)\).

Template for divisibility

\(P(n): m \mid f(n)\).
Often \(f(k+1)-f(k)\) or \(f(k+1)-r f(k)\) is visibly divisible by \(m\).

Template for inequalities

Use IH inside an inequality chain; track direction; ensure steps valid for \(k \ge n_0\).

Loop invariant preview

For a loop, an invariant \(I\) satisfies:

1. true before first iteration (init),
   
2. if true before iteration and guard true, true after (maintain),
   
3. \(I \wedge \neg\mathrm{guard}\) implies postcondition (use).

Induction on iteration count \(t\): \(P(t)=\) “\(I\) holds after \(t\) iterations.” Full pattern Day 32.

Common failure: all horses the same color

False claim. In any set of \(n\ge 1\) horses, all have the same color.

Broken “proof.” Base \(n=1\) OK. Assume any \(k\) horses same color. Take \(k+1\) horses; the first \(k\) same color, the last \(k\) same color, so all \(k+1\) same—fails at \(k=1\): the two groups of \(k=1\) horses do not overlap, so colors need not match. The step \(P(1)\rightarrow P(2)\) is false. Induction does not apply.

Moral: verify the step for every \(k \ge n_0\), especially the smallest.

Other failure modes

• Base wrong, step OK ⇒ false theorem “proved.”
  
• Step assumes \(k \ge 2\) but base only \(n=0\).
  
• IH applied to wrong instance.
  
• Algebra error in step (most common honest failure).

Induction is not circular

You do not assume \(P(k+1)\). You assume \(P(k)\) and derive \(P(k+1)\). The principle then lifts to all \(n\).

Worked examples

Example 1 — Sum of first \(n\) integers

\(P(n): \sum_{i=1}^n i = n(n+1)/2\) for \(n\ge 1\).
Base \(n=1\): \(1=1\cdot 2/2\).
IH: sum to \(k\) equals \(k(k+1)/2\).
Step: sum to \(k+1\) = \(k(k+1)/2 + (k+1) = (k+1)(k+2)/2\). \(\square\)

Example 2 — Geometric sum

\(P(n): \sum_{i=0}^n r^i = (r^{n+1}-1)/(r-1)\) for \(r\neq 1\), \(n\ge 0\).
Base \(n=0\): \(1=(r-1)/(r-1)\).
Step: sum to \(k\) plus \(r^{k+1}\) = \((r^{k+1}-1)/(r-1) + r^{k+1} = (r^{k+2}-1)/(r-1)\). \(\square\)

Example 3 — Divisibility

\(P(n): 3 \mid (4^n - 1)\) for \(n\ge 0\).
Base: \(4^0-1=0\).
Step: \(4^{k+1}-1 = 4\cdot 4^k - 1 = 4(4^k-1) + 3\), divisible by \(3\) if \(4^k-1\) is. \(\square\)

Example 4 — Inequality

\(P(n): 2^n \ge n+1\) for \(n\ge 0\).
Base: \(1\ge 1\).
Step: \(2^{k+1} = 2\cdot 2^k \ge 2(k+1) = 2k+2 \ge k+2\) for \(k\ge 0\). \(\square\)

Example 5 — Strict inequality later start

\(2^n > n\) for \(n\ge 1\): base \(2>1\); step similar.

Example 6 — Factorial bound

\(n! \ge 2^{n-1}\) for \(n\ge 1\): base \(1\ge 1\); step \((k+1)! = (k+1)k! \ge (k+1)2^{k-1} \ge 2\cdot 2^{k-1} = 2^k\) for \(k\ge 1\).

Example 7 — Set counting preview

Number of subsets of an \(n\)-element set is \(2^n\): base empty set \(1=2^0\); step: partition subsets by whether they contain a fixed element \(a\)—two copies of \(2^k\) subsets for size \(k+1\). (Also Day 36.)

Example 8 — Sum of odds

\(\sum_{i=1}^n (2i-1) = n^2\). Base \(1=1\); step \(k^2 + (2(k+1)-1) = k^2 + 2k +1 = (k+1)^2\).

Example 9 — Telescoping via induction

\(\sum_{i=1}^n \bigl(\frac{1}{i}-\frac{1}{i+1}\bigr) = 1-\frac{1}{n+1}\). Direct telescope preferred; induction also works.

Example 10 — Loop invariant lite

Loop summing \(1..n\): after \(t\) iterations, \(s = \sum_{i=1}^t i\) (with \(t\) from \(0\) to \(n\)). Init \(s=0\); maintain \(s\leftarrow s+(t+1)\); at end \(t=n\) gives formula—connects to Example 1.

Example 11 — Horses pinpoint

\(P(1)\) true; \(P(k)\rightarrow P(k+1)\) false for \(k=1\); true for \(k\ge 2\) if we absurdly assumed… actually for horses the step fails only when groups don’t overlap, i.e. \(k=1\). For \(k\ge 2\) the broken argument’s overlap would work if \(P(k)\) meant something true—but the claim is false for \(n\ge 2\), so step cannot hold for all \(k\). More carefully: the argument for the step is invalid at \(k=1\); for \(k\ge 2\) the argument would correctly show \(P(k)\rightarrow P(k+1)\) if \(P(k)\) were “any \(k\)-set monochromatic,” but since \(P(2)\) is false, implication \(P(2)\rightarrow P(3)\) is vacuously true. Induction needs step for all \(k\) including \(1\).

Example 12 — Wrong base

“Prove” \(n = n+1\) for \(n\ge 0\) with false base and “step” adding \(1\)—garbage in, garbage out.

Example 13 — \(n^3-n\) divisible by \(3\)

\(P(n): 3\mid(n^3-n)\). Factor \(n(n-1)(n+1)\) three consecutive; or induction: \((k+1)^3-(k+1) - (k^3-k) = 3k^2+3k\) divisible by \(3\).

Example 14 — Binary tree height bound (sketch)

A full binary tree of height \(h\) has at most \(2^{h+1}-1\) nodes: induction on \(h\).

Exercises

Write complete induction proofs unless asked only for \(P(n)\).

1. Prove \(\sum_{i=1}^n i^2 = n(n+1)(2n+1)/6\) for \(n\ge 1\).
   
2. Prove \(\sum_{i=1}^n i^3 = \bigl(n(n+1)/2\bigr)^2\) for \(n\ge 1\).
   
3. Prove \(2^n \ge n+1\) for all \(n\ge 0\).
   
4. Prove \(3 \mid (n^3 - n)\) for all integers \(n\ge 0\) by induction.
   
5. Prove \(4^n - 1\) is divisible by \(3\) (as in examples).
   
6. Prove \(\sum_{i=0}^n 2^i = 2^{n+1}-1\).
   
7. Prove \(n! > 2^n\) for all \(n \ge 4\) (check base at \(4\)).
   
8. Prove \(1 + 2 + \cdots + n = n(n+1)/2\) again in your own words.
   
9. Find the bug in a horses-style argument for a claim you invent.
   
10. Prove by induction: \(7^n - 1\) divisible by \(6\) for \(n\ge 0\).
    
11. Prove \(\sum_{i=1}^n (2i-1) = n^2\).
    
12. Prove \(2n+1 \le 3^n\) for \(n\ge 1\).
    
13. Define \(P(n)\) for “\(n\) lines in general position divide the plane into \((n(n+1)/2)+1\) regions” and prove it (standard).
    
14. Induction on \(n\): number of edges in complete graph \(K_n\) is \(n(n-1)/2\).
    
15. Prove Bernoulli: \((1+x)^n \ge 1+nx\) for \(x\ge -1\), \(x\in\mathbb{R}\), \(n\in\mathbb{N}\) (careful with \(x=-1\)).
    
16. Where does the step fail for \(P(n): n = n+1\)?
    
17. Prove \(\sum_{i=1}^n \frac{1}{i(i+1)} = 1 - \frac{1}{n+1}\) by induction.
    
18. Loop: write invariant for factorial loop \(f *= i\).
    
19. Prove \(5 \mid (n^5 - n)\) for \(n\ge 0\) (harder; or for small pattern \(n^5-n\) factor)—optional challenge.
    
20. Show base \(n=0\) and step for \(|P(\{1,\ldots,n\})|=2^n\).
    
21. Prove by induction on \(n\) that a set with \(n\) elements has \(n(n-1)/2\) unordered pairs.
    
22. False claim \(n^2 + n + 41\) always prime—show induction cannot “prove” it; give counterexample.
    
23. Prove \(3^n > n^2\) for \(n \ge 1\) (check small \(n\), induct when step works).
    
24. Connect: prove well-ordering for a finite nonempty subset of \(\mathbb{N}\) by induction on size.
    
25. Write the full template from memory, then fill it for \(\sum i = n(n+1)/2\).

CS connection

• Loop invariants are induction on iteration count.
  
• Recursive functions: structural induction Day 32; weak induction on size parameter.
  
• Complexity: unfolding recurrences gives sums proved by induction.
  
• Protocol rounds: property after \(r\) rounds.
  
• Compiler correctness lemmas often induct on AST size (strong/structural).
  
• Failing base cases in code ≈ off-by-one; failing step ≈ bug in loop body.

Common pitfalls

Pitfall	What to do instead
Skipping base	Always compute \(P(n_0)\)
Assuming \(P(k+1)\)	Assume only IH \(P(k)\)
Step fails at \(k=n_0\)	Check small \(k\) explicitly
Vague \(P(n)\)	Write full equation/claim
Algebra slip	Expand carefully; verify small \(k\)
Horses overlap error	Ensure shared structure in step
Inducting on wrong variable	Match \(P\) to the growing parameter

Checkpoint

• State weak induction principle
  
• Link to well-ordering in one paragraph
  
• Prove sum formula cold
  
• Prove one divisibility by induction
  
• Prove one inequality by induction
  
• Explain horses fallacy
  
• Write loop-invariant preview sentence
  
• Exercises done or logged

Two takeaways:

1. …
   
2. …

Deep dive — induction as a proof system rule

Think of induction as a rule of inference:

\[\frac{P(n_0) \qquad \forall k\ge n_0\,(P(k)\rightarrow P(k+1))}{\forall n\ge n_0\, P(n)}\]

You discharge two subgoals (base and step); the principle gives the universal conclusion. This is not circular: the step proves an implication for arbitrary \(k\), not the universal claim itself.

Choosing \(n_0\)

Situation	Move
Formula fails for \(n=0\) but holds \(n\ge 1\)	Set \(n_0=1\)
Step needs \(k\ge 2\)	Prove \(P(0),P(1)\) as bases or use strong induction
Empty sum conventions	Often \(n_0=0\) cleaner

Loop invariant as induction (preview formal)

\(P(t)\): after \(t\) iterations, invariant \(I\) holds.
Base \(t=0\): initialization.
Step: body preserves \(I\).
At termination \(t=T\), \(I\) + \(\neg G\) ⇒ postcondition.

More worked examples

Example 15 — Sum of geometric in base 2
\(\sum_{i=0}^n 2^i = 2^{n+1}-1\) again with careful IH.

Example 16 — Inequality \(n < 2^n\)
For \(n\ge 1\): base \(1<2\); step \(k+1 < 2^k + 1 \le 2^k + 2^k = 2^{k+1}\) for \(k\ge 1\).

Example 17 — Divisibility \(6\mid n^3-n\)
Factor \(n(n-1)(n+1)\) or induct; compare to \(3\mid n^3-n\).

Example 18 — False induction write-up
“Assume true for all \(k\), prove for \(n\)”—that is strong induction language misused in a weak write-up; fix quantifiers.

Additional exercises

26. Prove \(\sum_{i=1}^n i(i+1) = n(n+1)(n+2)/3\).
    
27. Prove \(4\mid 5^n-1\) for \(n\ge 0\)? Check; adjust.
    
28. Prove by induction: \(1\cdot 1! + 2\cdot 2! + \cdots + n\cdot n! = (n+1)! - 1\).
    
29. Where does induction “prove” all horses same color fail—write 5 sentence analysis.
    
30. Connect: prove \(s=\sum_{i=1}^n i\) loop correct via \(P(t)\) invariant form.

Extended practice workshop

Template fill-ins (write full proofs)

1. \(\sum_{i=1}^n i = n(n+1)/2\)
   
2. \(\sum_{i=0}^n r^i = (r^{n+1}-1)/(r-1)\) (\(r\neq 1\))
   
3. \(\sum_{i=1}^n (2i-1)=n^2\)
   
4. \(2^n \ge n+1\) for \(n\ge 0\)
   
5. \(3\mid(4^n-1)\)
   
6. \(n! \ge 2^{n-1}\) for \(n\ge 1\)
   
7. Number of subsets of \(n\)-set is \(2^n\)
   
8. \(\sum_{i=1}^n i(i+1)=n(n+1)(n+2)/3\)

Bug hunt

9. Find the error in a horses-colored proof (write your own flawed version then mark it).
   
10. Base false, step true: invent \(P(n)\) that is never true but step holds vacuously from false \(P(k)\).
    
11. Step fails only at \(k=0\): invent example.

Loop invariant lite

12. Sum loop invariant \(I(i,s)\).
    
13. Factorial loop invariant.
    
14. “count zeros in array” invariant.

Meta

15. Explain well-ordering link in \(\le 8\) sentences.
    
16. Why IH is not circular (paragraph).
    
17. When to start at \(n_0=4\) instead of \(0\).

Induction write-up checklist

• \(P(n)\) displayed
  
• Base computed
  
• IH stated with quantifier on \(k\)
  
• Goal \(P(k+1)\) stated
  
• Algebra connects IH to goal
  
• Conclusion sentence

Synthesis

Weak induction is the default tool whenever a claim is indexed by \(n\in\mathbb{N}\) (or \(n\ge n_0\)). Mastery means: precise \(P(n)\), honest base, IH used exactly once as \(P(k)\), and algebra that actually reaches \(P(k+1)\). Everything “inductive” later—strong induction, structural induction, loop invariants—is a variant of this spine.

Anatomy of a bulletproof write-up

Define P(n): …
Base (n = n0): … (arithmetic)
Inductive step: Fix k ≥ n0. Assume P(k).   ← IH
  Goal: P(k+1).
  … chain using IH …
  Therefore P(k+1).
By induction, ∀ n ≥ n0, P(n).

More worked examples

Example 19 — Sum of squares (compressed).
\(P(n):\sum_{i=1}^n i^2 = n(n+1)(2n+1)/6\).
Base \(n=1\): \(1=1\cdot2\cdot3/6\).
Step: IH sum \(+ (k+1)^2\) algebraically equals \((k+1)(k+2)(2k+3)/6\) after expanding both sides.

Example 20 — Divisibility with a telescoping difference.
\(P(n): 6\mid n^3-n\). Note \(n^3-n=n(n-1)(n+1)\). Among three consecutive integers, one is divisible by \(3\) and at least one by \(2\), so by \(6\)—direct factor argument. Induction also works: difference \((k+1)^3-(k+1)-(k^3-k)=3k(k+1)\) divisible by \(6\) for integer \(k\). Prefer the factor proof; keep induction as backup.

Example 21 — Choosing \(n_0\) for \(n! > 2^n\).
Fails for \(n=1,2,3\) (\(1\not>2\), \(2\not>4\), \(6\not>8\)). Holds at \(n=4\) (\(24>16\)). Induct for \(n\ge 4\): \((k+1)! = (k+1)k! > (k+1)2^k \ge 2\cdot 2^k = 2^{k+1}\) since \(k+1\ge 5>2\). Check base carefully.

Example 22 — Horses as a step-check protocol.
Whenever your step uses “two overlapping substructures of size \(k\),” verify overlap exists for every \(k\ge n_0\). At \(k=1\), two \(1\)-element subsets of a \(2\)-set are disjoint—classic trap.

Extra exercises (synthesis)

31. Prove \(\sum_{i=1}^n i^2 = n(n+1)(2n+1)/6\) with every algebra line shown.
    
32. Prove \(8\mid 3^{2n}-1\) for \(n\ge 0\) by induction (or find the correct modulus/statement if this fails—check \(n=0,1\)).
    
33. Prove \(1\cdot 1! + \cdots + n\cdot n! = (n+1)!-1\).
    
34. Write \(P(t)\) for a loop s=0; i=1; while i≤n: s+=i; i+=1 and prove \(s=n(n+1)/2\) at exit.
    
35. Invent a false \(P\) with true base and false step; invent a false \(P\) with false base and true step.
    
36. Explain in \(\le 6\) sentences why induction is not circular.

Failure mode flashcard

Symptom	Likely bug
True for small \(n\), “proof” for all	Step invalid at small \(k\) (horses)
Step fine, claim false	Base missing/wrong
Algebra fails at \(k=0\) only	Raise \(n_0\) or handle separately
Used \(P(k+1)\) in the middle	Circular / assumed goal

Cold-write Example 1 and Example 3 from memory before Day 32; if the template is not automatic, strong induction will only add confusion.

Tomorrow

Day 32 — Strong induction & invariants. Strong principle; Fibonacci; postage/Frobenius lite; structural induction on lists/trees; full loop-invariant pattern; algorithm correctness sketches.