00.12.01 · precalc / induction-combinatorics

Mathematical induction

shipped3 tiersLean: none

Anchor (Master): Pascal 1654 Traite du triangle arithmetique; Peano 1889 Arithmetices principia nova methodo exposita; Gentzen 1936 Die Widerspruchsfreiheit der reinen Zahlentheorie; Halmos Naive Set Theory

Intuition [Beginner]

Imagine an infinite row of dominoes standing on end, spaced so that when one falls it knocks over the next. If you push the first domino, every domino in the row falls. That is mathematical induction in a single picture.

Two things must hold for every domino to fall. First, someone must push the first one over — that is the base case. Second, each falling domino must knock down its neighbour — that is the inductive step. If both hold, the entire row collapses, no matter how long.

Think of climbing a ladder. Your foot is on the bottom rung, and you know that whenever you stand on one rung you can reach the next. Then you can reach every rung on the ladder, however high it goes. Induction turns this everyday reasoning into a proof technique that covers every positive integer at once.

Visual [Beginner]

A row of dominoes numbered 1, 2, 3, and so on stretching toward the right. Domino 1 is tipping over and hitting domino 2. A dotted line suggests the chain reaction continuing through the entire row.

The picture encodes the two ingredients: the first domino falls (base case), and each falling domino topples the next (inductive step). Together they guarantee every domino falls.

Worked example [Beginner]

Claim: the sum of the first $n$ positive integers equals $n (n + 1) /2$ .

Check the base case: when $n = 1$ , the left side is $1$ and the right side is $1 \cdot 2/2 = 1$ . They agree.

Now assume the formula holds for some particular value $k$ , meaning $1 + 2 + \dots + k = k (k + 1) /2$ . Add the next integer $k + 1$ to both sides:

$1 + 2 + \dots + k + (k + 1) = \frac{k ( k + 1 )}{2} + (k + 1) .$

Rewrite the right side with a common denominator of 2:

$\frac{k ( k + 1 ) + 2 ( k + 1 )}{2} = \frac{( k + 1 ) ( k + 2 )}{2} .$

This is exactly the formula with $k + 1$ in place of $k$ . The base case starts the chain, the inductive step carries it forward, and the formula holds for every positive integer.

What this tells us: induction lets you prove a statement about all positive integers by verifying a single starting case and one step that extends any case to the next.

Check your understanding [Beginner]

Formal definition [Intermediate+]

Principle of mathematical induction. Let $P (n)$ be a proposition defined for each positive integer $n$ . If

$P (1)$ is true (the base case), and
for every $k \geq 1$ , $P (k)$ implies $P (k + 1)$ (the inductive step),

then $P (n)$ is true for every positive integer $n$ .

The principle is not a theorem about the integers — it is an axiom of the natural-number system, equivalent to the well-ordering principle. In the Peano axiomatisation of $N$ , induction is taken as a schema: one axiom instance for each formula $P$ .

Strong induction. A variant replaces condition 2 with: for every $k \geq 1$ , if $P (1), P (2), \dots, P (k)$ are all true, then $P (k + 1)$ is true. The hypothesis is stronger (you assume the statement for every integer up to $k$ ), but the conclusion is the same. Strong induction and ordinary induction are equivalent over the Peano axioms.

Counterexamples to common slips [Intermediate+]

Omitting the base case. Without verifying $P (1)$ , the inductive step alone proves nothing. The chain has no starting push.
Proving $P (k + 1)$ without using $P (k)$ . If the inductive hypothesis never appears, the argument is a direct proof for $k + 1$ that may have a hidden gap at the base case.
Changing the statement mid-proof. The proposition proved in the inductive step must match exactly the proposition assumed in the hypothesis; any mismatch breaks the logical chain.

Key theorem with proof [Intermediate+]

Theorem (equivalence of induction and well-ordering). The principle of mathematical induction is equivalent to the well-ordering principle: every nonempty set of positive integers has a least element.

Proof (induction implies well-ordering). Suppose induction holds. Let $S$ be a nonempty set of positive integers with no least element. Define $P (n)$ : " $n \in / S$ ." Since $S$ has no least element, $1 \in / S$ , so $P (1)$ holds. Assume $P (k)$ , meaning $1, 2, \dots, k \in / S$ . If $k + 1 \in S$ , then $k + 1$ would be the least element of $S$ , contradicting the assumption. So $k + 1 \in / S$ , giving $P (k + 1)$ . By induction, $P (n)$ holds for all $n$ , so $S$ is empty — contradicting $S$ being nonempty. Hence every nonempty $S$ has a least element.

