Here is another incorrect proof that purports to use mathematical induction to p

Question

Here is another incorrect proof that purports to use mathematical induction to prove that all flowers have the same color! What is wrong? Consider the following predicate: If S is a set of flowers containing exactly n elements, then all the flowers in S have the same color. The predicate is clearly true if n = 1. We suppose it true for n = k and prove the result for n = k +1. Thus, let S be a set of k +1 flowers. If we remove one flower from S we get a set of k flowers. Therefore, by the induction hypothesis they all have the same color. Now return the flower removed from S and remove another. Again by our induction hypothesis the remaining flowers all have the same color. But now both of the flowers removed have been shown to have the same color as the rest. Thus, all the flowers in S have the same color.

Explanation / Answer

The problem lies in the statement "But now both of the flowers removed have been shown to have the same color as the rest" - this is only valid if the "rest" set is not empty. For k = 1, this set is empty and the argument falls apart. Hence, your inductive step proof is only valid when k >= 2 in the inductive hypothesis (i.e. "suppose it true for n = k"), in which case proving a base case of n = 1 is not sufficient.

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.