It's not proven in a vacuum: it's proven under the assumption that it's true for N-1. E.g. if we assume that all groups of 2 horses are the same color, we can

It's not proven in a vacuum: it's proven under the assumption that it's true for N-1. E.g. if we assume that all groups of 2 horses are the same color, we can prove that all groups of 3 horses are by labelling them A, B, C. A and B are the same color because they are a group of 2; B and C are the same color because they are also a group of 2; A and C are the same color transitively (or because they are also a group of 2). Therefore A, B, and C are the same color. This step is logically sound, and you can do this for any N greater than three. The problem is that this fails when tried for N=2, because then each sub-group can have only one horse in it. We already know that each horse is the same color as itself, so we don't actually reveal any new information by doing this. Since it doesn't work for N=2, the base assumption used for the N=3 case is incorrect.