The Proof That Assumed Its Conclusion
A student is asked to prove that for all positive integers n, n^3 - n is divisible by 6. She writes: 'Assume n^3 - n = 6k for some integer k. Then n^3 - n is divisible by 6, which is what we wanted. QED.' A marker flags circular reasoning. The student then tries induction: base case n = 1 gives 0, divisible by 6; inductive step assumes n^3 - n = 6k and tries to show (n+1)^3 - (n+1) = 6m. She expands and gets stuck because she cannot see why the leftover terms are multiples of 6. A tutor suggests factoring n^3 - n and using a parity argument instead.
1. Explain precisely why the student's first 'proof' is invalid, and identify the logical error by name.
Read the worked answer
The error. The student assumes the statement P(n): n^3 - n = 6k and then concludes P(n). This is circular reasoning (begging the question): the conclusion is contained in the premise. A valid proof must start from facts already established (definitions, axioms, previously proved results) and derive P(n) as a consequence; it cannot take P(n) as a hypothesis.
A subtler point: the student may have confused the structure of a direct proof with that of a conditional proof. 'If n^3 - n = 6k then n^3 - n is divisible by 6' is a true but trivial implication; it does not establish that such a k exists for every n. The missing ingredient is existence of k, which requires an argument from the form of n^3 - n, not an assumption.
2. Give a correct proof by factoring, using divisibility by 2 and by 3 separately, and explain why establishing both suffices.
Read the worked answer
Factor. n^3 - n = n(n^2 - 1) = n(n-1)(n+1) = (n-1)n(n+1), the product of three consecutive integers.
Divisibility by 2. Among any two consecutive integers one is even, so (n-1)n is even; hence the product is even.
Divisibility by 3. Among any three consecutive integers exactly one is divisible by 3, so the product is divisible by 3.
Why both suffice. 2 and 3 are coprime, so a number divisible by both is divisible by their product 6. Formally, if 2 | N and 3 | N then N = 2a = 3b; since gcd(2,3) = 1 and 3 | 2a, Euclid's lemma gives 3 | a, so a = 3c and N = 6c. Hence 6 | N.
Therefore 6 divides (n-1)n(n+1) = n^3 - n for every positive integer n. The proof is direct and non-circular.
3. Complete the induction the student started: show the inductive step from n^3 - n = 6k to (n+1)^3 - (n+1) being a multiple of 6, and comment on whether induction or the factoring proof is preferable here.
Read the worked answer
Inductive step. Expand:
(n+1)^3 - (n+1) = n^3 + 3n^2 + 3n + 1 - n - 1 = (n^3 - n) + 3n^2 + 3n = (n^3 - n) + 3n(n+1).
By hypothesis n^3 - n = 6k. Also n(n+1) is a product of consecutive integers, hence even, say n(n+1) = 2j. Then 3n(n+1) = 6j. Therefore
(n+1)^3 - (n+1) = 6k + 6j = 6(k + j),
a multiple of 6. Base case n = 1: 1 - 1 = 0 = 6*0, valid.
Comparison. Both proofs are correct. The factoring proof is shorter and gives insight (three consecutive integers). Induction requires the extra parity observation about n(n+1) inside the step, which is essentially the same fact in disguise. For this statement the direct factoring argument is preferable; induction is the better tool when the recurrence structure is unavoidable.