Answer: That the base case n=5 holds: 25 < 32.
- A That the base case n=5 holds: 25 < 32
- B That n=1 holds: 1 < 2
- C Nothing, induction applies automatically
- D That n=4 holds: 16 < 16
Correct answer: A. That the base case n=5 holds: 25 < 32
Explanation: The inequality n<sup>2</sup> < 2<sup>n</sup> fails for n=1,2,3,4 (at n=4: 16 < 16 is false since they are equal), but holds from n=5 onward (25 < 32). The base case must therefore be verified at n=5.
Mathematical induction works like a row of dominoes: proving the base case P(1) tips the first domino, and proving the inductive step (P(k) ⟹ P(k+1)) guarantees each domino knocks over the next - together these two facts guarantee ALL dominoes fall, without checking each one individually.
Concept context
A proof technique used to establish that a statement is true for every natural number, using a base case and an inductive step.