Home All Subjects Progress Videos Graphics

Progress

241 / 241 subjects

Phases

29-03 — Induction Deep Dive

Phase: 29 — Proof Techniques Subject: 29-03 Prerequisites: 03-08 (Mathematical Induction), 29-01 (Direct Proof), 29-02 (Proof by Contradiction) Next subject: 29-04 — Proof by Cases and Pigeonhole Arguments

Learning Objectives

By the end of this subject, you will be able to:

  1. Apply strong induction when the inductive step depends on multiple previous cases
  2. Use structural induction for recursively defined objects (strings, trees, formulas)
  3. Apply the Well-Ordering Principle as an alternative to induction
  4. Recognise when standard induction fails and strong/structural induction is needed
  5. Prove statements about algorithms and data structures using induction

Core Content

1. Standard (Weak) Induction Recap

Standard induction proves $P(n)$ for all $n \geq n_0$:

  1. Base case: Prove $P(n_0)$
  2. Inductive step: Assume $P(k)$ for arbitrary $k \geq n_0$. Prove $P(k+1)$.

The inductive hypothesis is $P(k)$ — only the immediately preceding case.

2. Strong Induction

Strong induction assumes ALL previous cases, not just $P(k)$:

  1. Base case: Prove $P(n_0)$ (often need multiple base cases)
  2. Inductive step: Assume $P(n_0), P(n_0+1), ..., P(k)$ are all true. Prove $P(k+1)$.

When to use: - When $P(k+1)$ depends on $P(k)$, $P(k-1)$, or even earlier cases - When the natural decomposition of $k+1$ uses values other than $k$ - When proving statements about recursive definitions

Example: Prove every integer $n \geq 2$ has a prime factorisation.

Base: $n = 2$ is prime. ✓ Inductive step: Assume all $2 \leq m \leq k$ have prime factorisations. For $k+1$: - If $k+1$ is prime: done. - If composite: $k+1 = ab$ where $2 \leq a, b < k+1$. By strong IH, both $a$ and $b$ have prime factorisations. Multiplying gives $k+1$'s factorisation. ✓

3. Structural Induction

Structural induction proves properties of recursively defined objects.

Template: 1. Base: Prove $P$ for the base objects of the recursion 2. Constructor step: Assume $P$ holds for the components. Prove $P$ holds for objects constructed from them.

Example: Prove all well-formed formulas (WFFs) in propositional logic have equal numbers of left and right parentheses.

Base: Atomic formulas ($p, q, r$) have 0 parentheses. ✓ Constructor: If $\phi$ has $a$ left and $a$ right parentheses, and $\psi$ has $b$ left and $b$ right: - $\neg\phi$: same count, $a = a$ - $(\phi \land \psi)$: adds 1 left and 1 right, so $a+1$ and $b+1$ ✓

4. The Well-Ordering Principle (WOP)

WOP: Every non-empty subset of $\mathbb{N}$ has a least element.

WOP is equivalent to standard induction. You can prove either from the other.

Using WOP: 1. Assume the set $S = \{n \in \mathbb{N} : P(n) \text{ is false}\}$ is non-empty 2. Let $m = \min S$ (exists by WOP) 3. Derive a contradiction by showing $P(m)$ must be true

Example: Prove $\sqrt{n}$ irrational for non-square $n$. Assume $S = \{n : \sqrt{n} \text{ is rational but } n \text{ is not a perfect square}\}$ is non-empty. Let $m = \min S$. Write $\sqrt{m} = a/b$ in lowest terms. $m = a^2/b^2$, so $b^2 \mid a^2$ and $a^2 = mb^2$. Since $m$ is minimal and not a perfect square, derive contradiction.

5. Induction on Algorithms

Induction is essential for proving algorithm correctness.

Example: Prove binary search on a sorted array of size $n$ runs in $O(\log n)$ time.

Base: $n = 1$: one comparison, $\lceil \log_2 1 \rceil = 0$... need careful base. Inductive step: Binary search checks the middle element ($O(1)$), then recurses on at most $\lfloor n/2 \rfloor$ elements. By IH, this takes $O(\log(n/2)) = O(\log n - 1) = O(\log n)$. Total: $O(1 + \log n) = O(\log n)$. ✓

