Description: Assume that horses always are the same color. Let us consider a group consisting of horses. First, exclude the last horse and look only at the first horses; all these are the same color since horses always are the same color. Likewise, exclude the first horse and look only at the last horses. These too, must also be of the same color. Therefore, the first horse in the group is of the same color as the horses in the middle, who in turn are of the same color as the last horse. Hence the first horse, middle horses, and last horse are all of the same color, and we have proven that: If horses have the same color, then horses will also have the same color. We already saw in the base case that the rule ("all horses have the same color") was valid for . The inductive step showed that since the rule is valid for , it must also be valid for , which in turn implies that the rule is valid for and so on. Thus in any group of horses, all horses must be the same color.