Q6: What is wrong with the following \"proof\"? (3pt) Show that \"all horses are
ID: 669073 • Letter: Q
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 hi, h2,., ,hk+1 be k+1 horses in a set Let h1, h2, ..., hk By inductive hypothesis (h,h2, hhas the same color and (h2,h3,hhave the same color. Therefore (h1,h2,h,. h+1) has the same colorExplanation / Answer
General steps in inductive hypothesis are:
1. Prove that given statement is true for very first element of the given set. (Base step)
2. Assume that given statement is true for 'n'th element of the given set. And Hence show that the given statement is also true for very next element after 'n'th element in the given set. (Inductive step)
In given case, the base step holds true. Also the assumption for P(k) is true, thus horses h1 to hk have same color.
But, that doesn't hold true for the horse Hk+1 Hence the statement "horses {h2, ....., hk+1 have same color }" is not true.
This is the wrong step taken in the proof.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.