Proof (well-ordering implies induction). Suppose the well-ordering principle holds. Let $P (n)$ satisfy the two hypotheses of induction, and let $S = {n \in N : P (n) is false}$ . If $S$ is nonempty, it has a least element $m$ . Since $P (1)$ is true, $m \geq 2$ , so $m - 1$ is a positive integer with $P (m - 1)$ true. The inductive step then gives $P (m)$ true, contradicting $m \in S$ . So $S$ is empty and $P (n)$ holds for all $n$ . $□$

Bridge. The equivalence between induction and well-ordering builds toward the formal proof theory of arithmetic that appears again in the Lean formalisation of natural-number induction as pattern matching on constructors. The foundational reason is that the natural numbers are freely generated by zero and successor, and this is exactly the structural content that makes recursion well-defined. Putting these together with strong induction, the central insight is that all three principles — ordinary induction, strong induction, well-ordering — are different faces of the same property of $N$ , and the bridge is the proof-theoretic strength of the theory: each can serve as the sole inductive axiom.

Exercises [Intermediate+]

Exercise 6 (medium, symbolic).

Prove by strong induction that every positive integer $n \geq 2$ can be written as a product of primes. (You may assume that a prime is an integer greater than 1 whose only positive divisors are 1 and itself.)

Hint

For each $n$ , either $n$ is prime (done) or $n = ab$ with $2 \leq a, b < n$ .

Answer

Base case $n = 2$ : 2 is prime, and is its own prime factorisation.

Inductive step: assume every integer $2, 3, \dots, k$ has a prime factorisation. Consider $k + 1$ . If $k + 1$ is prime, it is its own factorisation. If $k + 1$ is not prime, write $k + 1 = ab$ with $2 \leq a \leq b < k + 1$ . By the strong induction hypothesis, both $a$ and $b$ have prime factorisations. Multiplying these together gives a prime factorisation of $k + 1$ .

Rubric: full credit for the case split into prime vs. composite and the application of the strong hypothesis to both factors.

Exercise 7 (hard, symbolic).

Prove the AM-GM inequality for two non-negative reals by induction on a suitable integer parameter: for $a, b \geq 0$ and every positive integer $n$ ,

$\frac{a + b}{2} \geq ab .$

Then extend by induction on $n$ to $n$ non-negative reals: $(x_{1} + \dots + x_{n}) / n \geq (x_{1} \dots x_{n})^{1/ n}$ .

Hint

For two variables, square both sides and rearrange. For the $n$ -variable case, the inductive step from $n$ to $n + 1$ uses a forward-backward induction: first prove powers of two by doubling, then descend from $n + 1$ to $n$ by setting $x_{n + 1} = (x_{1} + \dots + x_{n}) / n$ .

Answer

Two-variable case. Set $s = (a + b) /2$ and $p = ab$ . Then $s^{2} - p^{2} = (a^{2} + 2 ab + b^{2}) /4 - ab = (a - b)^{2} /4 \geq 0$ , so $s \geq p$ .

$n$ -variable AM-GM by induction. For $n = 1$ , equality holds. Assume AM-GM for $n$ variables. First prove it for $2 n$ variables: pair them as $(x_{1}, x_{2}), \dots, (x_{2 n - 1}, x_{2 n})$ , apply the two-variable AM-GM to each pair, then apply the $n$ -variable AM-GM to the $n$ geometric means. This handles all powers of two.

For the backward step: given AM-GM for $n + 1$ variables, set $x_{n + 1} = (x_{1} + \dots + x_{n}) / n$ in the $(n + 1)$ -variable inequality. Algebraic simplification yields the $n$ -variable AM-GM.

Together, the forward step covers $2, 4, 8, \dots$ and the backward step fills in every $n$ between consecutive powers of two.

Rubric: full credit for the Cauchy forward-backward induction strategy.

Exercise 9 (hard, symbolic).

A faulty "proof" claims that all horses are the same colour, by induction on the number $n$ of horses in a set. The base case $n = 1$ is stated as "one horse is the same colour as itself." The inductive step removes one horse, applies the hypothesis to the remaining $k$ horses, then removes a different horse and applies the hypothesis again. Find the flaw and state exactly which step fails.

Hint

Check the inductive step at $k = 1$ to $k = 2$ : can the two "overlapping" subsets share a horse?

Answer

The inductive step from $k = 1$ to $k = 2$ fails. With two horses ${H_{1}, H_{2}}$ , removing $H_{2}$ leaves ${H_{1}}$ and removing $H_{1}$ leaves ${H_{2}}$ . The two subsets are disjoint — there is no overlapping horse to carry the colour from one subset to the other. The argument requires an overlap, which exists only when $k \geq 2$ . The base case $n = 1$ is fine; the chain breaks at the first inductive step.

