Mathematical Induction

The principle

To prove a statement P(n) holds for all natural numbers n ≥ n₀ (typically n₀ = 1):

1. Base case — verify P(n₀) is true.
2. Inductive step — assume P(k) is true for some k ≥ n₀ (the inductive hypothesis), and prove P(k+1) is true.

If both steps succeed, then P(n) is true for all n ≥ n₀.

The domino analogy

Imagine an infinite row of dominoes. Two facts together knock them all over:

• The first domino is pushed (base case).
• If the kth domino falls, it knocks the (k+1)th domino (inductive step).

Conclusion — all dominoes fall. The base case "starts" the chain; the inductive step "propagates" it.

Classic example — sum of first n integers

Claim — for all n ≥ 1, 1 + 2 + 3 + ... + n = n(n+1)/2.

Base case — n = 1: LHS = 1; RHS = 1·2/2 = 1. ✓

Inductive step — assume 1 + 2 + ... + k = k(k+1)/2 (inductive hypothesis). Show it holds for k+1:

1 + 2 + ... + k + (k+1) = k(k+1)/2 + (k+1)         [by IH]
                       = (k+1)(k/2 + 1)
                       = (k+1)(k+2)/2 ✓

By induction, the formula holds for all n ≥ 1.

Strong induction

In strong induction, the inductive step assumes P(j) for ALL j with n₀ ≤ j ≤ k (not just j = k):

1. Base case — P(n₀) true.
2. Strong inductive step — assume P(j) for all n₀ ≤ j ≤ k; prove P(k+1).

Strong induction is equivalent in logical power to weak induction (any proof using one can be converted to the other) but is often more convenient when the proof of P(k+1) needs multiple prior cases — like recurrence relations or factorization arguments.

Common induction proofs

Statement	Form	Type
1 + 2 + ... + n = n(n+1)/2	Sum formula	Weak
1² + 2² + ... + n² = n(n+1)(2n+1)/6	Sum formula	Weak
2ⁿ > n for n ≥ 1	Inequality	Weak
(1 + x)ⁿ ≥ 1 + nx for x ≥ −1, n ≥ 1	Bernoulli's	Weak
n³ − n divisible by 6	Divisibility	Weak
Every integer ≥ 2 has prime factorization	Existence	Strong
F(n) = Fibonacci closed form	Recurrence	Strong
Every chess position can reach a deterministic outcome	Game theory	Strong

Well-ordering principle

Well-ordering principle — every nonempty subset of natural numbers has a smallest element.

This is logically equivalent to induction. Each can be proved from the other using ordinary logical principles. Proofs by contradiction often invoke well-ordering — "let n be the smallest counterexample."

Generalizes to any well-ordered set — a totally ordered set where every nonempty subset has a minimum. ℕ is well-ordered; ℝ is not (no smallest positive real). Transfinite induction extends to ordinals beyond ℕ.

Structural induction — beyond ℕ

For recursively-defined structures (trees, lists, formal expressions), structural induction generalizes the principle:

1. Base case — prove for atomic structures (e.g., empty list, leaf node).
2. Inductive step — assume for all "smaller" substructures; prove for the larger structure built from them.

Used to prove:

• Properties of recursive algorithms (e.g., merge sort always produces sorted output).
• Type system soundness in programming languages.
• Theorems about formal grammars and proof trees.

JavaScript — verifying induction-proven formulas

// Verify the formula 1 + 2 + ... + n = n(n+1)/2 numerically
function sumFirstN(n) {
  let total = 0;
  for (let i = 1; i <= n; i++) total += i;
  return total;
}

function formulaSumN(n) {
  return n * (n + 1) / 2;
}

for (let n = 1; n <= 100; n++) {
  console.assert(sumFirstN(n) === formulaSumN(n), `Failed for n = ${n}`);
}
console.log('Sum formula verified for n = 1 to 100');

// Verify 1² + 2² + ... + n² = n(n+1)(2n+1)/6
function sumOfSquares(n) {
  let total = 0;
  for (let i = 1; i <= n; i++) total += i * i;
  return total;
}

function formulaSquares(n) {
  return n * (n + 1) * (2 * n + 1) / 6;
}

for (let n = 1; n <= 100; n++) {
  console.assert(sumOfSquares(n) === formulaSquares(n));
}
console.log('Sum of squares formula verified');

// Strong induction example: prime factorization
function primeFactors(n) {
  const factors = [];
  for (let p = 2; p * p <= n; p++) {
    while (n % p === 0) {
      factors.push(p);
      n /= p;
    }
  }
  if (n > 1) factors.push(n);
  return factors;
}

// FTA: every integer ≥ 2 has unique prime factorization
console.log(primeFactors(60));   // [2, 2, 3, 5]
console.log(primeFactors(2310)); // [2, 3, 5, 7, 11]

// Bernoulli's inequality: (1+x)ⁿ ≥ 1+nx for x ≥ -1, n ≥ 1
function checkBernoulli(x, n) {
  return Math.pow(1 + x, n) >= 1 + n * x - 1e-10;  // tolerance for FP
}

console.log(checkBernoulli(0.5, 10));  // true
console.log(checkBernoulli(-0.5, 5));  // true
console.log(checkBernoulli(2, 100));   // true

Where induction shows up

• Pure mathematics — proofs. Foundation for proofs by recurrence; many theorems in number theory, combinatorics, analysis.
• Algorithm correctness. Recursive algorithms (binary search, merge sort, dynamic programming) are proven correct via structural or numerical induction.
• Algorithm complexity. Solving recurrences (T(n) = 2T(n/2) + n → O(n log n)) often uses induction to verify.
• Programming language theory. Type systems, operational semantics, denotational semantics — all use structural induction over syntax/derivation trees.
• Combinatorics. Counting identities, partition theorems, Ramsey theory — proven via clever induction.
• Number theory. Prime factorization, divisibility properties, modular results often prove by strong induction.
• Computer science theory. Computability, complexity proofs, correctness of recursive data structures.

Common mistakes

• Forgetting the base case. Without the base case, the inductive step is meaningless — you've only shown the property is "self-propagating," not that it's true. Famous fallacy — "prove all horses are the same color" relies on missing or wrong base case.
• Wrong inductive hypothesis. Assume P(k) (single value), not "P(n) for all n" (which is what you're trying to prove). The hypothesis is one specific case used to prove the next.
• Inductive step missing the n+1 case. Some students prove P(k) implies P(k+2), or another offset. Only P(k) → P(k+1) covers everything (without gaps).
• Confusing induction with conjecture verification. Checking many cases (P(1), P(2), ..., P(100)) doesn't prove P(n) for all n. Induction needs the proof of "P(k) → P(k+1)" symbolically, not by checking values.
• Strong vs weak induction confusion. Weak — assume P(k); strong — assume P(1) through P(k). Use strong when the proof of P(k+1) genuinely needs earlier cases, not just k.
• Trying to use induction on real numbers. Standard induction works on ℕ or well-ordered sets. Reals don't have successors; you need different methods (continuity, limits) for real-valued statements.