Find the mistake in the following proof that all dogs are the same color (if there's any):

Let's use induction. Consider groups of 1 dog. All dogs of every group are the same color, of course. So we now that it's true for 1. Suppose it's true for groups of k dogs, i.e. every group of k dogs are the same color. Then let's consider any group A of k+1 dogs. Consider a subgroup of A containing k dogs. Let's call x the dog in A but not in the subgroup. Then by induction, all dogs in the subgroup are the same color. Now consider a subroup of A of k dogs, with x in the subgroup. All dogs except for x are the same color. Then, since every group of k dogs are the same color (by induction), all dogs in A are the same color. So x and every dog are the same color.

(In reply to solution by Charlie)

The Fallacy of Composition as defined on http://www.nizkor.org/features/fallacies/composition.html
is a fallacy of formal logic, not of proof by induction, but the principle is basically the same.

In an inductive proof, it is important that your zero-state not be merely trivially true, but true in the same way as the inductive step assumes for its manipulations. That is why whenever I use induction to prove something, I "show" not only the first example to be true, but also the second and third, so that a non-trivial zero-state has been shown to be true.

Posted by TomM on 2003-05-30 10:56:09