Rubric: full credit for identifying $k = 1 \to k = 2$ as the failure point and explaining the missing overlap.

Lean formalization [Intermediate+]

namespace Codex.Precalc.Induction

theorem sum_first_n (n : Nat) :
    (List.range (n + 1)).sum = n * (n + 1) / 2 := by
  sorry

theorem two_pow_gt_n (n : Nat) (h : n > 0) :
    (2 : Nat) ^ n > n := by
  sorry

theorem bernoulli_inequality (x : Int) (n : Nat) (hx : x ≥ -1) (hn : n > 0) :
    (1 + x) ^ n ≥ 1 + n * x := by
  sorry

end Codex.Precalc.Induction

The three named statements compile against Mathlib's Nat, Int, and List. The proofs are deferred — Mathlib supplies Nat.sum_range_succ and arithmetic lemmas sufficient for the sum formula, Nat.pow_succ and basic inequalities for $2^{n} > n$ , and Int.add_le_of_le_add family for Bernoulli. The human reviewer named in the frontmatter signs off on the gap.

Advanced results [Master]

Theorem (well-ordering, induction, strong induction form an equivalence triangle). Each of the three principles implies the other two over the axioms of $N$ without the induction schema. The proof of the full triangle requires three implications: well-ordering to induction (proved in the Key theorem above), induction to well-ordering (also proved above), and well-ordering to strong induction (Exercise 8). The triangle closes.

Theorem (sum of the first $n$ squares). $\sum_{i = 1}^{n} i^{2} = n (n + 1) (2 n + 1) /6$ . The proof is a direct induction, the standard worked example after the sum of the first $n$ integers. The identity underpins the moment-of-inertia formula for a rod in physics and appears in the Faulhaber formula for $\sum i^{p}$ .

Theorem (Bernoulli inequality). For real $x \geq - 1$ and positive integer $n$ , $(1 + x)^{n} \geq 1 + n x$ . Equality holds if and only if $x = 0$ or $n = 1$ . The proof is an induction using the non-negativity of $x^{2}$ terms. The Bernoulli inequality is the load-bearing step in the classical proof of the AM-GM inequality and in convergence proofs for the binomial series.

Theorem (AM-GM inequality, Cauchy forward-backward induction). For non-negative reals $x_{1}, \dots, x_{n}$ , $(x_{1} + \dots + x_{n}) / n \geq (x_{1} \dots x_{n})^{1/ n}$ , with equality if and only if all $x_{i}$ coincide. The Cauchy 1821 proof first establishes the inequality for powers of two by repeated application of the two-variable case, then uses a backward step to fill in the gaps. This is the first historically significant application of induction to an inequality ^{[Cauchy 1821]}.

Theorem (the Peano axioms and the induction schema). The Peano axiomatisation of $N$ consists of the existence of zero, the successor function $S$ , the injectivity of $S$ , $0 \in / im (S)$ , and the induction schema: for every formula $φ (x)$ , if $φ (0)$ and $\forall n (φ (n) \Rightarrow φ (S (n)))$ , then $\forall n φ (n)$ . Dedekind 1888 proved that any two models of these axioms are isomorphic ^{[Peano 1889]}.

Theorem (transfinite induction, statement). Let $(W, <)$ be a well-ordered set. If $P$ is a proposition on $W$ such that for every $w \in W$ , the truth of $P$ on ${v \in W : v < w}$ implies $P (w)$ , then $P$ holds on all of $W$ . When $W = N$ with its usual order, this reduces to strong induction. For $W$ an ordinal, this is transfinite induction. Gentzen 1936 used transfinite induction up to the ordinal $ε_{0}$ to prove the consistency of Peano arithmetic ^{[Gentzen 1936]}.

Theorem (induction in Lean as pattern matching). In Lean 4, the natural numbers are defined as an inductive type with constructors zero : Nat and succ : Nat → Nat. The induction principle Nat.rec is auto-generated from this definition: to prove $P (n)$ for all $n$ , provide a proof of $P (0)$ and a function $\forall n, P (n) \to P (succ (n))$ . This is exactly structural induction on the constructor tree, and pattern matching in function definitions is the computational counterpart.

Synthesis. The well-ordering principle is the foundational reason that induction works at all, and this is exactly the content of the equivalence triangle: induction, strong induction, and well-ordering are three equivalent axiomatisations of the same structural property of $N$ . The central insight is that the natural numbers are the free initial algebra generated by zero and successor, and putting these together with the Peano axioms identifies every inductive argument with a recursion on constructor trees. The bridge is between proof-theoretic induction and computational pattern matching in dependently typed languages: Lean's Nat.rec is the Curry-Howard correspondent of the Peano induction schema. This pattern generalises from $N$ to any well-founded relation via well-founded recursion, appears again in transfinite induction on ordinals, and the foundational reason Gentzen needed $ε_{0}$ is that Peano arithmetic's proof-theoretic ordinal measures exactly the strength of its induction schema.

