The following is a (wrong) proof by Induction that each nonnegative Integer equa
ID: 3006779 • Letter: T
Question
The following is a (wrong) proof by Induction that each nonnegative Integer equals twice itself, i.e. n = 2n for all integers n Greaterthanequalto 0. Base case n = 0 : P(n) holds for n = 0. Inductive step: let us assume that n = 2n holds for some nonnegative Integer n. We multiply both sides of this equation by the quantity This yields n + 1 = 2(n + 1), which is P(n + 1). This completes the proof by induction. Explain what is wrong with this proof. As usual, we will use the notation P(n) = (n = 2n). The base case is not n = 0 , it's n = 1 , for which the equation n = 2n is false. The base case is n = 0 but was incorrectly verified. P(0) is false. The conditional P(ri) P(n + 1) is false for all n, and the algebra in the inductive step that verifies this conditional is mistaken in all cases. The conditional P(n + 1) is false (only) for n=0, and the algebra in the inductive step that verifies this conditional is mistaken (only) in that case. The conditional P(n + 1) is false (only) for n=1, and the algebra in the inductive step that verifies this conditional is mistaken (only) in that case. The conditional P(n + 1) is false (only) for n=2, and the algebra in the inductive step that verifies this conditional is mistaken (only) in that case. There is nothing wrong with either the base case or the inductive step. The principle of induction just breaks down in this situation.Explanation / Answer
In inductive step we multiply by: (n+1)/n but n is assumed to be some non negative integer so n can be 0 so: (n+1)/n is not defined in that case.
Hence,
3. P(n)-->P(n+1) is false (only) for n=0
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.