For every nonnegative integer n, 3|n. the next paragraph claims to prove this st
ID: 3108708 • Letter: F
Question
For every nonnegative integer n, 3|n. the next paragraph claims to prove this statement. Is this proof correct? Explain why or why not, making specific reference to each step of the proof if it is correct or to specific errors if it is not. If you find errors in the proof, explain how you would correct them or whether that would be impossible (and why). "Proof': We proceed by strong mathematical induction. Basis step: Indeed, 3|0 because there is an integer, namely 0 such that 0 = 3 middot 0. Induction step: Let k be arbitrary. Assume, as the strong induction hypothesis, that for all nonnegative integers j with 0 lessthanorequalto j lessthanorequalto k, that 3|j. Write k + 1 = m + n, where m, n are integers less than k + 1. By the induction hypothesis, 3|m and 3|n. That is, there are integers a, b such that m = 3a and n = 3b. Therefore, k + 1 = (3a) + (36) = 3(a + b). Since the set of integers is closed under multiplication, a + b epsilon Z and 3|(k + 1), as required.Explanation / Answer
Your proof is not correct; of course, it cannot be!
The problem is where you are writing k+1 = m+n where m and n are non-negative integers < k+1. Note that this step is true only when k+1 is greater or equal to 2. Therefore, the proof is not correct as it doesn't work for k=0, and hence one cannot apply the strong mathematical induction.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.