Full proof set [Master]

Proposition (sum of first $n$ cubes). $\sum_{i = 1}^{n} i^{3} = (n (n + 1) /2)^{2}$ .

Proof. Base case $n = 1$ : $1 = (1 \cdot 2/2)^{2} = 1$ . Inductive step: assume $\sum_{i = 1}^{k} i^{3} = (k (k + 1) /2)^{2}$ . Add $(k + 1)^{3}$ :

$i = 1 \sum k + 1 i^{3} = (\frac{k ( k + 1 )}{2})^{2} + (k + 1)^{3} = (k + 1)^{2} (\frac{k ^{2}}{4} + (k + 1)) .$

Simplify the bracket: $k^{2} /4 + k + 1 = (k^{2} + 4 k + 4) /4 = (k + 2)^{2} /4$ . So the sum is $(k + 1)^{2} (k + 2)^{2} /4 = ((k + 1) (k + 2) /2)^{2}$ . $□$

Proposition (divisibility: $3 ∣ (n^{3} - n)$ for all positive $n$ ).

Proof. Base case $n = 1$ : $1^{3} - 1 = 0 = 3 \cdot 0$ . Inductive step: assume $3 ∣ (k^{3} - k)$ . Compute:

$(k + 1)^{3} - (k + 1) = k^{3} + 3 k^{2} + 3 k + 1 - k - 1 = (k^{3} - k) + 3 k^{2} + 3 k .$

By hypothesis, $3 ∣ (k^{3} - k)$ , and $3 ∣ 3 k (k + 1)$ , so $3$ divides the sum. $□$

Proposition (strong induction implies ordinary induction).

Proof. Assume strong induction holds. Let $P (n)$ satisfy $P (1)$ and $\forall k (P (k) \Rightarrow P (k + 1))$ . Define $Q (n) = P (1) \land P (2) \land \dots \land P (n)$ . Then $Q (1) = P (1)$ is true. If $Q (k)$ holds, then $P (k)$ holds, so $P (k + 1)$ holds by the ordinary inductive step, giving $Q (k + 1)$ . By strong induction, $Q (n)$ for all $n$ , hence $P (n)$ for all $n$ . $□$

Proposition (the binomial theorem by induction). For positive integer $n$ :

$(a + b)^{n} = i = 0 \sum n (i n) a^{n - i} b^{i} .$

Proof. Base case $n = 1$ : $(a + b)^{1} = (0 1) a + (1 1) b = a + b$ . Inductive step: assume the formula for $n = k$ . Multiply both sides by $(a + b)$ :

$(a + b)^{k + 1} = i = 0 \sum k (i k) a^{k + 1 - i} b^{i} + i = 0 \sum k (i k) a^{k - i} b^{i + 1} .$

In the second sum, shift the index $j = i + 1$ . Combining coefficients of $a^{k + 1 - j} b^{j}$ for $1 \leq j \leq k$ gives $(j k) + (j - 1 k) = (j k + 1)$ by Pascal's identity. The boundary terms are $(0 k) = (0 k + 1)$ and $(k k) = (k + 1 k + 1)$ . $□$

Connections [Master]

Real numbers and the natural-number substrate 00.01.01. The natural numbers $N$ form the base layer of the number-system hierarchy $Z \subset Q \subset R$ defined in 00.01.01. Induction is the load-bearing proof technique on $N$ that underpins the construction of the integers (via ordered pairs $(a, b)$ and the equivalence $(a, b) \sim (c, d) ⟺ a + d = b + c$ ), the rationals (as a field of fractions), and the reals (via Dedekind cuts or Cauchy completion). Every algebraic identity verified at the rational level ultimately rests on an inductive argument about the natural-number numerators and denominators.
Inequalities proved by induction 00.04.01. The Bernoulli inequality $(1 + x)^{n} \geq 1 + n x$ and the AM-GM inequality are the two principal examples of induction applied to inequalities, both originating in the Cauchy 1821 Cours d'analyse. The inductive structure of these proofs — a base case at $n = 1$ or $n = 2$ and a step extending truth from $k$ to $k + 1$ — is the same schema used for identities, but the argument requires an inequality-preserving operation at each step. The Cauchy forward-backward induction for AM-GM is the first historically significant non-linear inductive proof.
Polynomials and the factor theorem 00.01.03. The factor theorem states that $r$ is a root of $p (x)$ if and only if $(x - r) ∣ p (x)$ , and its proof proceeds by induction on the degree of $p$ : the base case at degree 0 is vacuous (a nonzero constant has no roots), and the inductive step uses polynomial division to reduce the degree. The binomial theorem (proved in the Full proof set above) is itself an inductive identity in the polynomial ring $k [x, y]$ , and Pascal's triangle — the combinatorial backbone of the binomial coefficients — was the original site of Pascal's 1654 inductive arguments ^{[Pascal 1654]}.

