02 — Induction | mathuser.com

Topic 02 — CS 70 Discrete Mathematics

Mathematical
Induction

The most powerful tool in the discrete mathematician's arsenal. Induction lets you prove statements about infinitely many cases by proving just two things: a base and a step. Learn it deeply — it underpins nearly every proof in this course.

Why Induction?

Consider the claim: "For every natural number n, 1+2+3+...+n = n(n+1)/2." There are infinitely many cases (n=0,1,2,...). We cannot check them all. We need a method to reason about all cases at once.

Induction exploits a key property of the natural numbers: they are built up one at a time. The naturals are {0, 1, 2, ...} where each number is just its predecessor plus one. If we can show P holds at the start, and that it "spreads" from each number to the next, then P must hold everywhere.

The Domino Analogy: Imagine infinitely many dominoes in a line. If you can knock down the first one (base case), and you know each domino knocks down the next (inductive step), then ALL dominoes will fall.

Simple (Weak) Induction

Principle of Mathematical Induction

Let P(n) be a predicate. To prove ∀n ∈ ℕ, P(n):

Base Case: Prove P(0) (or P(1), depending on context).

Inductive Step: Prove ∀n ≥ 0, P(n) → P(n+1).

In the inductive step, P(n) is called the Inductive Hypothesis (IH).

This is logically equivalent to: P(0) is true, and the IH is never falsified. Therefore P holds for all natural numbers.

The Induction Template

Every induction proof should clearly state these four components. Examiners will look for all of them.

Step 0 — State what you're proving
Clearly write P(n): the predicate/formula you will prove holds for all n.
Step 1 — Base Case: Prove P(0) [or P(1)]
Verify the claim directly for the smallest value of n. This is usually just arithmetic or a direct check.
Step 2 — Inductive Hypothesis (IH)
Assume P(n) is true for some fixed arbitrary n ≥ 0. State it explicitly: "Assume [formula] holds for n."
Step 3 — Inductive Step: Prove P(n+1)
Using the IH, derive that P(n+1) holds. This is the creative heart of the proof. You must use the IH here.
Step 4 — Conclude
By the principle of mathematical induction, P(n) holds for all n ≥ 0. ∎

Classic Examples

Sum of First n Natural Numbers

Theorem — ∑ᵢ₌₀ⁿ i = n(n+1)/2

P(n): 0 + 1 + 2 + ... + n = n(n+1)/2

Base Case (n=0): LHS = 0. RHS = 0(1)/2 = 0. ✓

IH: Assume 0 + 1 + ... + n = n(n+1)/2 for some n ≥ 0.

Inductive Step — prove P(n+1):

  1. 0 + 1 + ... + n + (n+1) = [0 + 1 + ... + n] + (n+1)
  2. = n(n+1)/2 + (n+1)     [by IH]
  3. = (n+1)[n/2 + 1] = (n+1)(n+2)/2     [algebra]
  4. This is exactly P(n+1): the formula with n replaced by n+1. ∎

Every n ≥ 2 is a Product of Primes

Theorem — Prime Factorization Exists

Note: This requires strong induction because "n = ab" with a,b < n — we need P for values smaller than n, not just n itself.

Base Case (n=2): 2 is prime, and 2 = 2 is a product of one prime. ✓

IH (Strong): Assume every integer k with 2 ≤ k ≤ n can be written as a product of primes.

Inductive Step — prove for n+1:

  1. If n+1 is prime: it's already a product of one prime. Done.
  2. If n+1 is not prime: n+1 = ab for some 2 ≤ a, b ≤ n.
  3. By IH applied to a: a = p₁p₂...pⱼ (product of primes). By IH applied to b: b = q₁q₂...qₖ (product of primes).
  4. Therefore n+1 = p₁...pⱼq₁...qₖ is a product of primes. ∎

Bernoulli's Inequality (DIS 1A)

Theorem — For n ∈ ℕ and x > -1: (1+x)ⁿ ≥ 1+nx

Base Case (n=0): (1+x)⁰ = 1 ≥ 1 + 0·x = 1. ✓

IH: Assume (1+x)ⁿ ≥ 1 + nx for some n ≥ 0.

Inductive Step:

  1. (1+x)ⁿ⁺¹ = (1+x)ⁿ · (1+x)
  2. ≥ (1+nx)(1+x)     [IH; and (1+x) > 0 since x > −1, so inequality preserved]
  3. = 1 + x + nx + nx² = 1 + (n+1)x + nx²
  4. ≥ 1 + (n+1)x     [since nx² ≥ 0]
  5. This is exactly P(n+1). ∎

Binary Representation (DIS 1A)

Theorem — Every positive integer can be written in binary

Base Case (n=1): 1 = 1·2⁰. Written in binary as "1". ✓

IH (Strong): Every integer k with 1 ≤ k ≤ n has a binary representation.

Inductive Step — prove for n+1:

  1. Case 1: n+1 is odd. Then n+1 = 2m+1 for m = (n+1-1)/2 = n/2 ≤ n. By IH, m has binary representation m = cₖ2ᵏ+...+c₀2⁰. Then n+1 = cₖ2ᵏ⁺¹+...+c₀2¹+1·2⁰. Binary representation exists.
  2. Case 2: n+1 is even. Then n+1 = 2m where m = (n+1)/2 ≤ n. By IH, m has binary rep. Multiply by 2 (shift left, append 0 bit). Done. ∎

Strong Induction

Principle of Strong Induction

To prove ∀n ∈ ℕ, P(n):

Base Case: Prove P(0).

Strong IH: Assume P(k) holds for all k ≤ n.

Inductive Step: Using the strong IH, prove P(n+1).

Strong and simple induction are equivalent in power — either can prove anything the other can. But sometimes strong induction is much more convenient.

