Proof by Induction

Why This Matters

How do you prove that a formula works for every natural number? You cannot check infinitely many cases one by one. Mathematical induction solves this problem elegantly: prove it works for the first case, then prove that if it works for any case k, it must also work for k+1. Like a chain of dominoes, knocking over the first one guarantees they all fall.

The base case is where the chain starts. The inductive step is the domino effect: it shows that truth at one position forces truth at the next. Together, they cover every natural number from the base case onward, no matter how large.

Induction is everywhere in computer science. Recursive algorithms have inductive structure: the base case handles the smallest input, and the recursive step reduces larger inputs. Proving that a recursive function terminates and produces correct results is fundamentally an inductive argument. Understanding induction makes you better at writing, analyzing, and trusting recursive code.

Define Terms

Visual Model

Code Example

// Mathematical Induction: verify the sum formula
// Claim: 1 + 2 + ... + n = n(n+1)/2

// Compute sum directly
function directSum(n) {
  let total = 0;
  for (let i = 1; i <= n; i++) {
    total += i;
  }
  return total;
}

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

// Base case: n = 1
console.log("Base case (n=1):");
console.log("  Direct:", directSum(1));   // 1
console.log("  Formula:", formulaSum(1)); // 1
console.log("  Match:", directSum(1) === formulaSum(1)); // true

// Inductive step: if formula works for k, show it works for k+1
function inductiveStep(k) {
  const sumK = formulaSum(k);            // Assume this is correct (P(k))
  const sumK1Direct = sumK + (k + 1);    // Add next term
  const sumK1Formula = formulaSum(k + 1); // What formula predicts for k+1
  const matches = sumK1Direct === sumK1Formula;
  console.log(`k=${k}: sum(k)=${sumK}, sum(k)+(k+1)=${sumK1Direct}, formula(k+1)=${sumK1Formula}, match=${matches}`);
  return matches;
}

console.log("\nInductive steps:");
for (let k = 1; k <= 10; k++) {
  inductiveStep(k);
}

// Verify for a large range
console.log("\nVerifying for n = 1 to 1000:");
let allMatch = true;
for (let n = 1; n <= 1000; n++) {
  if (directSum(n) !== formulaSum(n)) {
    console.log(`MISMATCH at n=${n}`);
    allMatch = false;
    break;
  }
}
console.log(allMatch ? "All matched!" : "Mismatch found!");

Interactive Experiment

Try these exercises:

• Verify the base case and inductive step for the formula: 1 + 3 + 5 + ... + (2n-1) = n squared. Test for n = 1 through 20.
• Write code that checks if adding the next odd number to the sum of the first k odd numbers gives (k+1) squared.
• Verify the sum of squares formula: 1 squared + 2 squared + ... + n squared = n(n+1)(2n+1)/6 for n = 1 to 100.
• What happens if you skip the base case? Take a false formula and show the inductive step "works" but the formula is wrong because the base case fails.
• Implement a recursive sum function and trace how each call corresponds to a step in the induction.

Quick Quiz

Coding Challenge

Real-World Usage

Inductive thinking is central to computer science:

• Recursive algorithms: Every correct recursive function has an inductive structure. The base case stops recursion; the recursive step reduces the problem.
• Data structure invariants: Proving that a balanced BST stays balanced after insertion uses induction on tree height.
• Compiler correctness: Compilers prove optimizations preserve meaning by induction on expression depth or program length.
• Network protocols: Proving that a routing algorithm converges uses induction on the number of iterations.
• Dynamic programming: DP solutions build answers for larger subproblems from smaller ones, following the inductive pattern exactly.

Connections