Solution

What is wrong with the following proof that all horses in any group of $n$ horses are the same color?

Basis Step.

Certainly, all horses from a group of $n=1$ horses are the same color -- there's only one horse after all.

Inductive Step.

Assume that all horses in a group of $k$ horses are the same color for some positive integer $k$. Now consider a group of $k+1$ horses. Suppose we name these horses: $h_1,h_2,h_3,\ldots,h_k, h_{k+1}$. Notice that horses $h_1,h_2,\ldots,h_k$ is a group of $k$ horses, and hence, must all be of the same color. Also, horses $h_2,h_3,\ldots,h_{k+1}$ is also a group of $k$ horses, and hence, must all be of the same color. Since these two groups of horses have common members (i.e., horses $h_2,h_3,\ldots,h_k$), all $k+1$ horses must be of the same color. Then by the principle of mathematical induction, for any positive integer $n$, all horses in any group of $n$ horses are the same color.


The inductive argument does not hold in the case where $k=1$. In this case, when we consider $k+1 = 2$ horses, and split them into two groups -- the groups consist of only a single horse each, with no common members between them.