1. The following “proof by induction” attemps to prove that all horses in univer
ID: 3796132 • Letter: 1
Question
1. The following “proof by induction” attemps to prove that all horses in universe have the same color. That is, for every n 1, any set of n horses in universe have the same color. Obviously, there is something wrong with this proof. State clearly which step is wrong and why.
(a) For n = 1, the set contains a single horse, which has the same color by itself, so the base is obviously correct
(b) For the hypothesis, suppose the claim is correct for some n 1.
(c) Then, we will prove the claim is also correct for n+1. Consider any set of n+1 horses. Let us number them as 1,2,···,n +1.
i. By the hypothesis, horses {1,2,···,n} have the same color.
ii. By the hypothesis, horses {2,3,···,n+1} have the same color.
iii. These two sets have in common horses {2,3,···,n}.
iv. Therefore, by transitivity, these n +1 horses all have the same color
Explanation / Answer
2nd step is wrong.
In 2nd step, by the hypothesis, number of horses should be n+1 but only n horses are taken into the equation (2,3,....n+1)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.