A student wants to prove P(n) for all n ≥ 1. They show P(1) is true, then write an inductive step that appears to derive P(k+1) — but on close inspection, one algebraic step secretly assumes P(k+1) is true in order to simplify an expression. What is wrong with this proof?
ANothing — the algebra is internally consistent and the proof is valid
BThe base case should be verified for n=0 as well, not just n=1
CThe proof is circular: it uses P(k+1) to establish P(k+1), which proves nothing
DThe inductive hypothesis was not written out explicitly enough
The inductive step must derive P(k+1) using only P(k) (the inductive hypothesis) and valid logic or algebra. If P(k+1) is assumed anywhere during the derivation, the argument is circular — you've proven 'if P(k+1) then P(k+1),' which is a tautology. This error is common because students recognize what they want to arrive at and unconsciously use it to simplify. The fix is to start only from P(k) and valid algebraic moves, never touching P(k+1) until you've derived it.
Question 2 Multiple Choice
A student verifies that the formula 1 + 2 + ⋯ + n = n(n+1)/2 holds for n = 1, 2, 3, …, 20. What has the student accomplished?
AA proof valid for all positive integers, since 20 cases establishes the pattern
BA proof by strong induction covering the first 20 cases
CA verification of finitely many cases — not a proof that the formula holds for all n
DA sufficient base case collection for a standard inductive proof
Verification of finitely many cases — even many cases — is not a proof for all natural numbers. Induction is powerful precisely because the inductive step is a universal claim: if P(k) then P(k+1) for *every* k. Combined with the base case, this chain reaches every natural number. Checking examples only establishes finitely many instances; no finite number of checks can rule out a counterexample at n = 1,000,000 or beyond.
Question 3 True / False
In the inductive step of a weak induction proof, you may assume P(k) is true for an arbitrary fixed k — this assumption is what allows you to derive P(k+1).
TTrue
FFalse
Answer: True
Correct. The inductive hypothesis is the assumption that P(k) holds for some fixed (but arbitrary) k. 'Arbitrary' is crucial: we're not assuming it for a specific number, but for a generic k that could be any value in the domain. The derivation that follows must use this assumption to logically arrive at P(k+1). If the derivation does not actually use P(k), something is likely wrong — either the proof is trivial or the argument is circular.
Question 4 True / False
A proof by weak induction is complete once you have verified the base case, because the inductive step just repeats the same calculation for the next value.
TTrue
FFalse
Answer: False
The base case alone proves only P(1) — one specific instance. The inductive step is not a repeated calculation; it is a conditional proof that *for any* k, P(k) implies P(k+1). Only when both parts are in place does the chain reaction start: P(1) is true, so P(2) is true (by the inductive step with k=1); P(2) is true, so P(3) is true (with k=2); and so on through all natural numbers. Without the inductive step, you've proven nothing beyond the base case.
Question 5 Short Answer
What makes mathematical induction a valid proof technique rather than just an extended pattern check? Why does proving P(1) and 'P(k) implies P(k+1)' actually establish P(n) for all n?
Think about your answer, then reveal below.
Model answer: Induction is valid because the inductive step is a universal conditional — it holds for every k without exception. Once we know P(1) (domino 1 falls) and that any true P(k) forces P(k+1) to be true (any fallen domino knocks down the next), the entire infinite sequence is determined: P(1) is true, so P(2) must be true; P(2) is true, so P(3) must be true; and this chain extends indefinitely. There is no gap and no stopping point. By contrast, checking examples only covers finitely many cases and leaves infinitely many unchecked.
The key is that 'P(k) implies P(k+1)' is a statement about *all* k, not just specific ones. Combined with P(1), it creates an unbroken chain of logical consequences stretching across all natural numbers. This is fundamentally different from pattern recognition: patterns can fail at large n, but a valid inductive step cannot, because it applies universally.