Parity proof with a converse slip
In a revision session on proof, a candidate is asked to prove: for every integer n, if n^2 is even then n is even. The candidate writes: 'Assume n is even. Then n=2k for some integer k, so n^2=4k^2=2(2k^2), which is even. Hence n^2 even implies n even.' The tutor suspects the argument proves only that an even n gives an even square. A second candidate offers a proof by contradiction: 'Assume n^2 is even and n is odd. Write n=2k+1, so n^2=4k^2+4k+1=2(2k^2+2k)+1, which is odd, contradicting n^2 even.' The class then argues about whether the statement is true for negative n and whether 'even' applies to negative integers. The marker must decide how many marks each response deserves and what logical principle is being tested.
1. Identify the logical error in the first candidate's argument and state precisely what that argument does prove. Then explain why the second argument is valid, including the role of the contradiction.
Read the worked answer
The first argument assumes n is even, which is the converse of the required hypothesis. It proves: for all integers n, if n is even then n^2 is even. That does not establish: if n^2 is even then n is even, because the case n odd has not been considered under the hypothesis n^2 even. The second argument is valid. It assumes the hypothesis n^2 even and the negation of the conclusion, n odd. Every odd integer has the form 2k+1 with k an integer, including negative odd integers. Squaring gives n^2=4k^2+4k+1=2(2k^2+2k)+1, which is odd, contradicting the hypothesis that n^2 is even. The contradiction shows the assumption n odd is impossible, so n must be even. The argument is a direct application of proof by contradiction and does not rely on checking finitely many values.
2. A third candidate claims: 'Since the statement works for n=1,2,3,4, it is true for all integers.' Explain why this is not a proof. Then decide whether the modified statement 'if n^2 is divisible by 4 then n is divisible by 4' is true, giving a counterexample if it is false.
Read the worked answer
Checking n=1,2,3,4 only proves the statement for those four integers; it cannot prove a universal statement over all integers. A single unexamined integer could satisfy the hypothesis and fail the conclusion. For the modified claim 'if n^2 is divisible by 4 then n is divisible by 4', n=2 is a counterexample: n^2=4 is divisible by 4, but 2 is not divisible by 4. Therefore the modified statement is false. A valid proof must cover an arbitrary integer n, usually by algebra or by contradiction, not by a finite sample.