Mathematical Induction & Recursion

Every non-empty set of natural numbers has a smallest element.

This single sentence is the bedrock on which all of induction rests. It sounds obvious — of course a bunch of whole numbers has a smallest one — but its implications are profound. It is what makes the natural numbers fundamentally different from, say, the positive rationals (between any two rationals there is another, so no smallest element exists in an open interval).

Formally: if S ⊆ ℕ and S ≠ ∅, then there exists m ∈ S such that m ≤ s for all s ∈ S.

Why does this imply induction? Suppose you want to prove P(n) holds for all n ∈ ℕ. Imagine, for contradiction, that some natural numbers fail P. Let F = {n ∈ ℕ : P(n) is false}. If F ≠ ∅, by well-ordering it has a smallest element m. Now: if you can show that m cannot exist (i.e., there is no smallest counterexample), then F must be empty and P holds for all n. That "no smallest counterexample" argument is precisely what the base case and inductive step establish in an induction proof.

The well-ordering principle is equivalent to mathematical induction — they are logically the same axiom stated differently. Understanding this equivalence helps you see induction not as a magic trick but as a theorem about the structure of the natural numbers.

Example: proof that every integer n ≥ 2 has a prime factor. Suppose not — let S = {n ≥ 2 : n has no prime factor}. If S ≠ ∅, let m be the smallest element. Since m ∈ S, m is not prime, so m = ab with 1 < a, b < m. Since a < m and m was the smallest element of S, a ∉ S, so a has a prime factor p. But p | a | m, so m has a prime factor — contradiction. Hence S = ∅.

# Well-ordering in action: finding the smallest counterexample to debug
# If an invariant ever fails, WOP guarantees a first failure step.

def find_first_failure(predicate, max_n=1000):
    """Find the smallest n in [0, max_n] where predicate fails."""
    for n in range(max_n + 1):
        if not predicate(n):
            return n  # smallest counterexample, guaranteed by WOP
    return None  # no failure found

# Example: test if sum of first n odds = n^2
print(find_first_failure(lambda n: sum(range(1,2*n,2)) == n**2, 100))
# prints None — the claim holds for all tested n

The standard template for proving P(n) holds for all integers n ≥ n₀.

Weak induction has two parts:

1. Base case: Prove P(n₀) directly.
2. Inductive step: Prove that for all k ≥ n₀, if P(k) holds (the inductive hypothesis), then P(k+1) holds.

Once both parts are established, you conclude P(n) for all n ≥ n₀.

The domino analogy: imagine an infinite row of dominoes, one for each natural number. The base case knocks over domino n₀. The inductive step says "whenever domino k has fallen, it knocks over domino k+1." Together, every domino eventually falls.

Key worked example: the sum of the first n positive 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 the formula holds for some k ≥ 1 (IH: 1+2+⋯+k = k(k+1)/2). We want to show it holds for k+1:

