Difficulty: Intermediate | Prerequisites: Chapter 3 (algorithm basics), basic algebra
Tags: mathematical induction, strong induction, structural induction, recursive definition, recursive algorithm, basis step, inductive step, inductive hypothesis, proof by induction, Fibonacci, full binary tree, rooted tree, CS182, discrete math, Purdue
Induction is the primary tool for proving statements about all positive integers (or all members of a recursively defined set). If you cannot write an induction proof, you cannot prove that most algorithms are correct or that most formulas hold for all n. This chapter covers three flavours: ordinary (weak) induction, strong induction, and structural induction. It also introduces recursive definitions and recursive algorithms, which are the computational counterpart of inductive reasoning. You should be comfortable with basic algebra and summation notation before starting.
Mathematical induction proves a statement P(n) for all integers n >= b by showing P(b) is true (basis step) and showing that P(k) implies P(k+1) (inductive step). Strong induction assumes all of P(b), P(b+1), ..., P(k) to prove P(k+1). Structural induction extends this to recursively defined objects like trees. Recursive definitions and algorithms mirror the structure of induction proofs.
Mathematical induction
A proof technique for establishing that a statement P(n) holds for every positive integer n (or every integer n >= b). Requires a basis step and an inductive step. Think of it as dominoes: knock over the first one (basis), and show that any domino falling causes the next to fall (inductive step).
Basis step
The part of an induction proof where you verify the statement for the smallest value of n (usually n = 1 or n = 0).
Inductive hypothesis
The assumption, made during the inductive step, that P(k) is true for some arbitrary integer k. You then use this assumption to prove P(k+1).
Inductive step
The part of an induction proof where you show P(k) implies P(k+1) for all k >= b.
Strong induction
A variant of induction where the inductive hypothesis assumes P(b), P(b+1), ..., P(k) are all true, and you prove P(k+1). Useful when proving P(k+1) requires more than just P(k). In simple terms, you assume every previous domino has fallen, not just the one right before.
Recursive definition
A definition where a function, sequence, or set is defined in terms of itself, with a base case specifying initial values and a recursive rule specifying how to compute new values from previous ones.
Recursive algorithm
An algorithm that solves a problem by reducing it to smaller instances of the same problem, with a base case that terminates the recursion.
Structural induction
An induction technique for proving properties of recursively defined structures (such as trees or strings). The basis step proves the property for the base elements; the recursive step proves it for elements built from smaller ones.
Full binary tree
A rooted tree where every internal vertex has exactly two children. Defined recursively: a single vertex is a full binary tree, and if T₁ and T₂ are full binary trees, a new tree with root r, left subtree T₁, and right subtree T₂ is a full binary tree.
The ladder analogy: if you can reach rung 1, and reaching any rung k means you can reach rung k + 1, then you can reach any rung.
To prove P(n) for all integers n >= b:
Basis step: Show P(b) is true.
Inductive step: For an arbitrary integer k >= b, assume P(k) is true (this is the inductive hypothesis). Prove P(k+1) is true.
Important: you do not assume P(k) is true for all k. You assume it for one arbitrary k and prove it for k + 1. The logical form is: "if P(k) then P(k+1)."
Proofs do not always start at 1. Some start at 0, 4, 12, or any other integer.
Prove: Σ(i=1 to n) i = n(n+1)/2.
Basis: n = 1. Left side = 1. Right side = 1(2)/2 = 1. True.
Inductive hypothesis: Assume Σ(i=1 to k) i = k(k+1)/2.
Inductive step: Show Σ(i=1 to k+1) i = (k+1)(k+2)/2.
Left side = (1 + 2 + ... + k) + (k+1) = k(k+1)/2 + (k+1) [by inductive hypothesis]
= k(k+1)/2 + 2(k+1)/2 = (k+1)(k+2)/2. Done.
Prove: 1 + 3 + 5 + ... + (2k - 1) = k².
Basis: k = 1. Left side = 1. Right side = 1. True.
Inductive hypothesis: Assume 1 + 3 + ... + (2k - 1) = k².
Inductive step: Add the next odd integer (2k + 1). Left side becomes k² + (2k + 1) = (k + 1)². Done.
Prove: n < 2ⁿ for all positive integers n.
Basis: n = 1. 1 < 2. True.
Inductive hypothesis: Assume k < 2ᵏ.
Inductive step: k + 1 < 2ᵏ + 1 <= 2ᵏ + 2ᵏ = 2 × 2ᵏ = 2ᵏ⁺¹. Done.
Prove: 2ⁿ < n! for all n >= 4.
Basis: n = 4. 2⁴ = 16 < 24 = 4!. True.
Inductive hypothesis: Assume 2ᵏ < k!.
Inductive step: 2ᵏ⁺¹ = 2 × 2ᵏ < 2 × k! <= (k+1) × k! = (k+1)!. (The last inequality holds because 2 <= k+1 for k >= 4.)
Prove: 3 | (n³ - n) for all positive integers n.
Basis: n = 1. 1 - 1 = 0 = 3 × 0. True.
Inductive hypothesis: Assume n³ - n = 3x for some integer x.
Inductive step: (n+1)³ - (n+1) = n³ + 3n² + 3n + 1 - n - 1 = (n³ - n) + 3n² + 3n = 3x + 3(n² + n) = 3(x + n² + n). Done.
Be aware of flawed induction arguments. The classic example: "every set of n non-parallel lines meets in a common point." The error occurs in the inductive step when you incorrectly assume that two intersection points from overlapping subsets must be the same. Always verify that your inductive step handles the transition from k to k+1 correctly, especially for small values of k.
To prove P(n) for all n >= b:
Basis step: Verify P(b) is true (may need multiple base cases).
Inductive step: Assume P(b), P(b+1), ..., P(k) are all true. Prove P(k+1).
Strong induction is equivalent in power to ordinary induction, but sometimes the proof is easier because you have more assumptions to work with.
Using ordinary induction:
Base case: p = 12 = 4×3 + 5×0.
Inductive hypothesis: p = 4x + 5y for some x, y >= 0.
For p+1: Case 1, if at least one 4-cent stamp was used for p, replace it with a 5-cent stamp. Case 2, if no 4-cent stamps were used, then p >= 12 means at least three 5-cent stamps were used; replace three 5-cent stamps (15 cents) with four 4-cent stamps (16 cents).
Using strong induction:
Base cases: p = 12, 13, 14, 15 (verify each can be formed).
Inductive hypothesis: all values from 12 to p can be formed.
For p+1: by the inductive hypothesis, p - 3 can be formed (since p - 3 >= 12 when p >= 15). Add a 4-cent stamp to get p + 1.
The strong induction version needs four base cases (12 through 15) to ensure p - 3 >= 12.
A recursive definition has a base step (initial values) and a recursive step (how to compute new values from old ones).
f(n) = 2ⁿ: f(0) = 1, f(n+1) = 2 × f(n)
f(n) = n!: f(0) = 1, f(n+1) = (n+1) × f(n)
Set S of natural numbers: 0 ∈ S, 1 ∈ S, and if a, b ∈ S then a + b ∈ S
Set T of powers of 2: 1 ∈ T, and if a ∈ T then 2a ∈ T
The Fibonacci sequence: f(1) = 1, f(2) = 1, f(n) = f(n-1) + f(n-2) for n >= 3.
Prove: fₙ > αⁿ⁻² for n >= 3, where α = (1 + √5)/2 (the golden ratio).
Base cases: f(3) = 2 > α ≈ 1.618. f(4) = 3 > α² ≈ 2.618.
Inductive step: fₖ₊₁ = fₖ + fₖ₋₁ > αᵏ⁻² + αᵏ⁻³ (by strong inductive hypothesis)
αᵏ⁻² + αᵏ⁻³ = αᵏ⁻³(α + 1) = αᵏ⁻³ × α² = αᵏ⁻¹ (using the property α² = α + 1).
Used to prove properties of recursively defined structures.
Basis step: show the property holds for the base elements of the recursive definition.
Recursive step: assuming the property holds for the components used to build a new element, show it holds for the new element.
Defined recursively: a single vertex r is a rooted tree. If T₁, T₂, ..., Tₙ are rooted trees with roots r₁, ..., rₙ, then a new tree formed by adding a root r connected to each rᵢ is a rooted tree.
Basis: a single vertex is a full binary tree.
Recursive step: if T₁ and T₂ are full binary trees, then T = T₁ · T₂ (a root with T₁ as left subtree and T₂ as right subtree) is a full binary tree.
Height h(T): for a single vertex, h(T) = 0. For T = T₁ · T₂, h(T) = 1 + max(h(T₁), h(T₂)).
Number of vertices n(T): for a single vertex, n(T) = 1. For T = T₁ · T₂, n(T) = 1 + n(T₁) + n(T₂).
Theorem: If T is a full binary tree, then n(T) <= 2^(h(T)+1) - 1.
Proof by structural induction: basis is n = 1 <= 2¹ - 1 = 1. Recursive step uses the inductive hypothesis on T₁ and T₂.
An algorithm is recursive if it solves a problem by reducing it to a smaller instance of the same problem.
Recursive factorial: factorial(0) = 1; factorial(n) = n × factorial(n-1).
Recursive exponentiation (power1): power1(a, 0) = 1; power1(a, n) = a × power1(a, n-1). Makes n multiplications.
Efficient recursive exponentiation (power2): if n is even, power2(a, n) = power2(a, n/2)². If n is odd, power2(a, n) = a × power2(a, ⌊n/2⌋)². Makes O(log n) multiplications.
Sum of first n integers: Σ(i=1 to n) i = n(n+1)/2
Sum of first k odd integers: 1 + 3 + 5 + ... + (2k-1) = k²
Fibonacci: fₙ = fₙ₋₁ + fₙ₋₂, with f₁ = f₂ = 1
Golden ratio property: α² = α + 1, where α = (1 + √5)/2
Full binary tree vertices: n(T) <= 2^(h(T)+1) - 1
Recursive algorithms are everywhere in CS: merge sort, quicksort, tree traversal, parsing, and divide-and-conquer strategies all rely on recursion. Induction proofs are how you verify these algorithms are correct. Structural induction is particularly important for compiler design, where you prove properties about parse trees and abstract syntax trees.
"Induction assumes what it is trying to prove." It does not. The inductive step proves a conditional: IF P(k) is true THEN P(k+1) is true. It does not assume P(k) is true for all k.
"You always start induction at n = 1." The base case can be any integer. Some proofs start at 0, 4, or 12.
"Strong induction is more powerful than ordinary induction." They are equivalent in logical power. Strong induction simply provides more assumptions in the inductive step, which sometimes makes the proof easier to write.
"A recursive algorithm is always better than an iterative one." Naive recursion (like recursive Fibonacci) can be exponentially slow. Iterative or dynamic programming solutions are often faster.
⚠️ Every induction proof must clearly label: the statement P(n), the basis step, the inductive hypothesis, and the inductive step. Points are deducted for skipping any of these.
⚠️ In the inductive step, you must explicitly use the inductive hypothesis. Highlight or underline where you invoke it.
⚠️ For strong induction, verify you have enough base cases. If the inductive step references P(k - 3), you need base cases for the first four values.
⚠️ Know the difference between ordinary induction and strong induction, and when each is appropriate.
⚠️ Be able to prove correctness of recursive algorithms like power2 using induction.
True or False: In ordinary induction, the inductive step assumes P(k) for all k.
Fill in the blank: Strong induction assumes P(b), P(b+1), ..., P(k) to prove ______.
True or False: The recursive Fibonacci algorithm runs in O(n) time.
Fill in the blank: The height of a full binary tree consisting of only a root is ______.
True or False: Structural induction can only be used on numbers.
Answers: 1. False (it assumes P(k) for one arbitrary k). 2. P(k+1). 3. False (it is O(2ⁿ)). 4. 0. 5. False (it applies to any recursively defined structure).
Q: Prove by induction that Σ(i=1 to n) i² = n(n+1)(2n+1)/6.
A: Basis: n = 1, 1 = 1×2×3/6 = 1. Inductive hypothesis: assume the formula holds for k. Then Σ(i=1 to k+1) i² = k(k+1)(2k+1)/6 + (k+1)² = (k+1)[k(2k+1) + 6(k+1)]/6 = (k+1)(2k² + 7k + 6)/6 = (k+1)(k+2)(2k+3)/6.
Q: Why does the postage problem using strong induction need base cases for p = 12, 13, 14, and 15?
A: The inductive step uses the fact that p - 3 can be formed. For p - 3 >= 12, we need p >= 15. So the cases p = 12, 13, 14 are not covered by the inductive step and must be verified directly.
Q: How many multiplications does power2(a, 15) use?
A: power2(a,15) calls power2(a,7), which calls power2(a,3), which calls power2(a,1). That is 4 calls, each doing at most 2 multiplications (squaring + one extra multiply for odd n). Total: about 7 multiplications, which is O(log 15) ≈ O(4).
Q: Why is the "all lines meet at a point" induction proof incorrect?
A: The inductive step assumes that when you split k+1 lines into two overlapping groups of k, the intersection points of the two groups must coincide. For k = 2 (going from 2 lines to 3), the two groups share only one line, which is not enough to force the intersection points to be the same.
Induction is the proof technique used most heavily in algorithm analysis (Chapter 3), where you prove runtime bounds. It connects to number theory (Chapter 4), where you prove divisibility results. Recursive definitions connect to counting (Chapter 6), where sequences like Fibonacci appear. Structural induction is essential for trees and graphs (Chapter 10).
mathematical induction, weak induction, strong induction, complete induction, structural induction, inductive hypothesis, basis step, inductive step, proof by induction, recursive definition, recursive algorithm, recursion, Fibonacci sequence, golden ratio, full binary tree, rooted tree, tree height, tree vertices, factorial, exponentiation, power algorithm, postage stamp problem, CS 182, Purdue, discrete math