Deciding whether an induction argument is valid
A student claims to prove that for all positive integers n, 1 + 3 + 5 + ... + (2n - 1) = n^2 + 1. Their argument: 'Base case n = 1: LHS = 1, RHS = 1 + 1 = 2. Hmm, that fails, but let's proceed. Assume true for n = k, i.e. 1 + 3 + ... + (2k - 1) = k^2 + 1. Then for n = k + 1, add 2k + 1 to both sides: LHS becomes (k+1)^2, and RHS becomes k^2 + 1 + 2k + 1 = (k+1)^2 + 1. So the pattern continues.' A second student says the algebra is correct so the proof is 'basically right apart from a typo'. A third student proposes fixing it by starting the induction at n = 2.
1. Assess the logical status of the student's argument. Is the inductive step correct as algebra? Does a correct inductive step plus a failed base case prove anything?
Read the worked answer
The inductive step as written is algebraically fine: if the statement held at n = k, then adding 2k + 1 to both sides gives (k+1)^2 on the left and (k+1)^2 + 1 on the right, so the statement would hold at n = k + 1. But the base case fails, and induction requires both parts. A valid inductive step with no true base case proves nothing about any n - it is a conditional chain with no starting link.
Concretely, the claimed identity is false: the sum of the first n odd numbers is n^2, not n^2 + 1. At n = 1 the identity fails; at n = 2 the sum is 4 while 2^2 + 1 = 5, also false. The inductive step merely shows that if the false statement were true somewhere, it would be true at the next integer - a vacuous implication.
2. Evaluate the third student's suggestion of starting the induction at n = 2. Does this rescue the proof?
Read the worked answer
No. Starting at n = 2 requires the base case n = 2 to be true, and it is false: 1 + 3 = 4 but 2^2 + 1 = 5. So the induction cannot start.
More generally, shifting the base case only helps if the statement is actually true from that point onward. Here the statement is false for every positive integer n (the sum is always n^2, one less than n^2 + 1), so no starting point rescues it. The third student has confused 'choosing a convenient base case' with 'choosing a base case that is true'.
3. Write a correct induction proof that 1 + 3 + ... + (2n - 1) = n^2 for all positive integers n, and explain in one or two sentences why the correct statement differs from the student's.
Read the worked answer
Claim: for all n ≥ 1, the sum of the first n odd numbers equals n^2.
Base case n = 1: LHS = 1, RHS = 1^2 = 1. True.
Inductive step: assume 1 + 3 + ... + (2k - 1) = k^2 for some k ≥ 1. Then
1 + 3 + ... + (2k - 1) + (2(k+1) - 1) = k^2 + (2k + 1) = (k+1)^2.
So the statement holds at n = k + 1. By induction it holds for all n ≥ 1.
The student's error was in the statement, not the technique: they added 1 to the right side. The inductive step is robust to this kind of slip because it propagates whatever the base case asserts - which is exactly why the base case must be checked honestly.