xercise 8. Find the mistake in the following argument. (Hint: In the inductive s
ID: 3167717 • Letter: X
Question
xercise 8. Find the mistake in the following argument. (Hint: In the inductive step, an implicit assump- tion is made which is valid for most values of n but not for all. What is this implicit assumption and for which values of n is it valid?) We claim that all horses have the same color. It suffices to show that for each neN, for each set of n horses, all of the horses in the set have the same color. We shall prove this by induction on n. Let P(n) be the sentence 2 For each set of n horses, all of the horses in the set have the same color. BASE CASE: Clearly P(1) is true, because all of the horses in a set containing only one horse have the same color. INDUCTIVE STEP: Let n N such that P(n) is true. Consider any set of n+1 horses. Removing one of the horses from the set, we obtain a set of n horses, all of which have the same color by the inductive hypothesis. Removing a different horse from the set of n +1 horses, we obtain another set of n horses and all of these horses have the same color by the inductive hypothesis. Thus all of the horses in the set of n +1 horses have the same color. Hence P(n +1) is true too. CONCLUSION: Therefore by induction, for each n e N, P(n) is true. The manipulation of summation notation can be confusing. Often such confusion can be resolved by writing the sums in-... notation, such as writing ,a in the form a " +0m+i +--+a, Thenext exercise gives some practice in this.Explanation / Answer
The inductive step is not acutually correct. The argument there successfully shows that P(n+1) is true when P(n) is true for n>1.
If we choose n=1, then P(1) is always true (By Base case)
But P(2) is not true at all.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.