Module 6 – Class 1: Principle of Mathematical Induction
Learning Objectives
- State the principle of mathematical induction (PMI).
- Identify and verify the base case and inductive step.
- Use induction to prove summation formulas and divisibility results.
- Connect induction to loops and recursion in Java.
- Implement iterative and recursive versions of the same computation, relating each to the proof structure.
Concept Overview
The Principle of Mathematical Induction
To prove a statement $P(n)$ for all integers $n \geq n_0$:
- Base case: Prove $P(n_0)$.
- Inductive step: Assume $P(k)$ for some $k \geq n_0$ (inductive hypothesis). Prove $P(k+1)$.
If both succeed, then $P(n)$ holds for all $n \geq n_0$.
The Domino Analogy
Induction is like an infinite row of dominos:
- Push the first domino (base case).
- Show that if any domino falls, the next one falls too (inductive step).
- Conclusion: all dominos fall.
Why Induction Works
PMI is an axiom of the natural numbers (Peano's fifth axiom). It captures the idea that every natural number can be reached from 0 by repeatedly adding 1.
Connection to Computation
| Induction Component | Loop Version | Recursion Version |
|---|---|---|
| Base case $P(n_0)$ | Initialization before loop | Base case in recursion |
| Inductive hypothesis $P(k)$ | Loop invariant at iteration $k$ | Recursive call result |
| Inductive step $P(k) \to P(k+1)$ | Loop body | Recursive case |
| Conclusion $\forall n \geq n_0, P(n)$ | Postcondition after loop | Correctness for all inputs |
Formal Notation
Worked Examples
Example 1: Sum of First $n$ Natural Numbers
Claim: $\displaystyle\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$ for all $n \geq 1$.
Proof by induction.
Base case ($n = 1$): $\sum_{i=1}^{1} i = 1 = \frac{1 \cdot 2}{2}$. ✓
Inductive step: Assume $\sum_{i=1}^{k} i = \frac{k(k+1)}{2}$ for some $k \geq 1$.
This is $\frac{(k+1)((k+1)+1)}{2}$, which is $P(k+1)$. ✓ $\blacksquare$
Example 2: Sum of Squares
Claim: $\displaystyle\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$ for all $n \geq 1$.
Base case ($n = 1$): $1 = \frac{1 \cdot 2 \cdot 3}{6} = 1$. ✓
Inductive step: Assume the formula holds for $k$. Then:
This is the formula with $n = k+1$. ✓ $\blacksquare$
Example 3: Divisibility
Claim: $n^3 - n$ is divisible by 3 for all $n \geq 0$.
Base case ($n = 0$): $0^3 - 0 = 0$, and $3 \mid 0$. ✓
Inductive step: Assume $3 \mid (k^3 - k)$.
By the inductive hypothesis, $3 \mid (k^3 - k)$. Clearly $3 \mid 3(k^2 + k)$. So $3$ divides their sum. ✓ $\blacksquare$
Example 4: Power of 2
Claim: $2^n > n$ for all $n \geq 1$.
Base case ($n = 1$): $2^1 = 2 > 1$. ✓
Inductive step: Assume $2^k > k$ for some $k \geq 1$.
(since $k \geq 1$). So $2^{k+1} > k + 1$. ✓ $\blacksquare$
Example 5: Geometric Sum
Claim: $\displaystyle\sum_{i=0}^{n} r^i = \frac{r^{n+1} - 1}{r - 1}$ for $r \neq 1$ and all $n \geq 0$.
Base case ($n = 0$): $r^0 = 1 = \frac{r - 1}{r - 1}$. ✓
Inductive step: Assume the formula for $k$:
✓ $\blacksquare$
Proof Techniques Spotlight
The Induction Template
- State the predicate $P(n)$ clearly.
- Base case: Substitute $n = n_0$ and verify directly.
- Inductive hypothesis: "Assume $P(k)$ holds for some $k \geq n_0$."
- Inductive step: Start from $P(k+1)$'s left side, manipulate to use $P(k)$.
- Conclude: By PMI, $P(n)$ holds for all $n \geq n_0$.
Common Mistakes
- Forgetting the base case. The step alone is not enough.
- Not using the hypothesis. If you prove $P(k+1)$ without assuming $P(k)$, you have a direct proof, not induction.
- Wrong base case. If $P(n)$ is for $n \geq 2$, verify $P(2)$, not $P(1)$.
- Falling into circularity. Never assume what you want to prove.
Java Deep Dive
import java.util.*;
public class InductionLibrary {
// --- Summation Functions ---
/**
* Iterative sum: 1 + 2 + ... + n.
* Loop invariant: after iteration i, sum = i(i+1)/2.
* consider O(n) vs O(1) complexity
*/
public static long sumIterative(int n) {
long sum = 0;
for (int i = 1; i <= n; i++) {
sum += i;
// Invariant: sum == i * (i + 1) / 2
}
return sum;
}
/**
* Recursive sum: mirrors the inductive proof.
* Base case: sum(0) = 0.
* Recursive case: sum(n) = sum(n-1) + n.
*/
public static long sumRecursive(int n) {
if (n <= 0) return 0; // Base case
return sumRecursive(n - 1) + n; // Inductive step
}
/**
* Closed-form formula (direct computation).
* This is what the proof establishes.
*/
public static long sumFormula(int n) {
return (long) n * (n + 1) / 2;
}
// --- Sum of Squares ---
public static long sumSquaresIterative(int n) {
long sum = 0;
for (int i = 1; i <= n; i++) {
sum += (long) i * i;
}
return sum;
}
public static long sumSquaresFormula(int n) {
return (long) n * (n + 1) * (2 * n + 1) / 6;
}
// --- Divisibility: n^3 - n divisible by 3 ---
public static boolean cubeMinusNDivisibleBy3(int n) {
long val = (long) n * n * n - n;
return val % 3 == 0;
}
// --- Geometric Sum ---
public static double geometricSumIterative(double r, int n) {
double sum = 0;
for (int i = 0; i <= n; i++) {
sum += Math.pow(r, i);
}
return sum;
}
public static double geometricSumFormula(double r, int n) {
if (Math.abs(r - 1.0) < 1e-10) return n + 1;
return (Math.pow(r, n + 1) - 1) / (r - 1);
}
// --- Factorial ---
/**
* Iterative factorial.
* Loop invariant: after iteration i, result = i!
*/
public static long factorialIterative(int n) {
long result = 1;
for (int i = 2; i <= n; i++) {
result *= i;
// Invariant: result == i!
}
return result;
}
/**
* Recursive factorial: mirrors induction.
* Base case: 0! = 1.
* Inductive step: n! = n * (n-1)!
*/
public static long factorialRecursive(int n) {
if (n <= 1) return 1;
return n * factorialRecursive(n - 1);
}
// --- Verification: Check formula against computation ---
/**
* For each n from 1 to max, verify formula matches iterative sum.
* This is empirical verification — the proof provides certainty.
*/
public static void verifyFormulas(int max) {
System.out.println("Verifying formulas for n = 1 to " + max + "...");
for (int n = 1; n <= max; n++) {
// Sum of first n naturals
assert sumIterative(n) == sumFormula(n)
: "Sum formula failed at n=" + n;
// Sum of squares
assert sumSquaresIterative(n) == sumSquaresFormula(n)
: "Sum-of-squares formula failed at n=" + n;
// n^3 - n divisible by 3
assert cubeMinusNDivisibleBy3(n)
: "n^3-n not divisible by 3 at n=" + n;
// Geometric sum (r=2)
double iterGeo = geometricSumIterative(2.0, n);
double formGeo = geometricSumFormula(2.0, n);
assert Math.abs(iterGeo - formGeo) < 1e-6
: "Geometric sum failed at n=" + n;
}
System.out.println("All formulas verified!");
}
// --- Power of 2 > n ---
public static void verifyPowerOf2(int max) {
System.out.println("Verifying 2^n > n for n = 1 to " + max + "...");
for (int n = 1; n <= max; n++) {
long pow = 1L << n; // 2^n using bit shift
assert pow > n : "2^n > n failed at n=" + n;
}
System.out.println("Verified!");
}
// --- Demonstration ---
public static void main(String[] args) {
System.out.println("=== Induction Library ===\n");
System.out.println("Sum of 1..100:");
System.out.println(" Iterative: " + sumIterative(100));
System.out.println(" Recursive: " + sumRecursive(100));
System.out.println(" Formula: " + sumFormula(100));
System.out.println("\nSum of squares 1..10:");
System.out.println(" Iterative: " + sumSquaresIterative(10));
System.out.println(" Formula: " + sumSquaresFormula(10));
System.out.println("\n10! = " + factorialIterative(10));
System.out.println("10! = " + factorialRecursive(10));
System.out.println("\nGeometric sum r=2, n=10:");
System.out.println(" Iterative: " + geometricSumIterative(2.0, 10));
System.out.println(" Formula: " + geometricSumFormula(2.0, 10));
// 2^11 - 1 = 2047
System.out.println();
verifyFormulas(1000);
verifyPowerOf2(60);
}
}Historical Context
Blaise Pascal (1654) and Pierre de Fermat used induction implicitly in their study of combinatorial identities and number theory. Giuseppe Peano (1889) made induction an explicit axiom in his axiomatization of the natural numbers. The Peano axioms remain the foundation of arithmetic.
The connection between induction and recursion was made rigorous by Kurt Gödel (1931) and Stephen Kleene (1936) through primitive recursive functions, laying the groundwork for theoretical computer science.
Gauss (age ~10, ca. 1787) famously computed $1 + 2 + \cdots + 100 = 5050$ by the pairing trick: write the sum forwards and backwards, pair terms to get $n+1$ each, giving $\frac{n(n+1)}{2}$.
Slide-Ready Problem Sets
Slide Set A: Conceptual Questions
A1. What are the two components of an induction proof? What role does each play?
A2. True or false: "If the inductive step works, the theorem is proved even without a base case."
A3. How does a for loop from 1 to $n$ mirror an induction proof?
A4. What goes wrong if we try to prove "$2^n > n^2$ for all $n \geq 1$" by induction? (Hint: check the base case.)
Slide Set B: Proof Problems
B1. Prove by induction: $\displaystyle\sum_{i=1}^{n} (2i - 1) = n^2$.
B2. Prove by induction: $3 \mid (4^n - 1)$ for all $n \geq 1$.
B3. Prove by induction: $\displaystyle\sum_{i=0}^{n} 2^i = 2^{n+1} - 1$.
Slide Set C: Java Coding Problems
C1. Write both iterative and recursive methods for $\sum_{i=1}^n i^2$. Verify they agree for $n = 1$ to 100.
C2. Write a method that checks $3 \mid (n^3 - n)$ for all $n$ from 0 to 10000.
C3. Implement factorial iteratively with a loop invariant comment. Add an assertion checking the invariant.
Full Problem Set
Discrete Math Problems
DM1. Prove by induction: $\displaystyle\sum_{i=1}^{n} i^3 = \left(\frac{n(n+1)}{2}\right)^2$.
DM2. Prove by induction: $n! > 2^n$ for all $n \geq 4$.
DM3. Prove by induction: for all $n \geq 1$, $\displaystyle\sum_{i=1}^{n} \frac{1}{i(i+1)} = \frac{n}{n+1}$.
DM4. Prove by induction: $6 \mid n(n+1)(n+2)$ for all $n \geq 0$.
DM5. Prove: $1 + 2 + 4 + \cdots + 2^{n-1} = 2^n - 1$ (geometric sum with $r = 2$).
DM6. Prove by induction: the number of subsets of a set with $n$ elements is $2^n$. (Connect to Module 4, power sets.)
Java Programming Problems
JP1. Implement sumFormula(n), sumIterative(n), and sumRecursive(n). Verify all three agree for $n = 1$ to 10000.
JP2. Implement factorialIterative(n) and factorialRecursive(n). Add loop invariant comments and assertions.
JP3. Write a method boolean isDivisibleBy(long n, int d) and use it to verify $6 \mid n(n+1)(n+2)$ for $n = 0$ to 1000.
JP4. Implement iterative and recursive geometric sum. Compare with the formula for various $r$ and $n$.
JP5. Write a method that, given $n$, returns the minimum $k$ such that $2^k > n$. Test it and explain the connection to $\lceil \log_2(n+1) \rceil$.
Bridge Problems
BR1. From Module 1: prove that the GCD algorithm terminates using the well-ordering principle (every non-empty set of non-negative integers has a least element). Then show how the well-ordering principle follows from PMI, and vice versa.
BR2. From Module 4: prove $|\mathcal{P}(A)| = 2^{|A|}$ by induction on $|A|$. Connect to the bit-mask power set generation from Module 4, Class 3.
Solutions
Discrete Math Solutions
DM1. Base ($n=1$): $1^3 = 1 = (1 \cdot 2/2)^2 = 1$. ✓
Inductive step: Assume $\sum_{i=1}^k i^3 = \left(\frac{k(k+1)}{2}\right)^2$.
$= \left(\frac{(k+1)(k+2)}{2}\right)^2$. ✓ $\blacksquare$
DM2. Base ($n=4$): $4! = 24 > 16 = 2^4$. ✓
Inductive step: Assume $k! > 2^k$ for $k \geq 4$.
$(k+1)! = (k+1) \cdot k! > (k+1) \cdot 2^k \geq 2 \cdot 2^k = 2^{k+1}$ (since $k+1 \geq 5 > 2$). ✓ $\blacksquare$
DM4. Base ($n=0$): $0 \cdot 1 \cdot 2 = 0$, and $6 \mid 0$. ✓
Inductive step: Assume $6 \mid k(k+1)(k+2)$.
$(k+1)(k+2)(k+3) = k(k+1)(k+2) + 3(k+1)(k+2)$.
By hypothesis, $6 \mid k(k+1)(k+2)$. Also, $(k+1)(k+2)$ is the product of two consecutive integers, so one is even, meaning $2 \mid (k+1)(k+2)$. Thus $6 \mid 3(k+1)(k+2)$. So $6$ divides the sum. ✓ $\blacksquare$
DM6. Base ($n=0$): $|\mathcal{P}(\emptyset)| = |\{\emptyset\}| = 1 = 2^0$. ✓
Inductive step: Let $|A| = k$ with $|\mathcal{P}(A)| = 2^k$. Let $A' = A \cup \{x\}$ where $x \notin A$, so $|A'| = k+1$. Every subset of $A'$ either contains $x$ or doesn't. Subsets not containing $x$ are exactly the subsets of $A$: there are $2^k$. Subsets containing $x$ are of the form $S \cup \{x\}$ for $S \subseteq A$: there are $2^k$. Total: $2^k + 2^k = 2^{k+1}$. ✓ $\blacksquare$
Module 6 – Class 2: Strong Induction and Recursive Definitions
Learning Objectives
- State and apply the principle of strong induction.
- Distinguish strong induction from ordinary induction.
- Write recursive definitions (sequences, sets, functions).
- Prove properties of recursively defined objects.
- Implement recursive functions in Java and prove their correctness/termination.
Concept Overview
Strong Induction
Ordinary induction assumes $P(k)$ to prove $P(k+1)$.
Strong induction assumes $P(n_0), P(n_0+1), \ldots, P(k)$ to prove $P(k+1)$.
Formally, to prove $P(n)$ for all $n \geq n_0$:
- Base case(s): Prove $P(n_0)$ (and possibly $P(n_0+1), \ldots, P(n_0 + j)$).
- Inductive step: Assume $P(n_0), P(n_0+1), \ldots, P(k)$ for some $k$. Prove $P(k+1)$.
Strong induction is logically equivalent to ordinary induction but sometimes more natural.
When to Use Strong Induction
- When the proof of $P(k+1)$ requires $P(j)$ for some $j < k$ (not just $P(k)$).
- Divide-and-conquer algorithms: proving correctness when the problem splits into subproblems of varying size.
- Proving unique factorization: factoring $n$ uses factorizations of divisors less than $n$.
Recursive Definitions
A recursive definition specifies:
- Base case(s): Explicitly define the object for small inputs.
- Recursive case: Define the object in terms of smaller instances.
| Object | Base | Recursive Rule |
|---|---|---|
| $n!$ | $0! = 1$ | $n! = n \cdot (n-1)!$ |
| $F_n$ (Fibonacci) | $F_0 = 0, F_1 = 1$ | $F_n = F_{n-1} + F_{n-2}$ |
| $\sum_{i=1}^n a_i$ | $\sum_{i=1}^{1} a_i = a_1$ | $\sum_{i=1}^{n} a_i = \left(\sum_{i=1}^{n-1} a_i\right) + a_n$ |
Formal Notation
Strong Induction Principle:
Worked Examples
Example 1: Every Integer $> 1$ Has a Prime Factor
Claim: Every integer $n > 1$ has a prime factor.
Proof by strong induction on $n$.
Base case ($n = 2$): 2 is prime, so it is its own prime factor. ✓
Inductive step: Assume every integer $j$ with $2 \leq j \leq k$ has a prime factor.
Consider $k + 1$. If $k + 1$ is prime, it is its own prime factor. ✓
If $k + 1$ is composite, then $k + 1 = ab$ where $2 \leq a, b \leq k$. By the inductive hypothesis, $a$ has a prime factor $p$. Since $p \mid a$ and $a \mid (k+1)$, we have $p \mid (k+1)$ (by transitivity of divisibility, Module 1). ✓ $\blacksquare$
Example 2: Fundamental Theorem of Arithmetic (Existence)
Claim: Every integer $n > 1$ can be written as a product of primes.
Proof by strong induction.
Base case ($n = 2$): $2$ is prime, so it is a product of one prime. ✓
Inductive step: Assume every integer $j$ with $2 \leq j \leq k$ has a prime factorization.
If $k+1$ is prime, it is a product of one prime. ✓
If $k+1$ is composite, then $k+1 = ab$ with $2 \leq a, b \leq k$. By hypothesis, both $a$ and $b$ have prime factorizations. Concatenating them gives a prime factorization of $k+1$. ✓ $\blacksquare$
Example 3: Fibonacci Numbers
Claim: $F_n < 2^n$ for all $n \geq 0$.
Base cases: $F_0 = 0 < 1 = 2^0$. $F_1 = 1 < 2 = 2^1$. ✓
Inductive step: Assume $F_j < 2^j$ for all $j \leq k$ where $k \geq 1$.
✓ $\blacksquare$
Example 4: Euclidean Algorithm Terminates (Module 1 Connection)
Claim: gcd(a, b) terminates for all $a \geq 0, b \geq 0$ with $a + b > 0$.
Proof by strong induction on $b$.
Base case ($b = 0$): The algorithm returns $a$ immediately. ✓
Inductive step: Assume the algorithm terminates for all inputs with second argument $< k+1$. The algorithm computes $r = a \bmod (k+1)$, where $0 \leq r < k+1$, then calls gcd(k+1, r). Since $r < k+1$, the inductive hypothesis applies, so this call terminates. ✓ $\blacksquare$
Example 5: Recursive Definition and Proof — Towers of Hanoi
Recursive definition: $T(n) =$ minimum number of moves to transfer $n$ disks.
- $T(1) = 1$
- $T(n) = 2T(n-1) + 1$ for $n > 1$
Claim: $T(n) = 2^n - 1$.
Base ($n = 1$): $T(1) = 1 = 2^1 - 1$. ✓
Inductive step: $T(k+1) = 2T(k) + 1 = 2(2^k - 1) + 1 = 2^{k+1} - 1$. ✓ $\blacksquare$
Proof Techniques Spotlight
Choosing Between Ordinary and Strong Induction
- Ordinary induction: Sufficient when $P(k+1)$ follows from $P(k)$ alone. Simpler.
- Strong induction: Necessary when the step requires $P(j)$ for arbitrary $j < k+1$. Common in divisibility, factorization, and divide-and-conquer arguments.
Verifying Recursive Definitions Are Well-Defined
A recursive definition is well-defined if:
- Every input eventually reduces to a base case.
- The recursive cases do not create circular dependencies.
This parallels proving termination of recursive functions.
Java Deep Dive
import java.util.*;
public class StrongInductionLibrary {
// --- Fibonacci ---
/**
* Naive recursive Fibonacci.
* Correctness: by definition F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2).
* Warning: exponential time! O(2^n).
*/
public static long fibRecursive(int n) {
if (n <= 0) return 0;
if (n == 1) return 1;
return fibRecursive(n - 1) + fibRecursive(n - 2);
}
/**
* Iterative Fibonacci with loop invariant.
* Invariant: after iteration i, prev = F(i-1), curr = F(i).
* O(n) time, O(1) space.
*/
public static long fibIterative(int n) {
if (n <= 0) return 0;
long prev = 0, curr = 1;
for (int i = 2; i <= n; i++) {
long next = prev + curr;
prev = curr;
curr = next;
// Invariant: prev == F(i-1), curr == F(i)
}
return curr;
}
/**
* Memoized Fibonacci using dynamic programming.
* O(n) time, O(n) space.
*/
public static long fibMemoized(int n) {
if (n <= 0) return 0;
long[] dp = new long[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
// --- Prime Factorization (Strong Induction) ---
/**
* Recursive prime factorization.
* Base: if n is prime, return [n].
* Recursive: find smallest factor d > 1, return [d] + factor(n/d).
*
* Correctness: By strong induction on n.
* Termination: n/d < n, so the argument strictly decreases.
*/
public static List<Integer> primeFactors(int n) {
List<Integer> factors = new ArrayList<>();
primeFactorsHelper(n, factors);
return factors;
}
private static void primeFactorsHelper(int n, List<Integer> factors) {
if (n <= 1) return;
// Find smallest divisor > 1
for (int d = 2; d * d <= n; d++) {
if (n % d == 0) {
factors.add(d);
primeFactorsHelper(n / d, factors);
return;
}
}
// n is prime
factors.add(n);
}
// --- Towers of Hanoi ---
/**
* Recursive Hanoi: move n disks from 'from' to 'to' using 'aux'.
* T(n) = 2^n - 1 moves.
*/
public static int hanoi(int n, String from, String to, String aux) {
if (n == 0) return 0;
int moves = 0;
moves += hanoi(n - 1, from, aux, to);
System.out.println(" Move disk " + n + " from " + from + " to " + to);
moves += 1;
moves += hanoi(n - 1, aux, to, from);
return moves;
}
// --- Recurrence: T(n) = 2T(n/2) + n ---
/**
* Simulates merge sort recurrence.
* By strong induction / master theorem: T(n) = O(n log n).
*/
public static int mergeSortWork(int n) {
if (n <= 1) return 0;
return 2 * mergeSortWork(n / 2) + n;
}
// --- Verification ---
public static void verifyFibBound(int max) {
System.out.println("Verifying F(n) < 2^n...");
for (int n = 0; n <= max; n++) {
long fib = fibIterative(n);
long pow = 1L << n;
assert fib < pow : "F(" + n + ") = " + fib + " >= 2^" + n;
}
System.out.println("Verified up to n = " + max);
}
public static void main(String[] args) {
System.out.println("=== Strong Induction Library ===\n");
// Fibonacci
System.out.println("Fibonacci:");
for (int n = 0; n <= 15; n++) {
System.out.printf(" F(%d) = %d (iter=%d, memo=%d)%n",
n, fibRecursive(n), fibIterative(n), fibMemoized(n));
}
// Prime factorization
System.out.println("\nPrime factorization (strong induction):");
int[] testNums = {2, 12, 60, 97, 360, 1001};
for (int n : testNums) {
System.out.println(" " + n + " = " + primeFactors(n));
}
// Towers of Hanoi
System.out.println("\nTowers of Hanoi (n=3):");
int moves = hanoi(3, "A", "C", "B");
System.out.println(" Total moves: " + moves + " (expected: " + ((1 << 3) - 1) + ")");
// Merge sort recurrence
System.out.println("\nMerge sort work:");
for (int n : new int[]{1, 2, 4, 8, 16, 32, 64}) {
System.out.println(" T(" + n + ") = " + mergeSortWork(n));
}
System.out.println();
verifyFibBound(60);
}
}Historical Context
Strong induction appears implicitly in Euclid's proof of the infinitude of primes and his fundamental result that every integer can be factored into primes.
The Fibonacci sequence was introduced by Leonardo of Pisa (Fibonacci) in Liber Abaci (1202) as a model of rabbit population growth. It appears in countless natural phenomena, and the ratio $F_{n+1}/F_n$ converges to the golden ratio $\phi = \frac{1+\sqrt{5}}{2}$.
The Towers of Hanoi puzzle was invented by Édouard Lucas (1883). The recurrence $T(n) = 2T(n-1)+1$ is one of the simplest nontrivial recurrences, and its analysis illustrates the power of induction applied to recursive definitions.
Slide-Ready Problem Sets
Slide Set A: Conceptual Questions
A1. What is the difference between ordinary induction and strong induction?
A2. Why does the proof that "every integer > 1 has a prime factor" require strong induction?
A3. Give a recursive definition of $n!$ with base case and recursive case.
A4. Why does a recursive function need a base case?
Slide Set B: Proof Problems
B1. Use strong induction to prove: every integer $n \geq 2$ is either prime or a product of primes.
B2. Prove by induction: $F_n \geq \phi^{n-2}$ for $n \geq 1$, where $\phi = \frac{1+\sqrt{5}}{2}$.
B3. Prove: if $T(1) = 1$ and $T(n) = 2T(n-1) + 1$, then $T(n) = 2^n - 1$.
Slide Set C: Java Coding Problems
C1. Implement Fibonacci iteratively and recursively. Time the naive recursive version for $n = 40$ and the iterative for $n = 40$. Observe the difference.
C2. Implement recursive prime factorization. Verify the product of factors equals $n$.
C3. Implement Towers of Hanoi. Verify the move count equals $2^n - 1$.
Full Problem Set
Discrete Math Problems
DM1. Prove by strong induction: every integer $n \geq 12$ can be expressed as $4a + 5b$ for non-negative integers $a, b$. (Hint: base cases $n = 12, 13, 14, 15$.)
DM2. Prove by strong induction: the Euclidean algorithm terminates in at most $2\lfloor\log_2(\min(a,b))\rfloor + 1$ steps.
DM3. Prove: $F_1 + F_3 + F_5 + \cdots + F_{2n-1} = F_{2n}$ for all $n \geq 1$.
DM4. Define $a_1 = 1, a_2 = 3$, and $a_n = a_{n-1} + 2a_{n-2}$ for $n \geq 3$. Prove by strong induction: $a_n = 2^n + (-1)^n$ divided by 3. (Actually $a_n = \frac{2^n - (-1)^n}{3}$.)
DM5. Use strong induction to prove: a binary tree with $n$ nodes has $n - 1$ edges. (Preview of Module 9.)
Java Programming Problems
JP1. Implement three Fibonacci methods: naive recursive, iterative, memoized. Compare timing for $n = 30, 35, 40, 45$.
JP2. Implement primeFactors(n) recursively. Verify: (a) all factors are prime, (b) their product equals $n$.
JP3. Implement the recurrence $a_n = a_{n-1} + 2a_{n-2}$ with $a_1 = 1, a_2 = 3$. Verify the closed form $a_n = \frac{2^n - (-1)^n}{3}$ for $n = 1$ to 30.
JP4. Implement Towers of Hanoi. Count moves and verify $= 2^n - 1$. Print the sequence of moves for $n = 4$.
JP5. Implement int stageCoins(int n) that computes the minimum number of coins (denominations 1, 5, 10, 25) to make change for $n$ cents, using recursion with memoization.
Bridge Problems
BR1. From Module 2: the Fundamental Theorem of Arithmetic says every $n > 1$ has a unique prime factorization. Prove uniqueness by strong induction (harder than existence). Connect to Module 2's factorization code.
BR2. From Module 5: prove that the number of functions from an $n$-element set to a 2-element set is $2^n$ using induction. Connect to Module 4's power set result ($|\mathcal{P}(A)| = 2^{|A|}$) by showing a bijection between subsets and characteristic functions.
Solutions
Discrete Math Solutions
DM1. Base cases: $12 = 4(3), 13 = 4(2)+5(1), 14 = 4(1)+5(2), 15 = 5(3)$. ✓
Inductive step: Assume all integers from 12 to $k$ can be expressed. For $k+1 \geq 16$: since $k+1 - 4 \geq 12$, by hypothesis $k-3 = 4a + 5b$. Then $k+1 = 4(a+1) + 5b$. ✓ $\blacksquare$
DM3. Base ($n=1$): $F_1 = 1 = F_2$. ✓
Inductive step: Assume $F_1 + F_3 + \cdots + F_{2k-1} = F_{2k}$.
$F_1 + F_3 + \cdots + F_{2k+1} = F_{2k} + F_{2k+1} = F_{2k+2} = F_{2(k+1)}$. ✓ $\blacksquare$
DM5. A tree with 1 node has 0 edges = $1 - 1$. ✓ For a tree with $k+1$ nodes, removing a leaf gives a tree with $k$ nodes and $k-1$ edges (by hypothesis). Adding the leaf back adds exactly 1 edge. Total: $k - 1 + 1 = k = (k+1) - 1$. ✓ $\blacksquare$
Module 6 – Class 3: Recursive Sets and Structural Induction
Learning Objectives
- Define sets and data structures recursively (arithmetic expressions, binary trees).
- Apply structural induction to prove properties of recursively defined objects.
- Connect structural induction to recursive program correctness.
- Implement recursive data structures in Java and prove properties about them.
Concept Overview
Recursively Defined Sets
A set $S$ is recursively defined by:
- Basis: Specify initial elements in $S$.
- Recursive rule: Specify how to build new elements from existing ones.
- Closure: $S$ contains only elements obtained by finitely many applications of the basis and rules.
Example: Arithmetic Expressions
- Basis: Any integer $n$ is an expression.
- Recursive rules: If $e_1, e_2$ are expressions, so are $(e_1 + e_2)$ and $(e_1 \times e_2)$.
Example: Binary Trees
- Basis:
nullis a binary tree (the empty tree). - Recursive rule: If $T_L$ and $T_R$ are binary trees and $v$ is a value, then $\text{Node}(v, T_L, T_R)$ is a binary tree.
Structural Induction
To prove a property $P$ holds for all elements of a recursively defined set:
- Base case(s): Prove $P$ for each basis element.
- Inductive step: For each recursive rule, assume $P$ holds for the sub-components (inductive hypothesis). Prove $P$ for the new element.
Structural induction generalizes mathematical induction from natural numbers to arbitrary recursively defined structures.
The Pattern
| Mathematical Induction | Structural Induction |
|---|---|
| Prove for $n_0$ | Prove for basis elements |
| Assume $P(k)$, prove $P(k+1)$ | Assume $P$ for sub-structures, prove $P$ for composite |
| Works on $\mathbb{N}$ | Works on any recursive definition |
Formal Notation
For binary trees with the definition $T ::= \text{null} \mid \text{Node}(v, L, R)$:
Worked Examples
Example 1: Full Binary Tree Theorem
Claim: In a non-empty full binary tree (every node has 0 or 2 children), the number of leaves $L$ equals the number of internal nodes $I$ plus one: $L = I + 1$.
Proof by structural induction.
Base case: A single node (no children). $L = 1, I = 0$. $1 = 0 + 1$. ✓
Inductive step: A full binary tree $T = \text{Node}(v, T_L, T_R)$ where both $T_L, T_R$ are non-empty full binary trees (since the root has 2 children).
By hypothesis: $L_L = I_L + 1$ and $L_R = I_R + 1$.
For $T$: $L = L_L + L_R$ (leaves come from subtrees), $I = I_L + I_R + 1$ (internal nodes of subtrees plus root).
✓ $\blacksquare$
Example 2: Size of an Expression Tree
Define $\text{size}(e)$ recursively:
- $\text{size}(n) = 1$ for any integer $n$.
- $\text{size}(e_1 \oplus e_2) = \text{size}(e_1) + \text{size}(e_2) + 1$ for $\oplus \in \{+, \times\}$.
Claim: $\text{size}(e) = 2 \cdot \text{ops}(e) + 1$, where $\text{ops}(e)$ is the number of operations.
Base: $\text{size}(n) = 1, \text{ops}(n) = 0$. $1 = 2(0) + 1$. ✓
Inductive step: $\text{size}(e_1 \oplus e_2) = \text{size}(e_1) + \text{size}(e_2) + 1 = (2\text{ops}(e_1)+1) + (2\text{ops}(e_2)+1) + 1 = 2(\text{ops}(e_1) + \text{ops}(e_2) + 1) + 1 = 2\text{ops}(e_1 \oplus e_2) + 1$. ✓ $\blacksquare$
Example 3: Evaluator Correctness
Define eval on expression trees:
eval(IntLit(n)) = n
eval(Add(e1, e2)) = eval(e1) + eval(e2)
eval(Mul(e1, e2)) = eval(e1) * eval(e2)Claim: eval computes the standard mathematical value of the expression.
This follows directly from structural induction: the base case agrees with the math, and each recursive case combines results correctly because addition and multiplication on Java int match the mathematical operations (within overflow bounds). $\blacksquare$
Example 4: Number of Nodes in a Binary Tree
Claim: size(null) = 0 and size(Node(v, L, R)) = 1 + size(L) + size(R) correctly returns the number of nodes.
Base: size(null) = 0. An empty tree has 0 nodes. ✓
Inductive step: Assume size(L) returns the node count of $L$ and size(R) returns the node count of $R$. Then 1 + size(L) + size(R) counts the root plus all nodes in the subtrees. ✓ $\blacksquare$
Example 5: Height and Node Count
Claim: A binary tree of height $h$ has at most $2^{h+1} - 1$ nodes.
Base ($h = 0$): A tree of height 0 is a single node: $1 \leq 2^1 - 1 = 1$. ✓
Inductive step: A tree of height $h+1$ has a root with subtrees of height $\leq h$. By hypothesis, each subtree has $\leq 2^{h+1} - 1$ nodes. Total: $\leq 1 + 2(2^{h+1} - 1) = 2^{h+2} - 1$. ✓ $\blacksquare$
Proof Techniques Spotlight
The Structural Induction Template
- Identify the recursively defined set/structure.
- State the property $P$ to prove.
- Base case(s): Verify $P$ for each basis element.
- Inductive step: For each constructor/rule, assume $P$ for sub-components, prove for the whole.
- Conclude: By structural induction.
Common Pitfall: Missing Constructors
If the recursive definition has multiple rules (e.g., Add and Mul), the inductive step must handle each rule separately.
Java Deep Dive
import java.util.*;
public class StructuralInductionLibrary {
// ===== Arithmetic Expression Trees =====
interface Expr {
int eval();
int size();
int ops();
String toInfix();
}
static class IntLit implements Expr {
final int value;
IntLit(int value) { this.value = value; }
public int eval() { return value; }
public int size() { return 1; }
public int ops() { return 0; }
public String toInfix() { return String.valueOf(value); }
}
static class Add implements Expr {
final Expr left, right;
Add(Expr left, Expr right) {
this.left = left;
this.right = right;
}
public int eval() { return left.eval() + right.eval(); }
public int size() { return left.size() + right.size() + 1; }
public int ops() { return left.ops() + right.ops() + 1; }
public String toInfix() {
return "(" + left.toInfix() + " + " + right.toInfix() + ")";
}
}
static class Mul implements Expr {
final Expr left, right;
Mul(Expr left, Expr right) {
this.left = left;
this.right = right;
}
public int eval() { return left.eval() * right.eval(); }
public int size() { return left.size() + right.size() + 1; }
public int ops() { return left.ops() + right.ops() + 1; }
public String toInfix() {
return "(" + left.toInfix() + " * " + right.toInfix() + ")";
}
}
// ===== Binary Tree =====
static class TreeNode {
int value;
TreeNode left, right;
TreeNode(int value) { this.value = value; }
TreeNode(int value, TreeNode left, TreeNode right) {
this.value = value;
this.left = left;
this.right = right;
}
}
/**
* Size: number of nodes.
* Correctness by structural induction (Example 4 above).
*/
static int size(TreeNode root) {
if (root == null) return 0;
return 1 + size(root.left) + size(root.right);
}
/**
* Height: length of longest root-to-leaf path.
* Height of empty tree is -1 (convention).
*/
static int height(TreeNode root) {
if (root == null) return -1;
return 1 + Math.max(height(root.left), height(root.right));
}
/**
* Count leaves.
* In a full binary tree: leaves = internal + 1.
*/
static int countLeaves(TreeNode root) {
if (root == null) return 0;
if (root.left == null && root.right == null) return 1;
return countLeaves(root.left) + countLeaves(root.right);
}
/**
* Count internal nodes (nodes with at least one child).
*/
static int countInternal(TreeNode root) {
if (root == null) return 0;
if (root.left == null && root.right == null) return 0;
return 1 + countInternal(root.left) + countInternal(root.right);
}
/**
* Check if a tree is full (every node has 0 or 2 children).
*/
static boolean isFull(TreeNode root) {
if (root == null) return true;
boolean hasLeft = root.left != null;
boolean hasRight = root.right != null;
if (hasLeft != hasRight) return false; // exactly one child
return isFull(root.left) && isFull(root.right);
}
/**
* Build a complete full binary tree of given height.
*/
static TreeNode buildFullTree(int height, int[] counter) {
if (height < 0) return null;
TreeNode node = new TreeNode(counter[0]++);
if (height > 0) {
node.left = buildFullTree(height - 1, counter);
node.right = buildFullTree(height - 1, counter);
}
return node;
}
/**
* Inorder traversal.
*/
static List<Integer> inorder(TreeNode root) {
List<Integer> result = new ArrayList<>();
inorderHelper(root, result);
return result;
}
private static void inorderHelper(TreeNode root, List<Integer> result) {
if (root == null) return;
inorderHelper(root.left, result);
result.add(root.value);
inorderHelper(root.right, result);
}
// ===== Demonstration =====
public static void main(String[] args) {
System.out.println("=== Structural Induction Library ===\n");
// --- Expression Trees ---
// (3 + 5) * (2 + 4) = 8 * 6 = 48
Expr expr = new Mul(
new Add(new IntLit(3), new IntLit(5)),
new Add(new IntLit(2), new IntLit(4))
);
System.out.println("Expression: " + expr.toInfix());
System.out.println(" eval = " + expr.eval());
System.out.println(" size = " + expr.size());
System.out.println(" ops = " + expr.ops());
System.out.println(" size == 2*ops + 1? " + (expr.size() == 2 * expr.ops() + 1));
// --- Binary Trees ---
System.out.println("\nFull binary tree (height 3):");
TreeNode tree = buildFullTree(3, new int[]{1});
System.out.println(" Size: " + size(tree));
System.out.println(" Height: " + height(tree));
System.out.println(" Leaves: " + countLeaves(tree));
System.out.println(" Internal: " + countInternal(tree));
System.out.println(" Full: " + isFull(tree));
System.out.println(" L = I+1? " + (countLeaves(tree) == countInternal(tree) + 1));
System.out.println(" Inorder: " + inorder(tree));
// Verify properties for full trees of various heights
System.out.println("\nVerifying full binary tree properties:");
for (int h = 0; h <= 6; h++) {
TreeNode t = buildFullTree(h, new int[]{1});
int s = size(t);
int leaves = countLeaves(t);
int internal = countInternal(t);
int expectedNodes = (1 << (h + 1)) - 1; // 2^(h+1) - 1
System.out.printf(" h=%d: nodes=%d (exp %d), leaves=%d, internal=%d, L=I+1? %b%n",
h, s, expectedNodes, leaves, internal, leaves == internal + 1);
assert s == expectedNodes;
assert leaves == internal + 1;
}
}
}Historical Context
Structural induction emerged from the formalization of recursive definitions in mathematical logic and formal language theory in the 20th century. Stephen Kleene and Alonzo Church studied recursive functions in the 1930s, laying the groundwork for both recursion theory and programming.
Context-free grammars (Chomsky, 1956) define languages recursively, and proofs about parse trees use structural induction. Every compiler course relies on these ideas.
The connection between recursive data structures and structural induction was made explicit in type theory (Martin-Löf, 1970s), where induction principles are automatically generated from data type definitions — a practice now common in proof assistants like Coq, Agda, and Lean.
Slide-Ready Problem Sets
Slide Set A: Conceptual Questions
A1. How does structural induction differ from mathematical induction on $\mathbb{N}$?
A2. Give the recursive definition of a binary tree.
A3. For the expression $(3 + (5 \times 2))$, draw the tree and compute eval, size, and ops.
A4. Why do we need a base case for null trees?
Slide Set B: Proof Problems
B1. Prove by structural induction: in any binary tree, the number of null pointers is one more than the number of nodes.
B2. Prove: eval(Mul(e1, e2)) = eval(e1) * eval(e2) correctly computes the product for all expressions $e_1, e_2$.
B3. Prove: a full binary tree of height $h$ has exactly $2^{h+1} - 1$ nodes.
Slide Set C: Java Coding Problems
C1. Implement the Expr interface with IntLit, Add, and Mul. Add a Sub variant.
C2. Write countLeaves and countInternal for binary trees. Verify $L = I + 1$ on full trees.
C3. Implement a method that builds an expression tree from a postfix string (e.g., "3 5 + 2 *") and evaluates it.
Full Problem Set
Discrete Math Problems
DM1. Give a recursive definition of the set of all balanced parentheses strings. Prove by structural induction that every string in the set has equal numbers of ( and ).
DM2. Prove by structural induction: the number of null children in a binary tree with $n$ nodes is $n + 1$.
DM3. Define the depth of an expression: $\text{depth}(n) = 0$, $\text{depth}(e_1 \oplus e_2) = 1 + \max(\text{depth}(e_1), \text{depth}(e_2))$. Prove: $\text{ops}(e) \leq 2^{\text{depth}(e)} - 1$.
DM4. Prove by structural induction: the mirror of a binary tree (swap left and right at every node) preserves the number of nodes.
DM5. Prove: $\text{height}(T) \leq \text{size}(T) - 1$ for every non-empty binary tree $T$.
Java Programming Problems
JP1. Implement Expr with IntLit, Add, Mul, Sub, Div. Add eval(), size(), toInfix(), toPostfix().
JP2. Build a postfix expression evaluator using a stack. Verify it matches eval() on the tree.
JP3. Implement mirror(TreeNode root) that returns a new tree with left/right swapped. Verify size(mirror(T)) == size(T) and height(mirror(T)) == height(T).
JP4. Implement isBalanced(TreeNode root) that returns true iff the heights of left and right subtrees differ by at most 1, recursively. Test on balanced and unbalanced trees.
JP5. Write a method that generates all binary trees with $n$ nodes (Catalan number enumeration). Count them and verify the count matches the $n$-th Catalan number $C_n = \frac{1}{n+1}\binom{2n}{n}$.
Bridge Problems
BR1. From Module 4: the power set of an $n$-element set has $2^n$ elements (proved by induction in Class 1). Structural induction on a binary tree of decisions ($\in / \notin$) gives an alternative proof: each path from root to leaf corresponds to a subset.
BR2. From Module 5: functions from $A$ to $\{0,1\}$ correspond bijectively to subsets of $A$. Express this correspondence using expression trees: an expression (x_1 AND x_2) OR (NOT x_3) defines a subset of $\{0,1\}^3$ via its truth set. Implement and evaluate.
Solutions
Discrete Math Solutions
DM1. Recursive definition: (i) $\varepsilon$ (empty string) is balanced. (ii) If $s$ is balanced, then $(s)$ is balanced. (iii) If $s_1, s_2$ are balanced, then $s_1 s_2$ is balanced.
Proof: Base: $\varepsilon$ has 0 (s and 0 )s. ✓ Rule (ii): If $s$ has equal ( and ), then $(s)$ adds one of each. ✓ Rule (iii): If $s_1$ and $s_2$ each have equal ( and ), so does $s_1 s_2$. ✓ $\blacksquare$
DM2. Base: null tree has 0 nodes and 1 null child (itself). $0 + 1 = 1$. ✓
Inductive step: $\text{Node}(v, L, R)$ has $n = 1 + n_L + n_R$ nodes. By hypothesis, $L$ has $n_L + 1$ null children and $R$ has $n_R + 1$. The full tree has $n_L + 1 + n_R + 1 = n_L + n_R + 2 = (1 + n_L + n_R) + 1 = n + 1$. ✓ $\blacksquare$
DM4. Base: mirror(null) = null. Both have 0 nodes. ✓
Inductive step: mirror(Node(v, L, R)) = Node(v, mirror(R), mirror(L)). By hypothesis, size(mirror(L)) = size(L) and size(mirror(R)) = size(R). So size(mirror(T)) = 1 + size(mirror(R)) + size(mirror(L)) = 1 + size(R) + size(L) = size(T). ✓ $\blacksquare$