Step 2. Assume that any collection of k horses is the same colour. We will show that it follows from this assumption that any collection of k + 1 horses is also the same colour.
Proof: Take any group of k horses. These are all the same colour, by our hypothesis. Now take away one of these horses, stable it next door so it won't gallop away. Bring in a fresh horse from somewhere else (a pony won't do). Now we again have a collection of k horses and therefore they are all the same colour, since this is the hypothesis.
But what about the horse waiting next door? Surely it is the same colour as the original k-1 horses? Yes, it is, because when it was part of the original group of k happy horses it was the same colour as all the others. It still is (assuming it wasn't sprayed pink on the way to the stable). The ring-in is also the same colour (by hypothesis), so all the horses so far mentioned, ie k+1 of them, are the same colour.
This is what we were trying to prove.
Step 3. It follows that all horses are the same colour. (But what colour? you ask.)
Error 1
If we remove one horse from a collection containing just one horse then no horse is left. When we add the fresh horse it is the same colour as itself, but not necessarily the same colour as the original horse. It makes no sense to talk about the k-1 horses being the same colour as the original horse, because k-1 is zero. Thus we have failed to prove the thesis for k+1 on the assumption that it holds for k, simply because we cannot go from k = 1 to k = 2.
Error 2
The second error is a methodological one. Mathematical induction is a valid method of proof under the following conditions. The statement to be proved must be true for n = 1 and the hypothesis of its truth for the first k elements of the set must lead to its truth for the first k+1 elements of the set. It is implicit in this that the set must be ordered. The order does not matter but must be fixed.
So let's order the set of all horses from 1 to N, where N is the number of horses in existence. The proof above selects k horses from the ordered set eg { s1, s2, ... sk). They are taken by hypothesis to have the same colour. The problem is that we are not confining ourselves to the first k horses but to any k horses anywhere in the set of all horses. This includes the first k horses, the horses from the 2nd to the k+1 th horse, from the 3rd to the k+2 th horse, and so on.
It is equivalent to assuming the conclusion to be proved. The assumption that all horses have the same colour leads to the conclusion that all horses have the same colour. This is logic at its best.
In other words, for mathematical induction to be valid we have to restrict the assumption of the condition holding for k horses to a fixed set, ie to the first k horses under some arbitrary but fixed ordering of the set of all horses. In the proof above, the assumption has been posited for all subsets having k horses. This is very naughty.
Footnote.
Thinking about this problem made me realise that it is not the case that one can say of zero horses that they are green, say. One might assert, for instance, that every 60-foot gorilla in Sydney zoo wears pink underwear. Since there is no 60-foot gorilla in Sydney zoo, this statement is not false. Hence it must be true.
This is a fallacy, as not all statements are either true or false. The canonical example is the self-referential statement, such as "This statement is false". Some statements, though syntactically correct, are simply meaningless eg "Green is slow." Others are too vague to evaluate as true or false eg, "He is". Here we need a context (Who is 'he'?) to be able to evaluate the truth of the statement. Or take, "It rains often." This is also too unspecific to evaluate - rains where? and what does 'often' mean?
In fact, the statement that every 60-foot gorilla in Sydney zoo wears pink underwear is neither true nor false, but simply meaningless. A statement without a referent is without meaning.
If this were not so we could subtract one horse (s1) from the set having just one horse (s1) and state that all the horses in the resulting (empty) set had any colour we cared to name, for instance the colour of whatever other horse we cared to think of (s2). So the horse s2 would have the same colour as the horses in the empty set, which also have the same colour as the horse s1. Ergo s1 and s2 have the same colour. We can only avoid this paradox by not allowing the statement that a non-horse has a colour. In effect, non-existent things do not have properties and hence are not fit for discussion.
This may be discriminatory towards non-existent horses, but it rescues the rest of us from logical disasters.