Edit: You seem to have deleted the part I was responding to. Here's a new response: > Nope, when you removed h1, and when you removed h2, by assumption you got

Edit: You seem to have deleted the part I was responding to. Here's a new response: > Nope, when you removed h1, and when you removed h2, by assumption you got two sets of uniform color, but you never proved they had the same uniform color as one another. This part of the proof happens sneakily here: >> But when we removed h_1, we got that all the remaining horses had the same color as h_2. The sneaky part is 'all the remaining horses' which does allow you to prove they're all the same color if the number of "remaining horses" is > 0. This is where the inductive step sneaks in the n>=2 assumption. Original: > The base case is the former but the inductive step appears to be assuming the latter The inductive step doesn't make that assumption. What it does do is assume that n>=2. The step basically says: from a set s1 of n+1 horses, remove horse h1 (this assumes n>=0). This gives you a set s2 of n horses, and we already know that all sets of n horses have horses of one color. Now take the original set of n+1 horses and remove a different horse (h1<>h2 assumes n>=1), leaving a set s2 of n horses, which we again already know are all same color. Now assume that there is yet another horse h3 (h1<>h2<>h3 assumes n>=2) that is in the original set s1. Since h3 is in s2 with h1 and in s3 with h2, h3 is the same color as h1 and h2. Since h3 is any arbitrary member of s1 besides h1 and h2 we know that all members of s1 are the same color. Thus the inductive rule is indeed valid for every n≥2. If you can ever prove that every pair from a horse population has the same color you have also shown that every size of sets of horses from that population will also all have the same color.