In a proof by induction that a statement P(n) holds for all natural numbers, the inductive step proves:
AP(n) is true for every specific value of n
BIf P(k) is true, then P(k+1) is true
CP(1) and P(2) are true, so P(n) is true for all n
DP(k+1) is directly true for all k
The inductive step proves the conditional: IF P(k) holds, THEN P(k+1) holds. It does not prove P(k+1) outright — it only establishes the implication. The base case then provides the starting truth (P(1) is true), and repeated application of the conditional propagates truth to every natural number.
Question 2 True / False
A proof that checks P(1), P(2), P(3), ..., P(100) for a statement about natural numbers constitutes a valid proof that P(n) holds for most n.
TTrue
FFalse
Answer: False
Checking finitely many cases — no matter how many — never proves a universal statement. There are infinitely many natural numbers, so any finite check leaves infinitely many cases unverified. Induction is powerful precisely because the inductive step is a general conditional that covers all k simultaneously, not a case-by-case check.
Question 3 Short Answer
Why is the base case necessary in a proof by induction? What goes wrong if you skip it?
Think about your answer, then reveal below.
Model answer: Without the base case, the inductive step gives you only a chain of conditionals with no starting truth. The argument would show P(1) → P(2) → P(3) → ... but never establish that P(1) is actually true, so the chain never 'fires.' A proof without a base case can appear to prove false statements.
A classic example of a broken induction is 'all horses are the same color' — the inductive step has a hidden flaw, but it illustrates that the structure of induction requires both parts. The base case is the seed; the inductive step is the propagation rule. Without the seed, no propagation occurs.