1 + 2 + ⋯ + k + (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 [this is exactly the formula for n = k+1] ✓

Common pitfalls: (1) Forgetting the base case — the inductive step alone proves nothing. (2) Circular reasoning in the inductive step — you must use the IH to prove P(k+1), not assume it. (3) Starting the base case too late — if the formula first holds at n=5, start there.

The three-column proof format (used at MIT 6.042 and Stanford CS103):

# Induction proof mirrored as a recursive function + its correctness argument

def gauss_sum(n: int) -> int:
    """Returns 1 + 2 + ... + n.
    
    Correctness proof by induction:
    Base case: gauss_sum(0) = 0 = 0*1/2. ✓
    IH: gauss_sum(k) = k*(k+1)//2.
    Step: gauss_sum(k+1) = (k+1) + gauss_sum(k)  [by definition]
                         = (k+1) + k*(k+1)//2      [by IH]
                         = (k+1)*(k+2)//2           [algebra] ✓
    """
    if n == 0:
        return 0            # base case
    return n + gauss_sum(n - 1)  # inductive step

# Verify against closed form
for n in range(20):
    assert gauss_sum(n) == n * (n + 1) // 2

Sometimes proving P(k+1) requires not just P(k) but P(0), P(1), ..., P(k) — all the cases up to k.

Strong induction modifies the inductive hypothesis: instead of assuming only P(k), you assume P(j) for all j with n₀ ≤ j ≤ k, and then prove P(k+1).

Formal template:

• Base case: Prove P(n₀) (sometimes multiple base cases are needed).
• Inductive step: For arbitrary k ≥ n₀, assume P(j) holds for all n₀ ≤ j ≤ k. Prove P(k+1).

Why is this still valid? Strong induction is logically equivalent to weak induction and to the well-ordering principle. You can derive strong from weak: define Q(k) = "P(j) holds for all j ≤ k"; then Q satisfies weak induction, and Q(k) implies P(k).

Key worked example: every integer n ≥ 2 has a prime factorization.

Weak induction would fail here because to factor n, you might split it as a·b where a and b are far from n−1. Strong induction lets you use the IH on any value smaller than n.

Base case (n=2): 2 is prime, so its factorization is just {2}. ✓

Inductive step: Assume every integer j with 2 ≤ j ≤ k has a prime factorization. Consider k+1. Either k+1 is prime (factorization = {k+1}), or k+1 = a·b with 2 ≤ a, b < k+1. By IH, both a and b have prime factorizations; combining them gives a prime factorization of k+1. ✓

Another key example: Fibonacci — computing fib(n) in linear time by strong IH. When analyzing the recursion T(n) = T(n−1) + T(n−2) + O(1), you need both T(n−1) and T(n−2) to be O(n), requiring the hypothesis for all values up to k, not just k itself.

When to use strong vs. weak induction: Use strong induction whenever your inductive step naturally wants to reach back more than one step — recursive algorithms with non-adjacent sub-problems (like divide-and-conquer), proofs about game trees, dynamic programming correctness.

def fib(n: int) -> int:
    """Naive exponential-time Fibonacci — illustrates where strong IH is needed."""
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)  # needs BOTH prior values

# Closed form check (strong IH proof: fib(n) = (phi^n - psi^n)/sqrt(5))
import math
phi = (1 + math.sqrt(5)) / 2
psi = (1 - math.sqrt(5)) / 2

def fib_closed(n: int) -> int:
    return round((phi**n - psi**n) / math.sqrt(5))

# Strong induction proof structure mirrors the two-base-case recursion:
# Base: fib(0)=0, fib(1)=1  -- TWO base cases because recurrence looks back 2
# IH:  fib(j) = closed_form(j) for all j <= k  (strong hypothesis)
# Step: fib(k+1) = fib(k) + fib(k-1) = cf(k) + cf(k-1) = cf(k+1)  [by IH + algebra]
for n in range(15):
    assert fib(n) == fib_closed(n)

A recursive (inductive) definition defines an object in terms of simpler instances of itself, with explicit base cases.

This is the "definition side" of the induction coin. Just as induction lets you prove things about all natural numbers, recursive definitions let you define functions, sets, and data structures for all natural numbers (or all members of a recursive structure).

A recursive definition has two parts:

1. Base cases: explicit values for the smallest inputs.
2. Recursive cases: rules that construct/define larger instances from smaller ones.

Example 1: Factorial.

• 0! = 1 (base)
• n! = n · (n−1)! for n ≥ 1 (recursive)

Example 2: The set of all binary strings.

• ε ∈ Σ* (ε = empty string)
• If w ∈ Σ*, then w0 ∈ Σ* and w1 ∈ Σ*

This defines an infinite set using a finite description. Every string is reachable by finitely many applications of the rules from the base case.

Example 3: Binary trees (as a type in Haskell).

The Haskell type definition is literally a recursive definition: a tree is either a leaf, or a node with two subtrees.

Example 4: The set of well-formed arithmetic expressions.

• Any integer literal is a WFE
• If e₁, e₂ are WFEs, then (e₁ + e₂), (e₁ × e₂) are WFEs

This is exactly how parser grammars work. Every real programming language is defined by a recursive grammar, and every compiler relies on structural induction to reason about programs.

The deep connection: whenever you have a recursive definition, you automatically get a proof technique (structural induction) that matches the shape of the definition. This is not a coincidence — it is the core principle of inductive types in type theory and functional programming.

-- Haskell: recursive type definition mirrors inductive definition exactly
data Tree a = Leaf | Node (Tree a) a (Tree a)

-- height is defined by recursion, proved correct by structural induction
height :: Tree a -> Int
height Leaf         = 0                          -- base case
height (Node l _ r) = 1 + max (height l) (height r)  -- recursive case

