Exercises: Strong Induction, Well-Ordering, and Recursive Definitions

These build from mechanical warm-ups to full proofs, code, modeling, and structural induction. Difficulty: ⭐ foundational, ⭐⭐ intermediate, ⭐⭐⭐ challenging. Worked solutions to the starred-with-a-dagger (†) and odd-numbered problems are in the appendix answers-to-selected.md; do them before you peek. For every proof, the rubric rewards a clearly stated $P(n)$, the correct number of base cases for the reach of your step, explicit use of the (strong or structural) inductive hypothesis, and a clean conclusion ending in $\blacksquare$.

Part A — Warm-ups (⭐)

7.1 † A recurrence is defined by $a_n = 2a_{n-1} - a_{n-2}$ for $n \ge 2$. How many base cases must a strong-induction proof about $a_n$ establish, and which values of $n$ are they? (Count the reach of the step — do not solve the recurrence.)

7.2 For each recurrence, state how far back the step reaches and therefore how many base cases a strong induction needs: (a) $b_n = b_{n-1} + b_{n-4}$; (b) $c_n = c_{\lfloor n/2 \rfloor} + 1$ for $n \ge 1$; (c) $d_n = d_{n-1} \cdot d_{n-2} \cdot d_{n-3}$.

7.3 † Decide whether each claim needs strong induction or whether ordinary induction suffices, and say why in one sentence: (a) $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$; (b) every integer $n \ge 2$ is a product of primes; (c) $3 \mid (4^n - 1)$ for $n \ge 0$.

7.4 Write the well-ordering principle in one sentence, then give a one-sentence reason it is false for the set $\{x \in \mathbb{Q} : x > 0\}$.

7.5 † Write a recursive definition (basis clause, recursive clause, exclusion clause) of the set of all powers of two, $\{1, 2, 4, 8, \dots\}$.

7.6 Using the recursive definition of len and append from §7.5, compute $\operatorname{append}(\texttt{Cons}(5, \texttt{Cons}(6, \texttt{Nil})), \texttt{Cons}(7, \texttt{Nil}))$ step by step, unfolding one clause at a time, and confirm its length is 3.

Part B — Prove it (⭐⭐)

7.7 † (Scaffolded — fill the missing step.) Prove by strong induction that every integer $n \ge 2$ can be written as a product of one or more primes. Fill in the blanks: - Base case ($n = 2$): $2$ is prime, so it is a product of $\underline{\hphantom{xxxx}}$ prime(s). ✓ - Strong inductive step: fix $k \ge 2$ and assume every integer $j$ with $2 \le j \le k$ is a product of primes. Consider $k + 1$. Either $k+1$ is prime — then it is a product of one prime, done — or $k+1$ is composite, so $k + 1 = a \cdot b$ with $\underline{\hphantom{xxxx}} \le a, b \le \underline{\hphantom{xxxx}}$. By the strong hypothesis, $a$ and $b$ are each products of primes, so their product $\underline{\hphantom{xxxx}}$ is too. ✓

Why does this proof need strong induction rather than ordinary induction? Answer in one sentence.

7.8 Prove by strong induction that for all $n \ge 1$, the Fibonacci number satisfies $F_n \ge \left(\frac{3}{2}\right)^{\,n-2}$ for $n \ge 3$ (check the base cases you need first). Compare the number of base cases here with the upper-bound proof $F_n \le 2^{\,n-1}$ in §7.1.

7.9 † (The postage / Chicken McNugget warm-up.) Prove by strong induction that every integer amount $n \ge 12$ cents can be made using only 4-cent and 5-cent stamps. State carefully how many base cases you check and why that number (revisit the Project Checkpoint hint in §7.6).

7.10 Prove that every integer $n \ge 8$ can be written as $n = 3a + 5b$ for some non-negative integers $a, b$. How many base cases does the step (which reduces $n$ by 3) require?

7.11 † (Well-ordering, smallest-counterexample.) Prove that every integer $n \ge 1$ is either $1$ or has a prime divisor, using the smallest-counterexample template from §7.2 (assume the set of $n \ge 2$ with no prime divisor is non-empty, take its least element, derive a contradiction).

