Indicate what is wrong with each of the following induction “proofs.”
(a) Theorem: For each n ∈ ℕ, let P(n) be the statement “Any collection of n marbles consists of marbles of the same color.” Then P(n) is true for all n ∈ ℕ.
Proof: Clearly, P(1) is a true statement. Now suppose that P(k) is a true statement for some k ∈ ℕ. Let S be a collection of k + 1 marbles. If one marble, call it x, is removed, then the induction hypothesis applied to the remaining k marbles implies that these k marbles all have the same color. Call this color C. Now if x is returned to the set S and a different marble is removed, then again the remaining k marbles must all be of the same color C. But one of these marbles is x, so in fact all k + 1 marbles have the same color C. Thus P(k+ 1) is true, and by induction we conclude that P(n) is true for all n ∈ ℕ. ♦
(b) Theorem: For each n ∈ ℕ, let P(n) be the statement “n2 + 7n + 3 is an even integer.” Then P(n) is true for all n ∈ ℕ.
Proof: Suppose that P(k) is true for some k ∈ ℕ. That is, k2 + 7k + 3 is an even integer. But then
(k + l)2+7(k + l) + 3 = (k2 +2k +1) + 7k + 7 + 3
= (k2 +7k + 3) + 2(k + 4),
and this number is even, since it is the sum of two even numbers. Thus P(k+ 1) is true. We conclude by induction that P(n) is true for all n ∈ ℕ. ♦
We need at least 10 more requests to produce the solution.
0 / 10 have requested this problem solution
The more requests, the faster the answer.