In a proof by induction of a statement P(n) for all n ≥ 1, the inductive step proves:
AP(1) is true
BP(n) is true for all n
CIf P(k) is true, then P(k+1) is true
DP(k) is true for some specific k
The inductive step proves the conditional: IF the statement holds for an arbitrary k, THEN it holds for k+1. This is not the same as proving P(n) for all n directly (option B does that only in combination with the base case). Option A is the base case. Option D is the inductive hypothesis, which is assumed, not proven, within the inductive step.
Question 2 True / False
A proof by induction can succeed without a base case.
TTrue
FFalse
Answer: False
Without a base case, there is no starting point for the chain. Consider the false statement 'all natural numbers are greater than 1000.' The inductive step would say 'if k > 1000, then k+1 > 1000,' which is true — but P(1) is false. Without a verified base case, the dominos never start falling. The base case is what connects the inductive chain to a concrete truth.
Question 3 Short Answer
Use induction to prove that 1 + 3 + 5 + ... + (2n-1) = n² for all n ≥ 1.
Think about your answer, then reveal below.
Model answer: Base case: n = 1. The left side is 1, the right side is 1² = 1. True. Inductive step: Assume 1 + 3 + ... + (2k-1) = k². Add (2(k+1)-1) = (2k+1) to both sides: k² + (2k+1) = (k+1)². The left side equals (k+1)², confirming the formula for k+1. By induction, the formula holds for all n ≥ 1.
The inductive step takes the assumed formula for k and extends it to k+1 by adding the next odd number (2k+1). The algebra k² + 2k + 1 = (k+1)² is the key calculation. Combined with the base case, induction covers every natural number.