Self-Assessment Quiz: Mathematical Induction

Eighteen questions to check your understanding. Answer before opening the key. Aim for 15+.

Question 1

In a proof by induction, the inductive hypothesis is:

A) the statement you ultimately want to prove, $P(n)$ for all $n$ B) the assumption that $P(k)$ holds for an arbitrary fixed $k$ C) the proof that $P(1)$ holds D) the claim that $P(k+1)$ is false

Question 2

"Assuming $P(k)$ to prove $P(k+1)$ is circular reasoning." This statement is:

A) true — induction is logically unsound B) true, but we accept it for convenience C) false — you prove an implication, not the conclusion itself D) false — you never actually use $P(k)$

Question 3

To prove $2^n > n^2$ for all $n \ge 5$, the correct base case is:

A) $n = 0$ B) $n = 1$ C) $n = 2$ D) $n = 5$

Question 4

Which is the closest programming analogue of the base case in an induction proof?

A) the recursive call B) the loop counter C) the non-recursive (terminating) branch of a recursive function D) the function's return type

Question 5

The "all horses are the same color" fallacy fails because:

A) the base case ($n=1$) is false B) the inductive step fails specifically at $k = 1$ (no overlap between the two groups) C) horses can genuinely be different colors, so no proof is possible in principle D) it uses strong induction incorrectly

Question 6

In a loop-invariant proof, "maintenance" corresponds to which part of induction?

A) base case B) inductive step C) conclusion D) the statement $P(n)$

Question 7

A valid inductive step with no base case checked proves:

A) the statement for all $n$ B) the statement for all $n \ge 2$ C) nothing about whether the statement is true D) that the statement is false

Question 8

The "peel off the last term" move is the standard engine for induction proofs about:

A) inequalities B) summations C) divisibility D) graph connectivity

Question 9 (True/False, justify)

True or false: If $P(1), P(2), \dots, P(1000)$ are all true, then $P(n)$ is true for all $n$. Justify in one sentence.

Question 10

Which claim would require strong induction (assuming more than just $P(k)$) rather than ordinary induction?

A) $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$ B) every integer $n \ge 2$ has a prime factorization C) $3 \mid (4^n - 1)$ D) a set of size $n$ has $2^n$ subsets

Question 11

In the divisibility proof that $3 \mid (4^n-1)$, we wrote $4^k - 1 = 3m$. The justification for writing this is:

A) an axiom of arithmetic B) the definition of "divides" applied to the inductive hypothesis C) the base case D) the well-ordering principle

Question 12

For the recursive triangle(n) correctness proof, the inductive hypothesis is the assumption that:

A) triangle(n) is defined B) triangle(k) returns $\frac{k(k+1)}{2}$ C) triangle(k+1) returns $\frac{(k+1)(k+2)}{2}$ D) the loop terminates

Question 13 (True/False, justify)

True or false: The base case of an induction must always be $n = 0$ or $n = 1$.

Question 14

A loop invariant must be checked at:

A) the end of the program only B) a fixed program point, every time control reaches it C) randomly chosen iterations D) only the first and last iterations

Question 15

"Computation tests a conjecture; proof settles it." The Toolkit's check_identity returning None means:

A) the identity is proven for all $n$ B) no counterexample was found up to the tested bound C) the identity is false D) the code crashed

Question 16 (Short answer)

State the three things you must verify to conclude a loop is correct using an invariant.

Question 17

Which is a legitimate base case for proving a statement about all integers $n \ge -3$?

A) $n = 0$ B) $n = 1$ C) $n = -3$ D) any of these, as long as the step covers the rest

Question 18 (Short answer)

In one sentence, explain why recursion and induction are described as "the same idea pointed in opposite directions."

Answer Key

Topics to review by question