Mathematical Induction

Discrete Mathematics Fundamentals

Chapter 8 · Mathematical Induction

Chapter 7 promised this: the one proof technique that can genuinely establish a property for infinitely many cases at once, not just the finitely many anyone happened to test. It's also the most directly programming-relevant technique in this entire course — proving a recursive function correct is induction, whether or not anyone names it that.

The Domino Intuition

Line up infinitely many dominoes. If you knock over the first one, and every domino is close enough to knock over the next one whenever it falls, then all of them fall — no matter how many there are. You never had to individually push each domino; the mechanism itself guarantees the rest.

The Formal Structure

Induction has exactly two parts:

  • Base case: prove the property P(n) holds for the smallest value (usually n=0 or n=1) — knocking over the first domino
  • Inductive step: assume P(k) holds for some arbitrary k (the "inductive hypothesis"), and prove that this forces P(k+1) to also hold — showing each domino knocks over the next

Together, using Chapter 3's own quantifier notation: [P(0) ∧ ∀k (P(k) → P(k+1))] → ∀n P(n).

Worked Example: Summing the First n Integers

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

Base case (n=1): LHS = 1. RHS = 1(2)/2 = 1. Equal. ✓

Inductive step: Assume 1+2+...+k = k(k+1)/2 (the inductive hypothesis). Show it then holds for k+1:

1+2+...+k+(k+1) = [k(k+1)/2] + (k+1)  (using the inductive hypothesis to replace the first k terms)
= (k+1)[k/2 + 1] = (k+1)(k+2)/2 — exactly the formula with n replaced by k+1. ∎

Worked Example: Proving a Recursive Function Correct

This is the same technique, applied directly to code — often called structural induction when the "size" being inducted on is the size of a data structure.

def sum_list(lst): if len(lst) == 0: return 0 return lst[0] + sum_list(lst[1:])
Claim: sum_list(lst) returns the sum of every element in lst, for any list of length n ≥ 0

Base case (n=0): An empty list hits len(lst) == 0 and returns 0 — the sum of no elements is 0, by convention. ✓

Inductive step: Assume sum_list correctly sums any list of length k (the inductive hypothesis). Consider a list of length k+1. The function computes lst[0] + sum_list(lst[1:]), where lst[1:] has length exactly k — so by the inductive hypothesis, sum_list(lst[1:]) correctly returns the sum of the remaining k elements. Adding lst[0] gives the sum of all k+1 elements. ✓

By induction, sum_list is correct for every possible list length. ∎

This is exactly how recursive functions get proven correct
Structural induction is the formal justification behind the intuition "if the recursive call works correctly, and the base case is right, the whole function is right" — that intuition is mathematical induction, just applied to a function's own input size rather than to a number in a summation.

Loop Invariants Are Induction Too

The same pattern, applied to a running loop
Proving a loop invariant holds after every iteration follows the identical structure: base case = the invariant holds before the loop starts (after zero iterations); inductive step = if the invariant holds before a given iteration, it still holds after that iteration runs. This is exactly how loop correctness gets formally proven — the same two-part argument, just applied to "iteration count" instead of a plain integer n.

The Common Mistake: Checking a Specific k Instead of an Arbitrary One

The inductive step has to work for ANY k, not just one you happened to check
Verifying that P(1) → P(2) holds, and stopping there, is not a valid inductive step — it's just one more base case in disguise. A genuine inductive step proves the implication P(k) → P(k+1) for a completely arbitrary k, using only the assumption that P(k) holds, never a specific numeric value. This is a genuinely common mistake, and it's exactly what Exercise 3 asks you to catch.

Hands-On Exercises

Exercise 1

Prove by induction that 1 + 3 + 5 + ... + (2n − 1) = n² for all n ≥ 1 (the sum of the first n odd numbers).

📄 View solution
Exercise 2

Given the recursive function power_of_two(n), which returns 1 if n == 0 and otherwise returns 2 * power_of_two(n-1), prove by induction that it correctly returns 2ⁿ for every n ≥ 0.

📄 View solution
Exercise 3

Someone offers this "proof" that 3ⁿ − 1 is divisible by 2 for all n ≥ 1: "Base case n=1: 3¹−1=2, divisible by 2. Inductive step: check n=2: 3²−1=8, divisible by 2. Therefore, by induction, the claim holds for all n." Explain specifically why this is not a valid inductive proof, and provide a corrected inductive step.

📄 View solution

Chapter 8 Quick Reference

  • Induction proves a property for infinitely many cases — the domino intuition: knock over the first, guarantee each knocks over the next
  • Base case: prove P(0) or P(1) directly — Inductive step: assume P(k) for arbitrary k, prove P(k+1) follows
  • Structural induction on a recursive function's input size is exactly how recursive functions get proven correct
  • Loop invariants are proven the same way — the invariant holding before an iteration implies it still holds after
  • The inductive step must work for an arbitrary k — checking one specific transition (like 1→2) is not a valid inductive step, just another base case
  • Next chapter: Combinatorics — counting, permutations, and combinations