7.12 (Structural induction.) Recall the set $E$ of arithmetic expressions from §7.3. Define $\operatorname{ops}(e)$ = the number of operators (+ or *) in $e$ and $\operatorname{nums}(e)$ = the number of basis symbols (a numeral or x) in $e$. Prove by structural induction that for every $e \in E$, $\operatorname{nums}(e) = \operatorname{ops}(e) + 1$.

7.13 † (Structural induction on trees.) For a full binary tree $T$, let $n(T)$ be its total number of nodes. Prove by structural induction that $n(T)$ is always odd. (Hint: relate $n(T)$ to the leaf/internal counts of §7.5, or induct directly on the tree definition.)

Part C — Implement it (⭐⭐)

Write Python for each. Do not run it on the grader's machine — hand-trace and include an # Expected output: comment, matching the book's convention. Reference implementations live in code/exercise-solutions.py.

7.14 † Implement make_postage(n) that returns a pair (fours, fives) of non-negative counts of 4- and 5-cent stamps summing to n, or None if impossible (this is the function from the Project Checkpoint). Then write three lines that print the results for $n = 11, 12, 27$. Which input returns None, and how does that value relate to the strong-induction theorem of Exercise 7.9?

7.15 Implement recursive_seq(step, base, n) from the Project Checkpoint — it evaluates a recursively defined sequence whose step may read all earlier terms — and use it to compute the "tribonacci" number $T_{10}$, where $T_0 = T_1 = 0$, $T_2 = 1$, and $T_n = T_{n-1} + T_{n-2} + T_{n-3}$. State the number of base cases the sequence requires.

7.16 † Implement count_nodes(tree) and count_leaves(tree) for full binary trees represented as nested tuples (a leaf is the string "L"; an internal node is (left, right)). Then verify the identity $\ell(T) = i(T) + 1$ from §7.5 on the tree (("L", "L"), "L") by printing both $\ell$ and $i$.

Part D — Find the error (⭐⭐)

Each "proof" below is wrong. State precisely which part fails and why.

7.17 † Claim: every Fibonacci number satisfies $F_n \le 2^{\,n-1}$ for $n \ge 1$. "Proof": "Base case $n = 1$: $F_1 = 1 \le 2^0 = 1$. ✓ Strong step: assume $F_j \le 2^{\,j-1}$ for all $1 \le j \le k$. Then $F_{k+1} = F_k + F_{k-1} \le 2^{\,k-1} + 2^{\,k-2} = 2^k$. ✓ Done." — The algebra of the step is fine, yet the proof is broken. Find the flaw. (Hint: at $k = 1$, what does the step reference?)

7.18 Claim: every integer $n \ge 2$ has a prime factorization. "Proof": "By ordinary induction. Base case $n = 2$ is prime. Inductive step: assume $n$ has a prime factorization; then $n + 1 \dots$" — Explain why ordinary induction's single hypothesis $P(n)$ cannot complete this step, and which hypothesis you actually need.

7.19 † Claim: the set $S$ defined by basis $5 \in S$, recursive clause "if $x \in S$ then $x + 5 \in S$" contains only multiples of 5. "Proof": "Structural induction. Basis: $5$ is a multiple of 5. ✓ Recursive step: if $x$ is a multiple of 5 then $x + 5$ is a multiple of 5. ✓ Therefore $S$ contains only multiples of 5 and equals $\{5, 10, 15, \dots\}$." — The structural-induction property proof is correct, but the final clause overreaches. What did the proof actually establish, and what extra step would be needed to conclude $S = \{5, 10, 15, \dots\}$?

7.20 Claim: "In any non-empty set of integers there is a least element, by well-ordering." "Proof": "Well-ordering says every non-empty set of naturals has a least element; integers are just naturals with signs, so the same holds." — Diagnose the error and give an explicit non-empty subset of $\mathbb{Z}$ with no least element.

Part E — Model it & Conjecture and test (⭐⭐⭐)

7.21 † (Model it.) A vending machine dispenses change using only 3-cent and 7-cent tokens. A product manager asks: "what is the largest amount of change we can never make exactly, and from which amount onward is every value makeable?" Translate this into a discrete-math statement of the form "every integer $n \ge n_0$ can be written as $3a + 7b$ with $a, b \ge 0$," conjecture $n_0$ by hand, and outline the strong-induction proof (state the base cases and the reduction the step uses). You need not write every line — give the structure.

