Day 11 — Contrapositive, Cases & Induction

Updated

July 30, 2025

Day 11 — Contrapositive, Cases & Induction

Day 29 — Contrapositive & contradiction

Stage III · concept day
Goal: Choose when to use contrapositive vs contradiction vs direct proof; prove claims via \(\neg Q \rightarrow \neg P\); run classic contradiction proofs (\(\sqrt{2}\) irrational; infinitude of primes recall); prove uniqueness by contradiction.

Why this matters

Some hypotheses are messy while their negations are clean; some conclusions are “never happens” claims. Contrapositive and contradiction are not decorations—they are the standard tools for irrationality, impossibility, uniqueness, and many CS “cannot occur” safety arguments (deadlock freedom sketches, “no two primaries,” collision impossibility under assumptions).

Theory

Contrapositive proof

To prove \(P \rightarrow Q\), prove the equivalent \(\neg Q \rightarrow \neg P\) (Day 25).

Template:

Assume \(\neg Q\).
Derive \(\neg P\) (often directly).
Conclude \(P \rightarrow Q\) by contrapositive equivalence.

When it shines: \(Q\) is “\(n\) is even/odd/composite/…” and \(\neg Q\) gives a usable algebraic form; or \(P\) is a compound “and” that is hard to start from.

Proof by contradiction

To prove \(R\), assume \(\neg R\) and derive a contradiction (false statement: \(S \wedge \neg S\), or \(0=1\), or violation of a known theorem).

Template:

Assume \(\neg R\) for contradiction.
Reason to some \(S\) and \(\neg S\) (or absurdity).
Reject \(\neg R\); conclude \(R\).

Special case for \(P\rightarrow Q\): assume \(P \wedge \neg Q\), derive contradiction. Equivalent to showing \((P \wedge \neg Q)\) is impossible.

Contrapositive vs contradiction vs direct

Method	Assume	Goal shape
Direct	\(P\)	Derive \(Q\)
Contrapositive	\(\neg Q\)	Derive \(\neg P\)
Contradiction	\(\neg R\) (or \(P\wedge\neg Q\))	Derive falsehood

Contradiction is more general (and easier to abuse with fuzzy “absurd”). Prefer direct or contrapositive when they fit; use contradiction for impossibility/uniqueness/global claims.

Classic: \(\sqrt{2}\) is irrational

Claim. \(\sqrt{2} \notin \mathbb{Q}\).

Proof (contradiction). Suppose \(\sqrt{2} = p/q\) with \(p,q\in\mathbb{Z}\), \(q\neq 0\), fraction in lowest terms (\(\gcd(p,q)=1\)), \(p>0\), \(q>0\).
Then \(p^2 = 2 q^2\). So \(p^2\) is even ⇒ \(p\) even (Day 28 converse parity / cases). Write \(p=2k\).
\((2k)^2 = 2q^2 \Rightarrow 4k^2 = 2q^2 \Rightarrow q^2 = 2k^2\) ⇒ \(q\) even.
Then \(2\mid p\) and \(2\mid q\), contradicting \(\gcd(p,q)=1\).
Hence \(\sqrt{2}\) is irrational. \(\square\)

Classic recall: infinitude of primes

Claim. There are infinitely many primes.

Proof sketch (Euclid, contradiction). Suppose only finitely many primes \(p_1,\ldots,p_k\). Let \(N = p_1\cdots p_k + 1\). Then \(N > 1\) has a prime factor \(q\). But \(q\) cannot be any \(p_i\) (each leaves remainder \(1\) when dividing \(N\)). Contradiction. \(\square\)

Uniqueness by contradiction

To prove at most one object satisfies \(P\): assume \(P(a)\), \(P(b)\), and \(a\neq b\), derive contradiction—or better, derive \(a=b\) from \(P(a)\wedge P(b)\) (sometimes direct). Unique existence = existence + uniqueness.