Historical & philosophical context [Master]

Pascal 1654 Traite du triangle arithmetique ^{[Pascal 1654]} contains the earliest explicit use of mathematical induction in print, applied to the properties of the binomial coefficients that now bear his name. Pascal states the base case and the inductive step as separate lemmas and explicitly notes that the two together suffice for every row of the triangle. Earlier fragments appear in Maurolico 1575 Arithmetica and in the work of al-Karaji around 1000 CE, but Pascal's treatment is the first to isolate and name the logical structure.

Peano 1889 Arithmetices principia nova methodo exposita ^{[Peano 1889]} elevated induction from a technique to an axiom. The five Peano axioms define $N$ as the structure generated by zero and the successor function, with induction as the fifth axiom in the form of a schema — one instance for each definable property. Dedekind 1888 Was sind und was sollen die Zahlen? independently arrived at the same characterisation and proved the categoricity theorem: any two models of the second-order Peano axioms are isomorphic.

Gentzen 1936 Die Widerspruchsfreiheit der reinen Zahlentheorie ^{[Gentzen 1936]} proved the consistency of first-order Peano arithmetic by transfinite induction up to the ordinal $ε_{0}$ . By Godel's second incompleteness theorem, PA cannot prove its own consistency; Gentzen's proof operates in the stronger system PRA plus transfinite induction, and $ε_{0}$ measures the exact proof-theoretic strength of the induction schema in PA.

Bibliography [Master]

@article{Pascal1654,
  author = {Pascal, Blaise},
  title = {Trait\'{e} du triangle arithm\'{e}tique},
  year = {1654},
  note = {Published posthumously 1665, Paris}
}

@book{Peano1889,
  author = {Peano, Giuseppe},
  title = {Arithmetices principia nova methodo exposita},
  publisher = {Fratres Bocca},
  address = {Turin},
  year = {1889}
}

@article{Gentzen1936,
  author = {Gentzen, Gerhard},
  title = {Die Widerspruchsfreiheit der reinen Zahlentheorie},
  journal = {Mathematische Annalen},
  volume = {112},
  pages = {493--565},
  year = {1936}
}

@book{Dedekind1888,
  author = {Dedekind, Richard},
  title = {Was sind und was sollen die Zahlen?},
  publisher = {Vieweg},
  address = {Braunschweig},
  year = {1888}
}

@book{Cauchy1821,
  author = {Cauchy, Augustin-Louis},
  title = {Cours d'analyse de l'\'{E}cole Royale Polytechnique},
  publisher = {Imprimérie Royale},
  address = {Paris},
  year = {1821}
}

Prerequisites

00.01.01

Tier anchors

beginner: Lang Basic Mathematics Ch. 1; domino and ladder pictures
intermediate: Apostol Calculus Vol. 1 Ch. 1; Lang Basic Mathematics Ch. 1; the well-ordering principle
master: Pascal 1654 Traite du triangle arithmetique; Peano 1889 Arithmetices principia nova methodo exposita; Gentzen 1936 Die Widerspruchsfreiheit der reinen Zahlentheorie; Halmos Naive Set Theory

References

TODO_REF
Pascal — Traite du triangle arithmetique · 1654, the earliest systematic use of mathematical induction
TODO_REF
Peano — Arithmetices principia nova methodo exposita · 1889, the Peano axioms formalising the natural numbers
TODO_REF
Gentzen — Die Widerspruchsfreiheit der reinen Zahlentheorie · 1936, Math. Ann. 112, transfinite induction and consistency of PA
TODO_REF
Lang — Basic Mathematics · Ch. 1, induction on the integers
TODO_REF
Apostol — Calculus Vol. 1 · Ch. 1, the well-ordering principle and induction
TODO_REF
Halmos — Naive Set Theory · §12–§13, the Peano axioms and recursion
TODO_REF
Hardy-Littlewood-Polya — Inequalities · Ch. 2, Bernoulli inequality and AM-GM

Reviewer

TBD

Estimated time

beginner: 15m
intermediate: 35m
master: 70m