7.22 (Model it — recursive definition.) A "well-formed parenthesis string" (a balanced bracket string) is one like (()) or ()() but not )( or ((). Give a recursive definition of the set $B$ of balanced strings over ( and ) using a basis clause and recursive clause(s), and explain why the exclusion clause is essential. (This is the Deep-Dive object previewed in the chapter's Learning Paths.)

7.23 † (Conjecture and test, then prove — structural induction.) Using your definition from 7.22, write Python that generates several balanced strings and checks, for each, that the number of ( equals the number of ). Conjecture the general statement and then prove it by structural induction on $B$. Then state one property your "equal counts" proof does not establish about balanced strings (compare §7.4's Check Your Understanding).

7.24 (Conjecture and test.) The recurrence $L_0 = 2$, $L_1 = 1$, $L_n = L_{n-1} + L_{n-2}$ defines the Lucas numbers. Conjecture, by computing small cases in code, a simple relationship between $L_n$ and the Fibonacci numbers $F_n$ (try $L_n$ versus $F_{n-1} + F_{n+1}$). Test it up to $n = 15$, then prove your conjecture by strong induction. How many base cases does the proof need?

7.25 † (Well-ordering / termination.) The Collatz step sends $n$ to $n/2$ if $n$ is even and to $3n + 1$ if $n$ is odd. Consider instead the simpler "halving" process: repeatedly replace $n$ by $\lfloor n/2 \rfloor$ until reaching $0$. Use the well-ordering principle to prove this process terminates for every starting $n \ge 0$. Identify the strictly decreasing quantity, and explain why "strictly decreasing sequence of naturals" plus well-ordering forces termination. (Contrast: explain in one sentence why the same argument does not settle ordinary Collatz.)

Part F — Interleaved & Deep Dive

Mixing techniques from earlier chapters keeps them sharp.

7.26 † (Ch. 6 + 7.) Take any one summation identity you proved by ordinary induction in Chapter 6 (e.g., $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$). Re-prove it using the smallest-counterexample (well-ordering) pattern instead. Which proof do you find cleaner, and why?

7.27 (Ch. 5 + 7.) The smallest-counterexample template is built on a Chapter 5 proof strategy. Name that strategy, state its opening move, and identify which step of the template (1–5 in §7.2) is the moment the contradiction is forced.

7.28 † (Ch. 4 + 7.) Recall the Chapter 4 definition "$a \mid b$ means $b = a m$ for some integer $m$." Use the recursively defined set $S$ with basis $3 \in S$ and recursive clause "if $x, y \in S$ then $x + y \in S$" (from §7.4). Prove by structural induction that every element of $S$ is divisible by 3, and point to the exact line where the Chapter 4 definition is unpacked.

7.29 (Ch. 2 + 7.) Write the principle of strong induction as a single logical formula using quantifiers over $n$ and $k$ and the predicate $P$. Contrast its inductive-step antecedent with the one you wrote for ordinary induction in Exercise 6.22.

7.30 † (Ch. 1 + 7.) A propositional formula is built recursively: basis — any propositional variable is a formula; recursive clause — if $\alpha$ and $\beta$ are formulas, then $(\neg \alpha)$, $(\alpha \land \beta)$, and $(\alpha \lor \beta)$ are formulas. Prove by structural induction that every such formula has an equal number of left and right parentheses. (Notice this is the same proof shape as §7.4's expression result.)

7.31 (Deep Dive.) Prove the full three-way equivalence sketched in §7.6 in your own words: write out all three implications (ordinary ⟹ strong, strong ⟹ well-ordering, well-ordering ⟹ ordinary) with every step justified, and explain in one paragraph why proving a cycle of implications establishes that all three principles are logically equivalent.

7.32 (Deep Dive.) Define a full binary tree's height recursively: $h(\text{leaf}) = 0$ and $h(\text{node}(T_1, T_2)) = 1 + \max(h(T_1), h(T_2))$. Prove by structural induction that a full binary tree of height $h$ has at most $2^{\,h+1} - 1$ nodes. (This bound underlies the analysis of balanced trees in Chapter 31.)

Solutions to † and odd-numbered exercises: see appendices/answers-to-selected.md. For each proof, remember the single most common strong-induction error: too few base cases. Before you write the step, ask "how far back does it reach?" — that number is how many base cases you owe.