Example pattern. Uniqueness of identity: if \(e,e'\) both identities, \(e = e\cdot e' = e'\).

Negations you need fluently

Claim	Negation
\(n\) even	\(n\) odd (on \(\mathbb{Z}\))
\(a\mid b\)	\(\forall m\, b \neq am\)
\(x\in\mathbb{Q}\)	\(x\) irrational
\(\forall x\, P(x)\)	\(\exists x\, \neg P\)
\(P\rightarrow Q\)	\(P \wedge \neg Q\)

Indirect proof hygiene

State “assume for contradiction …” explicitly.
Mark the contradictory pair.
Do not assume extra unjustified structure (e.g. “smallest counterexample” is well-ordering/induction territory—Day 31).
Lowest terms / well-defined gcd are part of the \(\sqrt{2}\) setup—mention them.

Proof of \(P \rightarrow Q\) by contradiction vs contrapositive

Assuming \(P\wedge \neg Q\) and deriving \(\neg P\) is essentially contrapositive plus unused \(P\) (or deriving false from \(P\)). Both valid; contrapositive is cleaner if you never need \(P\) in the branch.

Worked examples

Example 1 — Contrapositive parity

Claim. If \(n^2\) is even, then \(n\) is even.

Proof. Contrapositive: if \(n\) odd, then \(n^2\) odd (Day 28). \(\square\)

Example 2 — Contrapositive divides

Claim. If \(n\) is not divisible by \(3\), then \(n^2\) is not divisible by \(3\).
Contrapositive: if \(3\mid n^2\) then \(3\mid n\) (needs Euclid’s lemma / prime property—state as cited fact if not proved).

Example 3 — Contradiction: no largest integer

Claim. There is no largest integer.

Proof. Suppose \(N\) is largest. Then \(N+1 > N\) and \(N+1\in\mathbb{Z}\), contradiction. \(\square\)

Example 4 — \(\sqrt{2}\) details

Emphasize: even square ⇒ even base uses Example 1. gcd step needs that \(2\) is prime or that common factor \(2\) contradicts lowest terms.

Example 5 — Uniqueness of zero additive

If \(z+a=a\) for all \(a\), and \(0\) is the usual zero, show \(z=0\): set \(a=0\), \(z+0=0\) ⇒ \(z=0\). Or from two zeros: \(z = z+0' = 0'\).

Example 6 — Impossible config

Claim. There are not two distinct primary leaders if the system invariant says \(\exists! p\, Primary(p)\).

Proof. If \(Primary(p_1)\), \(Primary(p_2)\), \(p_1\neq p_2\), contradicts uniqueness clause of \(\exists!\). \(\square\)

Example 7 — Direct vs contrapositive choice

Claim: if \(n\) is multiple of \(6\), then \(n\) even. Direct is easy (\(n=6k=2(3k)\)). Contrapositive works but is longer. Prefer direct.

Example 8 — Contradiction for \(\forall\) denial

To show \(\neg \forall x\, P(x)\), exhibit counterexample—this is direct proof of \(\exists x\, \neg P\), not heavy contradiction. Prefer constructive counterexample when available.

Example 9 — Irrationality style for \(\sqrt{3}\) (outline)

Same as \(\sqrt{2}\) with \(3\): \(p^2=3q^2\) ⇒ \(3\mid p^2\) ⇒ \(3\mid p\), etc., need prime \(3\) divides product ⇒ divides factor.

Example 10 — Empty of solutions

Claim. No \(n\in\mathbb{Z}\) with \(n^2 = 2\).
If \(n^2=2\), then \(|n|\ge 2\) ⇒ \(n^2\ge 4\), or \(|n|\le 1\) ⇒ \(n^2\le 1\); contradiction. (Integer case—different from irrationality of \(\sqrt{2}\).)

Example 11 — Contrapositive with implication hypothesis

Prove: if \(n^2 + n\) is odd, then \(n\) is even? Wait check: \(n(n+1)\) always even. Odd never happens—vacuous. Bad claim. Better: if \(n^2\) odd then \(n\) odd (contrapositive of even square).

Example 12 — Infinite primes: construct \(N\)

For primes \(2,3,5\), \(N=31\) prime; for larger lists \(N\) may be composite but still has a new prime factor—that is enough.

Example 13 — Uniqueness of max in strict order

In a strictly ordered set, at most one maximum: if \(m_1,m_2\) both maxima, \(m_1\le m_2\) and \(m_2\le m_1\) ⇒ equal in total order with antisymmetry.

Example 14 — Proof that \(\sqrt{4}\) rational does not “break” method

\(\sqrt{4}=2=2/1\); the step “\(p^2=4q^2\) ⇒ \(p\) even” does not force infinite descent the same way because \(4\) is not square-free—method depends on prime factorization structure.

Exercises

Prove by contrapositive: if \(n^2\) is odd, then \(n\) is odd.
Prove by contrapositive: if \(n\) is even, then \(n+1\) is odd (almost definitional).
Prove by contradiction: there is no smallest positive real number.
Write a full \(\sqrt{2}\) irrational proof from memory.
Outline \(\sqrt{3}\) irrational; identify the prime lemma you need.
Prove: if \(a\) is rational and \(b\) irrational, then \(a+b\) is irrational (contradiction).
Prove: if \(a\neq 0\) rational and \(b\) irrational, then \(ab\) irrational.
Disprove: product of two irrationals is irrational (counterexample).
Prove uniqueness: at most one identity element in a structure with axiom \(e\cdot x=x=x\cdot e\).
Prove by contradiction: if \(n^2\) is divisible by \(2\), wait—use contrapositive preferred; write both styles for “even square ⇒ even \(n\).”
Euclid’s proof: explain why \(N\) is not divisible by any listed prime.
Prove: \(\log_2 3\) is irrational (hint: \(2^a=3^b\) forces parity/prime contradiction).
Show there is no largest even integer.
Prove: if \(3\nmid n\), then \(3\nmid n^2\)—state needed lemma or use cases mod \(3\) (Day 30).
Uniqueness of solution to \(2x=6\) in \(\mathbb{R}\) (direct or contradiction on two solutions).
Prove by contradiction that \(\sqrt{2}+\sqrt{8}\) is… actually rational? \(\sqrt{8}=2\sqrt{2}\), sum \(3\sqrt{2}\) irrational. Prove.
Method choice: for “if \(n\) ends with digit \(5\) then \(5\mid n\),” is direct or contrapositive better?
Prove: not both \(n\) and \(n+1\) even.
Formalize “cannot have two distinct masters in a single-master lock” as uniqueness.
Find the flaw: “Assume \(\sqrt{2}=p/q\). Then … something false about decimals … contradiction.” (Vague contradiction.)
Prove: if \(n\mid 7\) then \(n\in\{\pm1,\pm7\}\) using size/contradiction on factorization.
Show \(\nexists n\in\mathbb{Z}\, (2n=1)\).
Prove contrapositive form of: if a function \(f\) is injective then … (preview) wait: if \(f(a)=f(b)\) is false whenever \(a\neq b\)—write contrapositive of injectivity definition.
Infinite primes: show that from any finite list you can produce an integer with a prime factor outside the list.
Write \(\neg(P\rightarrow Q)\) and use it in a contradiction proof skeleton for an implication claim.

CS connection

Safety properties: “bad state never reachable” often proved by contradiction (assume reachable, violate invariant).
Uniqueness of leaders, mutex holders, primary keys.
Impossibility results (FLP, CAP awareness later) are contradiction/model arguments at systems scale.
Hash collision: under pigeonhole (Day 45), contradiction if too many keys without collision assumed.
Type soundness sketches: assume stuck state, contradict progress/preservation.
Prefer constructive counterexamples for “not always” bugs—contradiction not required.

Common pitfalls

Pitfall	What to do instead
Proving the converse by accident	Write \(\neg Q\rightarrow\neg P\) explicitly
“Contradiction” without naming it	Exhibit \(S\) and \(\neg S\)
Assuming lowest terms silently	State gcd \(=1\)
Using contradiction for easy direct claims	Prefer direct
Circular: using irrationality of \(\sqrt{2}\) to prove itself	Only prior facts
Infinite descent without justification	Formalize or use fixed \(\sqrt{2}\) pattern
Negating \(P\rightarrow Q\) as \(\neg P\rightarrow\neg Q\)	Negation is \(P\wedge\neg Q\)

Checkpoint

State contrapositive template
State contradiction template
Prove even-square converse via contrapositive
Reproduce \(\sqrt{2}\) irrational proof
Sketch infinitude of primes
Prove one uniqueness claim
Choose methods for three sample claims
Exercises done or logged

Two takeaways:

Deep dive — choosing the method

Claim shape	Prefer	Why
\(P\rightarrow Q\) with messy \(P\), clean \(\neg Q\)	Contrapositive	Start from \(\neg Q\)
“There is no …” / impossibility	Contradiction	Assume exists
Uniqueness	Assume two, derive equal (often direct) or contradict \(\neq\)
Algebraic identity / expansion	Direct
\(\sqrt{2}\notin\mathbb{Q}\)	Contradiction + lowest terms	Classic

Structure of the \(\sqrt{2}\) proof (checklist)

Assume \(\sqrt{2}=p/q\) in lowest terms, \(q>0\).
\(p^2=2q^2\).
\(p\) even ⇒ \(p=2k\).
\(q^2=2k^2\) ⇒ \(q\) even.
Common factor \(2\) contradicts lowest terms.
Discharge assumption.

Missing step 3’s lemma “even square ⇒ even root” is a common hole—prove it by contrapositive first.

Infinite primes — what is constructive?

Euclid produces, from any finite list, an integer \(N\) that has some prime factor outside the list. You may need to factor \(N\) to name the prime—existence is constructive relative to factorization.

More worked examples

Example 15 — Contrapositive divisibility
If \(n^2\) not divisible by \(3\), then \(n\) not divisible by \(3\) is the converse direction of the useful lemma; useful form: if \(3\mid n^2\) then \(3\mid n\) (Euclid’s lemma for prime \(3\)).

Example 16 — No rational root of \(x^2-2=0\)
Same as irrationality of \(\sqrt{2}\).

Example 17 — Contradiction for simultaneous
Cannot have \(n\) even and \(n=2k+1\) for integers—definitions contradict.

Example 18 — Uniqueness of empty set
If \(E_1,E_2\) both empty, then \(E_1\subseteq E_2\subseteq E_1\) so equal.

Additional exercises

Prove \(\sqrt[3]{2}\) irrational (outline with prime \(2\)).
Prove: if \(a\) rational, \(b\) irrational, \(a\neq 0\), then \(a/b\) irrational.
Method choice table: fill for five claims of your choice.
Find the gap in a fake \(\sqrt{2}\) proof that never uses lowest terms.
Prove uniqueness of additive inverse in \(\mathbb{Z}\).

Extended practice workshop

Contrapositive translations

Rewrite each as a contrapositive claim, then prove or outline:

If \(n^2\) even then \(n\) even.
If \(n\) ends with digit \(0\) then \(10\mid n\) (direct may be easier—note choice).
If a product \(ab\) is odd then \(a\) and \(b\) both odd.
If \(f(a)=f(b)\) always implies \(a=b\), then … (injectivity forms).

Contradiction drills

Full \(\sqrt{2}\) write-up from blank paper.
\(\sqrt{3}\) outline with prime lemma named.
No largest prime (Euclid).
No rational solution to \(x^2=2\) in \(\mathbb{Q}\).
If \(a\in\mathbb{Q}\), \(b\notin\mathbb{Q}\), then \(a+b\notin\mathbb{Q}\).
If \(a\in\mathbb{Q}\setminus\{0\}\), \(b\notin\mathbb{Q}\), then \(ab\notin\mathbb{Q}\).

Uniqueness drills

Unique solution to \(3x+1=7\) in \(\mathbb{R}\).
Unique empty set.
Unique identity in a monoid (axiomatic).
At most one maximum in a poset (preview).

Method selection (one line each)

15–20. For six claims of your invention, pick direct/contrapositive/contradiction and justify.

Proof cleanliness rubric

Criterion	0	1	2
Assumption stated
Contradiction pair explicit
Lemmas cited
Quantifiers clear

Synthesis

Indirect proof is not a second-class citizen—it is often the only clean path for impossibility, uniqueness, and “if messy then clean” implications. The skill is method choice plus hygiene: name the assumption, name the contradiction, cite lemmas, and never smuggle the goal into the premises.

Decision flowchart (use until automatic)

Is the claim “there is no …” / “impossible” / “at most one”? → Contradiction (or direct uniqueness \(a=b\)).
Is it \(P\rightarrow Q\) where \(\neg Q\) is algebraically nicer than \(P\)? → Contrapositive.
Is \(P\) already a usable hypothesis (even, divides, …)? → Direct.
If stuck, try contradiction on \(P\wedge\neg Q\); if you derive \(\neg P\) without using \(P\), rewrite as contrapositive.

More worked examples

Example 19 — Rational + irrational.
Claim. If \(a\in\mathbb{Q}\) and \(b\notin\mathbb{Q}\), then \(a+b\notin\mathbb{Q}\).
Proof. Suppose \(a+b=r\in\mathbb{Q}\). Then \(b=r-a\in\mathbb{Q}\), contradiction. \(\square\)

Example 20 — Product of nonzero rational and irrational.
Claim. If \(a\in\mathbb{Q}\setminus\{0\}\) and \(b\notin\mathbb{Q}\), then \(ab\notin\mathbb{Q}\).
Proof. If \(ab=r\in\mathbb{Q}\), then \(b=r/a\in\mathbb{Q}\) (since \(a\neq 0\)), contradiction. \(\square\)

Example 21 — Contrapositive beats direct.
Claim. If \(n^2\) is even then \(n\) is even.
Direct: “\(n^2=2k\) ⇒ \(n=\sqrt{2k}\)” is not integer reasoning. Contrapositive uses only odd \(\times\) odd = odd.

Example 22 — Uniqueness of multiplicative identity.
If \(e,e'\) both satisfy \(ex=x=xe\) and \(e'x=x=xe'\) for all \(x\), then \(e=ee'=e'\). No contradiction needed—direct equality chain.

Example 23 — Bad contradiction.
“Assume \(\sqrt{2}\) rational. Rationals have repeating decimals. \(\sqrt{2}\)’s decimal does not repeat. Contradiction.”
Bug: “does not repeat” is not established independently; the argument is circular or incomplete. Prefer the integer lowest-terms proof.

Extra exercises (synthesis)

Prove: if \(a\) rational and \(a+b\) rational, then \(b\) rational (contrapositive or direct rearrangement).
Prove: there is no smallest positive rational (contradiction: half of it).
Write both a contrapositive and a contradiction proof of “even square ⇒ even \(n\)”; compare length.
Prove uniqueness of the additive inverse of \(a\) in \(\mathbb{Z}\).
Outline why \(\sqrt{p}\) is irrational for prime \(p\) (same skeleton as \(\sqrt{2}\)).
Method choice only (no full proof): (a) sum of first \(n\) integers formula; (b) no largest prime; (c) if \(4\mid n^2\) then \(2\mid n\) (careful—true?); (d) \(n\) even ⇒ \(n^2\) even.

Clean write-up micro-rubric (apply to Ex. 31–35)

Assumption line present?
Contradiction pair named (\(S\) and \(\neg S\))?
Lowest terms / gcd stated when needed?
Quantifiers on \(n,a,b\) explicit?

Indirect proofs fail most often on hygiene, not on cleverness. Slow is fine; vague is not.

Tomorrow

Day 30 — Cases & existence. Exhaustive cases (parity, mod \(n\)); constructive vs non-constructive existence; max/min arguments; pigeon preview.

Day 30 — Cases & existence

Stage III · concept day
Goal: Structure exhaustive case proofs (parity, residue classes mod \(n\)); distinguish constructive and non-constructive existence; use min/max arguments carefully; preview the pigeonhole principle.

Why this matters

Computers branch; proofs branch. Exhaustive cases mirror switch on a finite set of possibilities. Existence claims mirror “there is a witness object”—sometimes you construct it, sometimes you only know it exists. Algorithms often need constructive witnesses (return the index); pure math sometimes does not. Knowing which you proved prevents false confidence in implementability.

Theory

Proof by exhaustive cases

To prove \(R\), find statements \(C_1,\ldots,C_k\) such that \(C_1\vee\cdots\vee C_k\) is true (covers all possibilities), and prove \(C_i \rightarrow R\) for each \(i\).

Checklist:

Cases are exhaustive (every possibility falls in some \(C_i\)).
Cases may overlap (OK if each still implies \(R\)) unless you claim a partition.
Handle edge cases (zero, empty, \(n=1\)).
Announce case structure up front.

Classic partitions

Parity: every \(n\in\mathbb{Z}\) is even or odd (not both).

Mod \(m\): every \(n\in\mathbb{Z}\) satisfies exactly one of \(n\equiv 0,1,\ldots,m-1 \pmod{m}\) (Division Algorithm).

Sign: \(x>0\), \(x=0\), or \(x<0\) for real \(x\).

Boolean: \(P\) or \(\neg P\) (classical logic).

Existence proofs

Constructive: exhibit an explicit witness \(c\) with \(P(c)\), or give an algorithm producing one.

Non-constructive: prove \(\exists x\, P(x)\) without naming a concrete \(x\)—often via contradiction (\(\neg\exists \equiv \forall\neg\) leads to falsehood), pigeonhole, or intermediate value-type theorems.

Both are valid classical mathematics. Software extraction usually wants constructive proofs.

Non-example of existence

Proof by example shows \(\exists\) sometimes, but “\(P(n)\) for \(n=1,2,3\)” does not show \(\forall n\, P(n)\).

Max and min arguments

On a finite nonempty set of reals (or integers), a maximum and minimum exist. On infinite sets, not always (\(\mathbb{Z}\) has no max; \((0,1)\) has no min in the set).

Well-ordering principle (for \(\mathbb{N}\)): every nonempty subset of \(\mathbb{N}\) has a least element. Underpins induction (Day 31) and “smallest counterexample” proofs.

Minimal counterexample method: to prove \(\forall n\, P(n)\), assume the set of counterexamples is nonempty, take least \(n_0\), derive contradiction (often using smaller cases that do satisfy \(P\)).

Pigeonhole principle (preview)

Basic. If \(n+1\) pigeons go into \(n\) holes, some hole has at least two pigeons.

Formally. Any function \(f: A \to B\) with \(|A| > |B|\) (finite) is not injective—some fiber has size \(\ge 2\).

Full treatment Day 45; today use only the basic form in simple arguments.

Combining with earlier methods

Cases inside a direct proof; existence of a case that works; contradiction that all cases fail; constructive choice of residue.

Division algorithm (tool)

For \(a\in\mathbb{Z}\) and \(d>0\), there exist unique \(q,r\) with \(a = dq + r\) and \(0\le r < d\). Residue \(r\) is the case label mod \(d\).

Worked examples

Example 1 — \(n(n+1)\) even

Claim. For all \(n\in\mathbb{Z}\), \(n(n+1)\) is even.

Proof. Case 1: \(n\) even, \(n=2k\), product \(2k(2k+1)\) even.
Case 2: \(n\) odd, \(n+1\) even, product even. \(\square\)

Example 2 — Squares mod \(4\)

Claim. For all \(n\in\mathbb{Z}\), \(n^2 \not\equiv 3 \pmod{4}\).

Proof. Cases \(n\equiv 0,1,2,3 \pmod{4}\):
\(0^2\equiv 0\), \(1^2\equiv 1\), \(2^2=4\equiv 0\), \(3^2=9\equiv 1 \pmod{4}\). Never \(3\). \(\square\)

Example 3 — Constructive existence

Claim. \(\exists n\in\mathbb{Z}\, (n^2 = n)\).
Witness \(n=0\) (or \(n=1\)). Constructive. \(\square\)

Example 4 — Non-constructive flavor (IVT awareness)

Any continuous \(f:[0,1]\to\mathbb{R}\) with \(f(0)<0<f(1)\) has a root—existence without a closed formula for the root. (Awareness; not a full analysis proof today.)

Example 5 — Pigeon preview

Among \(13\) people, at least two share a birth month (12 months). Holes = months, pigeons = people.

Example 6 — Cases on gcd style

If \(n\) mod \(3\) is \(0,1,2\), then \(n(n+1)(n+2)\) divisible by \(3\) (three consecutive). Case or note one of three consecutive is \(0 \bmod 3\).

Example 7 — Existence of quotient

For \(a=17\), \(d=5\), \(q=3\), \(r=2\) because \(17=5\cdot 3+2\). Constructive from division.

Example 8 — Max of finite set

\(S=\{3,1,4,1,5\}\) has max \(5\). Proof of existence for finite nonempty: induct on size (Day 31) or scan.

Example 9 — No max

\(\mathbb{N}\) if defined without bound has no maximum (for every \(n\), \(n+1\) larger). Contradiction proof Day 29 style.

Example 10 — Case split on algorithm branch

Correctness: if key present then path A returns index; if absent path B returns \(-1\). Exhaustiveness of present/absent.

Example 11 — Constructive vs not in number theory

Euclid’s proof shows a prime factor of \(N\) exists outside the list—constructive existence of some prime dividing \(N\), not necessarily a formula for the \(k\)-th prime.

Example 12 — Minimal counterexample sketch

Claim \(\forall n\ge 0\, 2^n \ge n\). If false, least \(n_0\ge 0\) with \(2^{n_0}<n_0\). Cannot be \(0\); then \(n_0-1\) ok… (complete with care Day 31 induction is cleaner).

Example 13 — Overlapping cases OK

Prove \(n^2 \ge n\) for \(n\in\mathbb{Z}\): cases \(n\le 0\) and \(n\ge 1\) (overlap \(n=0,1\) fine). Or \(n\le 0\), \(n=1\), \(n\ge 2\).

Example 14 — Existence for sorted check witness

If array not sorted, \(\exists i\, A[i]>A[i+1]\)—constructive by scanning for first inversion.

Exercises

Prove by cases: if \(n\in\mathbb{Z}\) then \(n^2+n\) is even.
Prove: \(n^2 \equiv 0\) or \(1 \pmod{4}\) for all \(n\).
Prove: among any \(3\) integers, two have difference divisible by \(2\) (parity pigeon).
Show \(\exists k\in\mathbb{Z}\, (5k+3 = 18)\) or disprove.
Constructive: find \(x,y\in\mathbb{Z}\) with \(3x+5y=1\) (or explain none).
Prove by mod \(3\) cases: if \(3\nmid n\) then \(n^2\equiv 1\pmod{3}\).
Existence: \(\exists\) irrational \(x,y\) with \(x+y\) rational (construct).
Existence: \(\exists\) irrational \(x,y\) with \(xy\) rational (construct).
Why does “checked \(n=1..1000\)” not prove a \(\forall n\) claim?
Pigeon: show among any \(6\) people, at least \(3\) born on same day of week? (Generalized—compute.)
Prove every integer is \(\equiv 0,1,\) or \(2 \pmod{3}\) using division algorithm statement.
Max argument: finite nonempty set of integers has a maximum—prove by induction on cardinality (outline OK).
Show \((0,1)\) has no least element.
Case proof: \(|x| \ge x\) and \(|x| \ge -x\) for real \(x\) from definition of \(|x|\).
If \(n\) mod \(2\) and \(m\) mod \(2\) known, case-table the parity of \(n+m\).
Non-constructive template: write a skeleton proving \(\exists x\, P(x)\) by assuming \(\forall x\, \neg P\) leads to contradiction (fill a toy \(P\)).
Among \(n+1\) integers, two have difference divisible by \(n\) (pigeon on residues mod \(n\)). Prove.
Does every nonempty subset of \(\mathbb{Q}^+\) have a least element? Counterexample.
Prove \(n^3 - n\) divisible by \(3\) by factoring or cases.
Algorithmic: describe a constructive witness for “unsorted array has an inversion.”
Prove: for all \(n\), \(n\) or \(n+1\) is even (cases / excluded middle).
Existence of mid index in binary search bounds \(lo \le hi\): \(mid=\lfloor(lo+hi)/2\rfloor\) is integer with \(lo\le mid\le hi\)—prove.
Case on empty/nonempty list for “max of list” spec.
Show that \(x^2 + y^2 = 3\) has no integer solutions by cases mod \(4\) (use Ex. squares mod \(4\)).
Write a full case proof that the product of two consecutive integers is even.

CS connection

Branch coverage in testing tries to hit proof cases.
Constructive proofs ≈ programs that return witnesses (Curry–Howard lite awareness).
Default cases in switch must preserve exhaustiveness—same bug as missing proof case.
Pigeonhole in hashing (Day 45–76): collisions must exist when load is high.
Division algorithm underpins % and bucket indices.
Min-counterexample debugging: smallest failing input.

Common pitfalls

Pitfall	What to do instead
Missing a residue class	List \(0,\ldots,m-1\) explicitly
Overlapping cases that disagree	Ensure each case implies the same claim \(R\)
Proof by example for \(\forall\)	Use arbitrary \(n\) or induction
Claiming construction when only non-constructive	Label the method
Max of open/infinite sets	Check finiteness / closedness
Pigeon with wrong hole count	Define holes clearly
Division algorithm with \(d\le 0\)	Require positive divisor

Checkpoint

Run a parity case proof cold
Run a mod \(4\) or mod \(3\) case proof
Give constructive and non-constructive existence examples
State basic pigeonhole
State well-ordering of \(\mathbb{N}\)
Explain when max/min exist
Exercises done or logged

Two takeaways:

Deep dive — building exhaustive case splits

Name the discriminant (parity, \(n \bmod m\), sign, empty/nonempty).
Prove the discriminant hits every possibility (cite division algorithm or LEM).
In each case, prove the goal—possibly with different algebra.
Optional: note overlapping cases if simpler.

Division algorithm (statement to use)

For integers \(a\) and \(d>0\), unique \(q,r\) exist with \(a=dq+r\) and \(0\le r<d\).
Residue \(r\) is the complete set of cases mod \(d\).

Constructive vs non-constructive table

Proof style	Delivers	Example
Exhibit witness	Object + check	\(n=0\) for \(n^2=n\)
Algorithm	Procedure producing object	Linear scan finds max
Contradiction / PHP	Existence only	Collision among \(n+1\) keys
IVT-style	Existence, not closed form	Root of continuous \(f\)

Minimal counterexample pattern

To prove \(\forall n\ge n_0\, P(n)\): assume \(C=\{n\ge n_0:\neg P(n)\}\neq\emptyset\), take \(m=\min C\), derive contradiction from \(P\) on smaller values. This is induction in disguise (Day 31).

More worked examples

Example 15 — Squares mod 3
\(n\equiv 0,1,2 \pmod 3\) ⇒ \(n^2\equiv 0,1,1\pmod 3\) never \(2\).

Example 16 — Existence of inverse mod prime (preview)
For \(p\) prime and \(a\not\equiv 0\), the map \(x\mapsto ax \bmod p\) injective on \(\{0,\ldots,p-1\}\) hence surjective—non-constructive-ish existence of inverse; extended Euclid constructs it.

Example 17 — Max of two
\(\max(x,y)\) exists for reals \(x,y\): cases \(x\ge y\) and \(y>x\).

Example 18 — Guarantee a pair of socks
3 colors, draw 4: PHP cases on colors.

Additional exercises

Prove \(n^2\equiv 0\) or \(1\pmod 3\) for all \(n\).
Prove no integer solutions to \(x^2+y^2=3\) using mod 4.
Construct irrational \(x,y\) with \(x^y\) rational (classic \(\sqrt{2}^{\sqrt{2}}\) story outline).
Case proof: \(|xy|=|x||y|\) for real \(x,y\).
Write a minimal-counterexample sketch for \(2^n \ge n+1\).

Extended practice workshop

Workshop 1 — Parity master sheet

Prove each in \(\le 6\) lines:

Sum of two odds is even.
Product of two odds is odd.
\(n\) even iff \(n^2\) even (both directions; one may use contrapositive).
\(n(n+1)(n+2)\) divisible by \(6\) (parity + mod 3).

Workshop 2 — Mod \(m\) master sheet

Squares mod \(5\) take values in \(\{0,1,4\}\).
No integer \(n\) with \(n^2\equiv 2\pmod 4\).
Among any \(3\) integers, two have difference divisible by \(2\).
Among any \(5\) integers, two have difference divisible by \(4\) (residues).

Workshop 3 — Existence master sheet

Construct \(x\in\mathbb{Q}\setminus\mathbb{Z}\).
Construct irrationals \(x,y\) with \(x+y\in\mathbb{Q}\).
Non-constructive: explain PHP existence of collision without naming keys.
Does every nonempty finite set of reals have a max? Prove or cite.

Workshop 4 — Algorithm-shaped cases

Spec: binary search mid index—cases on empty range / singleton / larger.
Spec: merge two sorted lists—cases on which head smaller.
Prove \(\lfloor n/2\rfloor + \lceil n/2\rceil = n\) by cases \(n\) even/odd.

Self-score

Workshop	Solved cold	Needed notes
1	/4
2	/4
3	/4
4	/3

Method selection cards

Keep these as flashcards:

Cases when a finite partition of the domain is natural.
Construct when a witness is easy.
PHP when crowding forces a property.
Contradiction when the claim is “none exist.”
Induction (tomorrow) when a statement is parameterized by \(n\in\mathbb{N}\).

Synthesis

Case analysis and existence are the branching and return of mathematical argument. Exhaustiveness is correctness of the switch; constructivity is whether the proof yields a program. Together with direct and indirect proof, you now have a complete “method menu” for Stage III claims that are not inductive.

Building a case proof that survives review

Name the discriminant (parity, residue mod \(m\), sign, empty/nonempty, key present/absent).
Cite why it covers all possibilities (division algorithm, LEM, definition).
Prove the same goal \(R\) in each branch—different algebra is fine; different conclusions are not.
Call out edges (\(n=0\), \(m=1\), empty list) even if they fall into a general case.

More worked examples

Example 19 — Product of two consecutive integers is even.
Cases: \(n\) even ⇒ \(n(n+1)\) even; \(n\) odd ⇒ \(n+1\) even ⇒ product even. Exhaustive by parity.

Example 20 — Squares mod \(5\).
Residues \(0,1,2,3,4\): squares \(0,1,4,4,1\). So \(n^2\not\equiv 2,3\pmod 5\). Useful for “no integer solution” arguments later.

Example 21 — Constructive irrationals summing to rational.
\(\sqrt{2}\) and \(1-\sqrt{2}\) are both irrational (if \(1-\sqrt{2}\) were rational then \(\sqrt{2}\) would be), and sum to \(1\in\mathbb{Q}\). Witness pair exhibited.

Example 22 — Non-constructive collision.
Any function \(\{1,\ldots,13\}\to\{1,\ldots,12\}\) is non-injective (PHP). Existence of a colliding pair without naming which keys collide until you scan.

Example 23 — Minimal counterexample vs induction.
To prove \(\forall n\ge 0\, P(n)\), taking the least counterexample and deriving a contradiction is induction in disguise. Prefer explicit induction write-ups once Day 31’s template is fluent; keep minimal-counterexample as a discovery tool.

Extra exercises (synthesis)

Prove by mod \(4\) cases that \(n^2+m^2\not\equiv 3\pmod 4\) for integers \(n,m\)—hence \(x^2+y^2=4k+3\) has no integer solutions.
Among any \(5\) integers, show two have difference divisible by \(4\) (pigeon on residues mod \(4\)).
Construct irrational \(x,y\) with \(xy\) rational and \(x\neq y\).
Prove \(\lfloor x\rfloor \le x < \lfloor x\rfloor+1\) for real \(x\) from the definition of floor (existence of the integer is the division/completeness tool you may cite).
Write a case-structured correctness argument for: “if list length is \(0\) return sentinel; else return max”—exhaust empty vs nonempty.
Is “checked all \(n\le 10^6\)” a case proof for a \(\forall n\in\mathbb{N}\) claim? Explain.

Existence hygiene checklist

Question	Why it matters
Did I exhibit a witness?	Constructive
Did I only show nonemptiness?	May be non-constructive
Is the witness in the claimed domain?	Type/universe bugs
Did I prove \(\forall\) by three examples?	Invalid

Cases without exhaustiveness and existence without domain checks are the two most common silent failures in student proofs and in design docs.

Tomorrow

Day 31 — Weak induction. Principle, well-ordering link, sums/divisibility/inequalities, loop invariant preview, common failures (horses), template.

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:

Base case: \(P(n_0)\) is true, and
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)

Define \(P(n)\) precisely (full claim for that \(n\)).
Base: prove \(P(n_0)\) by direct computation.
IH: assume \(P(k)\) for fixed arbitrary \(k \ge n_0\).
Step: prove \(P(k+1)\) using IH + algebra/definitions.
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:

true before first iteration (init),
if true before iteration and guard true, true after (maintain),
\(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)\).

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

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

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

Extended practice workshop

Template fill-ins (write full proofs)

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

Bug hunt

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

Loop invariant lite

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

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)

Prove \(\sum_{i=1}^n i^2 = n(n+1)(2n+1)/6\) with every algebra line shown.
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\)).
Prove \(1\cdot 1! + \cdots + n\cdot n! = (n+1)!-1\).
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.
Invent a false \(P\) with true base and false step; invent a false \(P\) with false base and true step.
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.