Simple Induction IH

"Assume P(n) is true."
You only get to use P at the single value n.

Strong Induction IH

"Assume P(k) for all k ≤ n."
You can use P at any smaller value. More tools available.

When to use strong induction: When the step from n+1 uses information about values other than just n — for example, when n+1 = a + b where a, b < n+1 but neither equals n (like Fibonacci or prime factorization).

Strengthening the Induction Hypothesis

Sometimes, the statement you want to prove is actually too weak to be provable by induction — the IH doesn't give you enough to work with in the inductive step. The solution is to prove a stronger statement.

Paradox: It seems harder to prove a stronger statement. But a stronger statement gives you a stronger IH — and that stronger IH is exactly what you need to make the inductive step work. The extra strength feeds into itself.
DIS 1A — Prove: aₙ ≤ 3^(2ⁿ) where a₁=1, aₙ₊₁ = 3aₙ²

Why weak IH fails: In the inductive step, we need to bound a²ₙ. If IH gives aₙ ≤ 3^(2ⁿ), then aₙ² ≤ 3^(2ⁿ⁺¹). So aₙ₊₁ = 3aₙ² ≤ 3·3^(2ⁿ⁺¹) = 3^(2ⁿ⁺¹+1). But we need 3^(2ⁿ⁺¹) — we're off by a factor of 3. The IH is too weak.

Stronger claim: Prove aₙ ≤ 3^(2ⁿ⁻¹) for all n ≥ 1. (This is actually stronger — a tighter bound.)

Base Case (n=1): a₁ = 1 ≤ 3^(2⁰) = 3^1 = 3. ✓

IH: Assume aₙ ≤ 3^(2ⁿ⁻¹).

Inductive Step: aₙ₊₁ = 3aₙ² ≤ 3·(3^(2ⁿ⁻¹))² = 3·3^(2ⁿ) = 3^(2ⁿ+1) = 3^(2ⁿ⁺¹⁻¹). ✓

Why stronger implies the original: 3^(2ⁿ⁻¹) ≤ 3^(2ⁿ) for all n ≥ 1, so the stronger bound immediately implies the weaker one. ∎

Classic — Sum of odd numbers

Weak claim: The sum of the first n odd numbers is a perfect square. Hard to do induction on because "is a perfect square" is hard to work with in the step.

Strong claim: The sum of the first n odd numbers is n². (This is stronger and more specific.)

1 + 3 + 5 + ... + (2n−1) = n²

Now the IH is: 1+3+...+(2n−1) = n². In the step: add (2n+1) to get n² + (2n+1) = (n+1)². Perfect. ∎

The stronger IH gave us exactly what we needed!

Build-Up Error — A Crucial Pitfall

⚠ What Is Build-Up Error?

Build-up error occurs when you try to prove a property of all n-vertex graphs by adding a vertex to a graph with n−1 vertices. The problem: not all n-vertex graphs are obtained this way. The added vertex might not satisfy the property you need, and more critically, the (n+1)-vertex graph you construct is a very specific type — not an arbitrary graph on n+1 vertices.

DIS 2A — The False Claim and its Flawed Proof

False Claim: If every vertex in a graph with |V| ≥ 2 has degree at least 1, then the graph is connected.

Counterexample: Take two disjoint edges: {1−2} and {3−4}. Every vertex has degree 1. But the graph is disconnected (no path from 1 to 3).

Why the "proof" fails: The proof adds a vertex x to a connected n-vertex graph and says "x has degree ≥ 1 so it's connected to some y, and y is in the connected graph, so done." But the (n+1)-vertex graph is not arbitrary — it's specifically one that was built by adding x to a connected component. A real (n+1)-vertex graph where every vertex has degree ≥ 1 need not have this structure.

Rule of Thumb: In induction on graphs, it's safer to remove a carefully chosen vertex/edge (tear-down induction) than to add one (build-up). When tearing down, you get an arbitrary smaller graph; when building up, you get a constrained larger graph.

Worked Problems from Discussion

Fibonacci: Every Third Fib is Even (DIS 1A)

Theorem — F₃ₙ is even for all n ≥ 1, where F₁=F₂=1, Fₙ=Fₙ₋₂+Fₙ₋₁

Insight: Prove something stronger — determine the parity of ALL Fibonacci numbers. The pattern is: Odd, Odd, Even, Odd, Odd, Even, ... repeating every 3 terms.

Strengthen to P(n): F₃ₙ₋₂ is odd, F₃ₙ₋₁ is odd, F₃ₙ is even.

Base Case (n=1): F₁=1 (odd), F₂=1 (odd), F₃=2 (even). ✓

IH: Assume F₃ₙ₋₂ odd, F₃ₙ₋₁ odd, F₃ₙ even.

Inductive Step:

  • F₃ₙ₊₁ = F₃ₙ + F₃ₙ₋₁ = even + odd = odd ✓
  • F₃ₙ₊₂ = F₃ₙ₊₁ + F₃ₙ = odd + even = odd ✓
  • F₃ₙ₊₃ = F₃ₙ₊₂ + F₃ₙ₊₁ = odd + odd = even ✓

Pattern maintained. By induction, every third Fibonacci number is even. ∎

Practice Problems

Practice 1

Prove: ∑ᵢ₌₁ⁿ i² = n(n+1)(2n+1)/6.

Practice 2

Prove: 3 | (n³ − n) for all n ∈ ℕ. (Hint: try cases mod 3, or factor n³−n = n(n−1)(n+1).)

Practice 3 (Strong Induction)

Prove: Every integer n ≥ 8 can be written as 3a + 5b for non-negative integers a, b. (Base cases: 8=3+5, 9=3+3+3, 10=5+5. Strong IH: if true for all k < n, then for n use n = (n−3) + 3.)