Q6: What is wrong with the following proof? (3pt) Show that all horses are the s

Question

Q6: What is wrong with the following proof? (3pt) Show that all horses are the same color. Let P(n) = a set of n horses being the same color Basis step: P(1) is true because one horse is the same color Assume P(k) is true, i.e., all the horses in any set of k horses are the same color Show that P(k + 1) is true: Let h1,h2, ...,hk, hk + 1 be k + 1 horses in a set By inductive hypothesis (h1, h2, ..., hk has the same color and (h2, h3. ... ,hk + 1) have the same color. Therefore (h1, h2, h3, ..., hk+1} has the same color.

Explanation / Answer

Inductive hypothesis is true only when two subsets of horses has a common element.

but for k=2 means two horses,

first horse and the second horse have no horses in common, and therefore may not all have the same color.

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

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