-- size (number of nodes)
size :: Tree a -> Int
size Leaf         = 0
size (Node l _ r) = 1 + size l + size r

-- Claim: size t <= 2^(height t) - 1  for all trees t
-- Proof by structural induction on t:
--   Base: size Leaf = 0 <= 2^0 - 1 = 0. ✓
--   IH:   size l <= 2^h_l - 1,  size r <= 2^h_r - 1
--   Step: size (Node l _ r) = 1 + size l + size r
--                           <= 1 + (2^h_l-1) + (2^h_r-1)  [by IH]
--                           <= 2^(1+max h_l h_r) - 1       [algebra] ✓

Structural induction is induction over the shape of a recursively defined structure, not over the natural numbers.

The principle: to prove P(x) for all members x of a recursively defined set S:

1. Prove P(b) for each base-case element b of S.
2. For each constructor rule "if x₁,...,xₙ ∈ S then f(x₁,...,xₙ) ∈ S", prove: if P(x₁),...,P(xₙ) hold (IH), then P(f(x₁,...,xₙ)) holds.

Why does this work? Every element of S was built from base cases by finitely many constructor applications. The well-foundedness of recursive definitions (you can always count the number of constructor applications to build any element — it's a natural number!) reduces structural induction to ordinary induction.

Worked example: proving a property of binary trees.

Claim: Every full binary tree (every internal node has exactly 2 children) with n internal nodes has n+1 leaves.

Base case: A tree with 0 internal nodes is a single leaf. Leaves = 1 = 0+1. ✓

Inductive step: Consider a full binary tree T with a root and left subtree L and right subtree R. Let L have iₗ internal nodes and R have iᵣ internal nodes, so T has iₗ + iᵣ + 1 internal nodes.

By IH (applied to both L and R):

• Leaves(L) = iₗ + 1
• Leaves(R) = iᵣ + 1

Leaves(T) = Leaves(L) + Leaves(R) = (iₗ+1) + (iᵣ+1) = iₗ+iᵣ+2 = (iₗ+iᵣ+1) + 1. ✓

Worked example: proving a property of arithmetic expressions.

Claim: Every WFE built by our grammar above is fully parenthesized (every binary operation is surrounded by parentheses).

Base case: integer literals have no operators — trivially fully parenthesized. ✓

Inductive step: If e₁ and e₂ are fully parenthesized WFEs (IH), then (e₁ + e₂) places outermost parentheses around the operation, and e₁, e₂ are fully parenthesized by IH. ✓

Structural induction on lists (used constantly in functional programming): To prove P holds for all lists:

• Prove P([]) (empty list).
• Prove: if P(xs) holds (IH), then P(x:xs) holds for any element x.

# Structural induction in Python: prove map(f, map(g, xs)) == map(f∘g, xs)
# We prove this by structural induction on lists.

from typing import TypeVar, Callable, List
A = TypeVar('A'); B = TypeVar('B'); C = TypeVar('C')

def my_map(f: Callable, xs: List) -> List:
    if not xs:            # base case: empty list
        return []
    return [f(xs[0])] + my_map(f, xs[1:])   # recursive case: x : rest

# Proof sketch (structural induction on xs):
# Base: my_map(f, my_map(g, []))
#     = my_map(f, [])    [base case of my_map]
#     = []               [base case again]
#     = my_map(f∘g, [])  [base case] ✓
#
# IH: my_map(f, my_map(g, xs)) == my_map(f∘g, xs) for some xs
# Step: my_map(f, my_map(g, x:xs))
#     = my_map(f, [g(x)] + my_map(g, xs))  [recursive case of inner map]
#     = [f(g(x))] + my_map(f, my_map(g, xs))  [recursive case of outer map]
#     = [f(g(x))] + my_map(f∘g, xs)          [by IH]
#     = [(f∘g)(x)] + my_map(f∘g, xs)         [definition of ∘]
#     = my_map(f∘g, x:xs)                     [recursive case] ✓

compose = lambda f, g: lambda x: f(g(x))
xs = [1,2,3,4,5]
assert my_map(lambda x: x*2, my_map(lambda x: x+1, xs)) == \
       my_map(compose(lambda x: x*2, lambda x: x+1), xs)

Induction is how you prove that a program does what it is supposed to do, not just for the inputs you tested, but for all valid inputs.

There are two main patterns:

Pattern 1: Proving recursive functions correct by induction on input size.

The proof structure mirrors the code structure exactly:

• Base case of proof ↔ base case of recursion
• Inductive hypothesis ↔ the recursive call works correctly (by IH, since the input is smaller)
• Inductive step ↔ the combining step in the code is correct

This is not a coincidence. Correctness proofs for recursive programs and inductive proofs have the same shape because recursion is induction.

Pattern 2: Loop invariants (induction over iteration count).

A loop invariant is a predicate P(i) such that:

• Initialization: P(0) holds before the loop starts.
• Maintenance: if P(i) holds at the start of iteration i, then P(i+1) holds at the end.
• Termination: when the loop terminates (say at iteration n), P(n) together with the termination condition implies the postcondition.

This is exactly induction! The iteration count plays the role of n.

Worked example: binary search.

binary_search(A, target):
  lo, hi = 0, len(A)-1
  while lo <= hi:
    mid = (lo + hi) // 2
    if A[mid] == target: return mid
    elif A[mid] < target: lo = mid+1
    else: hi = mid-1
  return -1

Loop invariant: "If target is in A, it is in A[lo..hi]."

Initialization: before the loop, A[lo..hi] = A[0..n-1] = all of A. If target is in A, it is here. ✓

Maintenance: Suppose the invariant holds — target is in A[lo..hi] if anywhere. We check A[mid]. If A[mid] < target, then since A is sorted, target must be in A[mid+1..hi]. Setting lo=mid+1 preserves the invariant. Similarly for A[mid] > target. ✓

Termination: When lo > hi, A[lo..hi] is empty, so by the invariant target is not in A — return -1 is correct. Or we returned mid when A[mid] == target. ✓

Why this matters: loop invariants are how NASA verifies flight software, how CompCert verifies a production C compiler, and how AWS verifies the TLS implementation in the S2N library. The discipline starts here.

def insertion_sort(A: list) -> list:
    """Sort A in place.
    
    Loop invariant: after i iterations,
    A[0..i-1] contains the i smallest elements of the original A,
    in sorted order.
    
    Proof by induction on i:
    Base (i=0): A[0..-1] is empty — trivially sorted. ✓
    IH: A[0..i-1] is sorted and contains the i smallest elements.
    Step: We insert A[i] into A[0..i-1] at the correct position.
      - The inner while loop shifts elements right until we find
        the correct position j where A[j-1] <= A[i] <= A[j].
      - After insertion, A[0..i] contains the i+1 smallest elements,
        sorted. ✓  (by IH + the fact that insertion preserves order)
    Termination (i = len(A)): A[0..len(A)-1] = all elements, sorted. ✓
    """
    A = A[:]  # don't mutate input
    for i in range(1, len(A)):
        key = A[i]
        j = i - 1
        while j >= 0 and A[j] > key:  # shift right
            A[j + 1] = A[j]
            j -= 1
        A[j + 1] = key
    return A

assert insertion_sort([5, 2, 4, 6, 1, 3]) == [1, 2, 3, 4, 5, 6]

Induction can go wrong in subtle ways. Here are the classic traps, and how to recognize them.

Pitfall 1: The fake proof that all horses are the same color.

Claim (FALSE): All horses in any group of n horses have the same color.

"Proof": Base case (n=1): trivially true. Inductive step: suppose all groups of k horses are monochromatic. Take a group of k+1 horses: h₁,...,hₖ₊₁. By IH, h₁,...,hₖ are the same color. By IH, h₂,...,hₖ₊₁ are the same color. So all k+1 horses are the same color.

The flaw: when k=1 (base case), the two overlapping subsets are {h₁} and {h₂} — they do not overlap! The argument requires k ≥ 2. This is a classic example of an inductive step that fails for the transition from the base case to the next case.

Lesson: Always verify that your inductive step works for the smallest case (base → base+1), not just for "large k."

Pitfall 2: Assuming what you are trying to prove (circular IH).

In the inductive step, you may assume P(k) to prove P(k+1). You may NOT assume P(k+1) to prove P(k+1) — that is circular.

Pitfall 3: Missing base cases.

Some recursive definitions need multiple base cases (e.g., Fibonacci needs fib(0) and fib(1)). Omitting one can leave the induction without a starting point for some cases.

Pitfall 4: Wrong induction variable.

Sometimes the obvious induction variable is not the right one. A common fix: induct on a different measure of "size" (total size of input, depth of recursion tree, etc.).

Pitfall 5: Off-by-one in the inductive step.

Ensure your inductive step proves P(k+1) assuming P(k), not P(k−1) or some other shifted version.

Pitfall 6: Implicit use of strong induction when you only stated weak.

If in your inductive step you use P(k−5) but only stated "assume P(k)," you have silently switched to strong induction. Be explicit about which form you are using.

The best defense: write your proof in the three-column format with explicit justifications for every step. If you ever write "by IH" for something that is not exactly your stated IH, stop and investigate.

# Demonstrating the horse fallacy computationally
# The bug: overlapping subsets do NOT cover k=1->2 transition

def monochromatic_subsets(k):
    """Show that for k+1 horses, the two subsets of size k
    only overlap when k >= 2."""
    horses = list(range(1, k + 2))  # k+1 horses: [1, 2, ..., k+1]
    left  = horses[:k]               # h_1 ... h_k
    right = horses[1:]               # h_2 ... h_{k+1}
    overlap = set(left) & set(right)
    print(f"k={k}: left={left}, right={right}, overlap={overlap}")
    return len(overlap) > 0

for k in range(1, 5):
    monochromatic_subsets(k)
# k=1: left=[1], right=[2], overlap=set()  <-- BUG! No overlap at k=1
# k=2: left=[1,2], right=[2,3], overlap={2}
# k=3: left=[1,2,3], right=[2,3,4], overlap={2,3}
# The inductive step requires overlap to argue shared color.
# It fails exactly at the critical base->next transition.

The deepest insight of this module: induction and recursion are the same mathematical idea viewed from two different angles.

When you write a recursive function, you are implicitly asserting: "the function terminates and returns the correct answer for input n, assuming it terminates and returns the correct answer for all smaller inputs." That assumption is the inductive hypothesis. The base case of the recursion is the base case of the induction.

This unity is made precise in two ways:

1. The principle of recursive definition. In set theory and type theory, you can define a function f : ℕ → X by:

• f(0) = c (base case)
• f(n+1) = g(n, f(n)) (recursive case)

The Recursion Theorem (a theorem of ZFC set theory) guarantees that such a definition uniquely determines f. This theorem is proved using the well-ordering principle — it is induction in disguise.

2. Inductive types in type theory. In Coq, Lean, and Haskell, data types are defined inductively. A value of type List A is either Nil (base case) or Cons(h, t) where t : List A (recursive case). The type system guarantees that pattern matching is exhaustive and that recursive functions terminate (for the right class of functions). Proofs about these types are structural inductions.

3. Recurrence relations. When you analyze the time complexity T(n) of a recursive algorithm, you write a recurrence:

T(n) = 2T(n/2) + O(n) [merge sort]

Solving this recurrence (e.g., by the Master Theorem or by substitution + induction) is itself an inductive argument: you conjecture T(n) = O(n log n), then prove it by strong induction.

The practical takeaway: every recursive program comes with a free induction proof template. Read the code, extract the recursive structure, and your induction proof writes itself. This is why functional programmers can be so confident about their code's correctness: algebraic data types + pattern matching + termination checking = built-in induction.

-- Proving merge sort correct in Haskell (sketch).
-- The recursive structure of the program IS the inductive proof.

mergeSort :: Ord a => [a] -> [a]
mergeSort []  = []        -- base case 1
mergeSort [x] = [x]       -- base case 2
mergeSort xs  =           -- recursive case
  let (left, right) = splitAt (length xs `div` 2) xs
  in merge (mergeSort left) (mergeSort right)

merge :: Ord a => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys)
  | x <= y    = x : merge xs (y:ys)
  | otherwise = y : merge (x:xs) ys

-- Correctness proof sketch by strong induction on length xs:
-- Base cases: [] and [x] are already sorted. ✓
-- IH: mergeSort correctly sorts any list shorter than xs.
--     length left < length xs, length right < length xs  (for |xs|>=2)
-- Step: by IH, mergeSort left is sorted, mergeSort right is sorted.
--       merge of two sorted lists is sorted (separate lemma by induction).
-- Therefore mergeSort xs is sorted. ✓