Horse of a different color
Analyze the following “proof” that all horses are the same color:
We argue by mathematical induction. Clearly, all horses in any set of 1 horses are all the same color. Now assume that the result is true for any collection of n horses, and consider a collection of n+1 horses. In the collection of n+1 horses, we know that horses 1, 2, …, n are all the same color (by the induction hypothesis), as are horses 2, 3, …, n+1 (since this is another collection of n horses). These two subcollections have horses 2, 3, …, n in common. Thus, all horses in the collection 1, 2, …, n, n+1 are the same color. Therefore, by the principle of mathematical induction, all horses are the same color.
Out of the 29 students, only two correctly (or very nearly correctly) pointed out the flaw in this logic. Can you? It’s easy to say that not all horses are the same color. It’s more difficult to say exactly how the principle of mathematical induction was misapplied.
Tags: proof
You can comment below, or link to this permanent URL from your own site.
February 1, 2011 at 1:09 am
I don’t think the inductive reasoning step works for n=1 to get you to n=2. If n=1, there are no common elements in the (i) the subcollection 1,…n (i.e 1) and (ii) the subcollection 2…n+1 (i.e. 2), so the proof breaks down. In other words true for n=1 does not imply true for n=2 (which of course is only common sense). Still it’s a pretty clever “proof”.