Worked Examples

Example 1: Strong Induction — Fibonacci Identities

Problem: Prove that every integer $n \geq 1$ can be written as a sum of distinct, non-consecutive Fibonacci numbers (Zeckendorf's theorem).

Solution:

This requires strong induction. Let $P(n)$ = "$n$ can be written as a sum of distinct non-consecutive Fibonacci numbers."

Base cases: $P(1)$: $1 = F_1$. ✓ $P(2)$: $2 = F_2$ (using $F_1 = 1, F_2 = 2$). ✓ $P(3)$: $3 = F_3$. ✓ $P(4)$: $4 = 3 + 1 = F_3 + F_1$ (non-consecutive: $F_3, F_1$ skip $F_2$). ✓

Inductive step: Assume $P(m)$ holds for all $1 \leq m \leq k$. Prove $P(k+1)$.

Let $F_j$ be the largest Fibonacci number $\leq k+1$. Then $k+1 - F_j < F_{j-1}$ (property of Fibonacci numbers).

By strong IH, $k+1 - F_j$ has a Zeckendorf representation using only Fibonacci numbers $F_1$ through $F_{j-2}$ (all $< F_{j-1}$).

Adding $F_j$ gives a representation of $k+1$ using non-consecutive Fibonacci numbers (since the largest in the remainder is $F_{j-2}$, which is not consecutive with $F_j$). ✓

Answer: Zeckendorf's theorem is proven by strong induction.

Example 2: Structural Induction — Tree Property

Problem: Prove that in any binary tree, the number of leaves $L$ equals the number of nodes with two children $N_2$ plus 1: $L = N_2 + 1$.

Solution:

Base: A single node tree has $L = 1$ leaf and $N_2 = 0$ nodes with two children. $1 = 0 + 1$. ✓

Constructor step: Assume the property holds for two trees $T_1$ and $T_2$: - $L_1 = N_2^{(1)} + 1$ - $L_2 = N_2^{(2)} + 1$

Create a new tree by adding a root with $T_1$ as left child and $T_2$ as right child: - New leaves: $L = L_1 + L_2$ (root is not a leaf) - New $N_2$: $N_2 = N_2^{(1)} + N_2^{(2)} + 1$ (the new root has two children)

Check: $L = L_1 + L_2 = (N_2^{(1)} + 1) + (N_2^{(2)} + 1) = (N_2^{(1)} + N_2^{(2)} + 1) + 1 = N_2 + 1$. ✓

Answer: By structural induction, $L = N_2 + 1$ for all binary trees.

Example 3: Well-Ordering Principle — Division Algorithm

Problem: Prove that for any integers $a, b$ with $b > 0$, there exist unique integers $q, r$ such that $a = bq + r$ and $0 \leq r < b$ (Division Algorithm).

Solution (using WOP):

Consider $S = \{a - bk : k \in \mathbb{Z}, a - bk \geq 0\}$. If $a \geq 0$: $S$ is non-empty (take $k = 0$). If $a < 0$: take $k$ very negative so $a - bk > 0$. By WOP, $S$ has a minimum $r = a - bq$ for some $q$.

By minimality of $r$: if $r \geq b$, then $r - b = a - b(q+1) \in S$ and $r - b < r$, contradicting minimality. So $0 \leq r < b$.

Uniqueness: If $a = bq_1 + r_1 = bq_2 + r_2$ with $0 \leq r_1, r_2 < b$: $b(q_1 - q_2) = r_2 - r_1$. Since $|r_2 - r_1| < b$, we need $r_2 - r_1 = 0$, so $r_1 = r_2$ and $q_1 = q_2$.

Answer: Division Algorithm proven using WOP.

Practice Problems

Problem 1: Use strong induction to prove that every integer $n \geq 12$ can be written as $4a + 5b$ for non-negative integers $a, b$.

Problem 2: Prove by structural induction that any valid arithmetic expression built from numbers, $+$, and $\times$ has the same number of left and right parentheses.

Problem 3: Use WOP to prove that every positive integer has a unique prime factorisation (Fundamental Theorem of Arithmetic — existence part).

Problem 4: Prove by strong induction that every tree with $n$ nodes has exactly $n-1$ edges.

Problem 5: Prove that any amount of postage $\geq 12$ cents can be formed using 4-cent and 5-cent stamps.

Summary

  1. Strong induction assumes ALL previous cases $P(1), ..., P(k)$ to prove $P(k+1)$
  2. Structural induction proves properties of recursively defined objects (formulas, trees, lists)
  3. Well-Ordering Principle is equivalent to induction and useful for existence proofs
  4. Algorithm correctness often requires induction, especially for recursive algorithms
  5. Choose the right induction: standard for simple $k \to k+1$, strong for multi-case dependencies, structural for recursive objects

Key Terms

Pitfalls

Quiz

  1. Skipping the base case. Even if the induction step works, without verifying P(0) or P(1), the proof is incomplete. The base case anchors the domino chain.
  2. Assuming what you're trying to prove in the induction step. The induction hypothesis is P(k), not P(k+1). Don't start the step by assuming P(k+1) is true.
  3. Wrong induction hypothesis for strong induction. In strong induction, assume P(1), P(2), ..., P(k) all hold, not just P(k). Using only P(k) when you need all prior cases breaks the proof.
  4. Induction on the wrong variable. For recurrence relations, sometimes you need induction on n, sometimes on both n and k. Check which variable the recurrence actually reduces.
  5. Forgetting structural induction rules. For recursive data structures (trees, lists), the induction is on structure, not on a number. Base cases are the empty/minimal structure.
  6. Confusing well-ordering with induction. WOP says every non-empty set of naturals has a least element. Induction says if P(0) and P(k)→P(k+1), then P(n) for all n. They're equivalent, but the proof techniques differ.
  7. Using induction for uncountable sets. Induction only works on well-ordered sets (typically ℕ). You can't induct over ℝ or uncountable sets the same way.

Q1: Strong induction differs from standard induction in that:

A) It requires more base cases B) The inductive hypothesis assumes ALL previous cases, not just $P(k)$ C) It only works for prime numbers D) It is always weaker than standard induction

