Self-Assessment Quiz: Strong Induction, Well-Ordering, and Recursive Definitions

Twenty questions to check your understanding. Answer before opening the key. Aim for 16+.

Question 1

The difference between ordinary and strong induction lies entirely in the:

A) base case — strong induction needs no base case B) inductive hypothesis — strong induction may assume all prior cases, not just $P(k)$ C) conclusion — strong induction proves a stronger statement D) starting value $n_0$

Question 2

A recurrence's strong inductive step uses $a_{n-1}$, $a_{n-2}$, and $a_{n-3}$. The correct number of base cases is:

A) one B) two C) three D) four

Question 3 (True/False, justify)

True or false: Strong induction can prove theorems that ordinary induction cannot. Justify in one sentence.

Question 4

The single most common way a strong-induction proof silently breaks is:

A) using the wrong variable name B) checking too few base cases for the reach of the step C) forgetting to write $\blacksquare$ D) assuming only $P(k)$ instead of all prior cases

Question 5

The well-ordering principle states that every:

A) subset of $\mathbb{Z}$ has a least element B) non-empty subset of $\mathbb{N}$ has a least element C) non-empty subset of $\mathbb{N}$ has a greatest element D) finite subset of $\mathbb{Q}$ has a least element

Question 6

The well-ordering principle is false for which set?

A) $\mathbb{N}$ B) $\{0, 2, 4, 6, \dots\}$ C) the integers $\mathbb{Z}$ D) $\{5, 10, 15, \dots\}$

Question 7

In the "smallest-counterexample" proof pattern, after assuming the set $C$ of counterexamples is non-empty, the very next move is to:

A) check the base case B) take the least element $m$ of $C$ (by well-ordering) C) assume $P(m)$ is true D) conclude $C$ is empty

Question 8

The smallest-counterexample pattern is fundamentally an instance of which proof strategy?

A) direct proof B) proof by contradiction C) proof by cases D) constructive existence proof

Question 9

A recursive definition of a set consists of a basis clause, a recursive clause, and an implicit:

A) termination clause B) exclusion clause ("nothing else is in the set") C) induction clause D) closure under multiplication

Question 10 (True/False, justify)

True or false: Dropping the word "smallest" from "let $E$ be the smallest set such that…" leaves the definition unchanged. Justify in one sentence.

Question 11

In structural induction, the inductive hypothesis lets you assume the property holds for:

A) the integer $n - 1$ B) the sub-objects that a recursive clause combines to form the current element C) all integers less than $n$ D) the basis elements only

Question 12

Structural induction is logically valid because of which clause of the recursive definition?

A) the basis clause B) the recursive clause C) the exclusion clause (every element is built in finitely many steps) D) none — it is a separate axiom

Question 13

For the expression set $E$ (basis: x, numerals; recursive: (a + b), (a * b)), a structural induction proof has exactly:

A) one case (the basis) B) one case per clause of the definition (a basis case and a recursive case) C) infinitely many cases, one per expression D) two base cases and no recursive case

Question 14

A full binary tree is one in which every node has:

A) exactly one child B) at most two children C) either zero children or exactly two children D) exactly two children, always

Question 15

The identity $\ell(T) = i(T) + 1$ for full binary trees says the number of leaves is:

A) equal to the number of internal nodes B) one more than the number of internal nodes C) twice the number of internal nodes D) one less than the number of internal nodes

Question 16

Why can't you prove $\ell(T) = i(T) + 1$ by "adding one node" to a full binary tree of $n$ nodes?

A) full binary trees have no leaves B) adding a single child to a leaf violates the "full" property (that node would have one child) C) the identity is false for small trees D) node count is never a natural number

Question 17 (True/False, justify)

True or false: The three induction principles (ordinary, strong, well-ordering) are logically equivalent. Justify in one sentence.

Question 18

The proof "ordinary induction ⟹ strong induction" works by:

A) checking infinitely many base cases B) applying ordinary induction to a bundled statement $Q(n) = P(0) \land \dots \land P(n)$ C) using well-ordering as an intermediate D) assuming strong induction and deriving ordinary induction

Question 19

Which claim most clearly calls for strong induction rather than ordinary induction?

A) $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$ B) the correctness of an power_fast that recurses on e // 2 C) $6 \mid (n^3 - n)$ D) a set of size $n$ has $2^n$ subsets

Question 20 (Short answer)

In one sentence each, state the rule of thumb for (a) how many base cases a strong induction needs and (b) which form of induction to reach for when "grab the smallest bad case" is the natural move.

Answer Key

Topics to review by question