Correct: B)

Q2: Structural induction is used to prove properties of:

A) Only prime numbers B) Recursively defined objects (formulas, trees, lists) C) Continuous functions D) Differential equations

Correct: B)

Q3: The Well-Ordering Principle states that:

A) Every integer can be factored into primes B) Every non-empty subset of $\mathbb{N}$ has a least element C) Every proof can be written in one line D) Every number greater than 1 is prime or composite

Correct: B)

Q4: In strong induction for "every $n \geq 12$ is $4a + 5b$," the base cases include:

A) Just $n = 12$ B) $n = 12, 13, 14, 15, 16$ (to cover all residues mod 4) C) $n = 0, 1, 2, ..., 11$ D) No base cases needed

Correct: B)

Q5: WOP can be used to prove the Division Algorithm because:

A) Division is the same as multiplication B) The set $S = \{a - bk : a - bk \geq 0\}$ is non-empty, so it has a minimum by WOP C) WOP is only about prime numbers D) The Division Algorithm doesn't need proof

Correct: B)

Q6: In Zeckendorf's theorem, why is strong induction needed?

A) Because Fibonacci numbers are prime B) Because the representation of $k+1$ may use a Fibonacci number $F_j$ and the remainder $k+1-F_j$ requires the inductive hypothesis for values less than $k$ (possibly much less) C) Because all proofs about sums need strong induction D) Because Fibonacci numbers grow exponentially

Correct: B)

Q7: A proof by structural induction for binary trees requires:

A) Proving the property for all trees of height 1 B) Proving the property for a single-node tree (base) and showing that combining two trees with a root preserves the property C) Assuming all smaller trees satisfy the property D) Using contradiction

Correct: B)

Q8: Which statement about the equivalence of WOP and induction is TRUE?

A) WOP implies induction, but induction does not imply WOP B) Induction implies WOP, but WOP does not imply induction C) WOP and induction are logically equivalent — each can be derived from the other D) Neither implies the other

Correct: C)

Next Steps

Continue to 29-04 — Proof by Cases and Pigeonhole Arguments to learn how to split complex proofs into manageable cases and apply the pigeonhole principle.