Problem: Show that all horses are of the same color.
“Solution”: We will show, by induction, that for any set of $ n$ horses, every horse in that set has the same color. Suppose $ n=1$, this is obviously true. Now suppose for all sets of $ n$ horses, every horse in the set has the same color. Consider any set $ H$ of $ n+1$ horses. We may pick a horse at random, $ h_1 \in H$, and remove it from the set, getting a set of $ n$ horses. By the inductive hypothesis, all of the $ n$ remaining horses are the same color.
On the other hand, if we remove a different horse $ h_2 \in H$, we again get a set of $ n$ horses which are all the same color. Let us call this color “brown,” just to give it a name. In particular, $ h_1$ is brown. But when we removed $ h_1$, we got that all the remaining horses had the same color as $ h_2$. So $ h_2$ must also be brown. Hence, all horses in $ H$ are brown.
Explanation: The argument here is valid for almost all $ n$. For large $ n$, it is a very natural argument that follows from the inductive hypothesis. However, it fails for $ n=2$ (and this is the only time it fails). By having only two horses, we cannot conclude that the removed horses have the same color, because there aren’t any horses remaining in $ H$ to apply the transitivity of “having the same color as.”
This false proof highlights the danger of neglecting the base case of an inductive argument. Here the true base case was not $ n=1$, but rather $ n=2$. Since the base case is false, we should have prudently stopped our argument there before embarrassing ourselves.
I enjoyed your “proof”, but I’d suggest a revision to the reason it’s invalid. I don’t think it’s so much that you need to consider the case of 2 horses. What the proof does, is not the normal sort of induction that I’ve seen. Typically you show it’s true for n=1 (which in the horse proof is trivial). Then you assume that it’s true for n, and then show that this means it’s true for n+1. You can’t do that in this horse of a different color proof. If you assume it’s true for n, you really don’t have any way of getting to n+1. To start by assuming that it’s true for ANY collection of n+1, you’re begging the question.
In any case, I still have to say that I enjoyed reading it.
The proof fails for n=2 because the general argument works precisely when there are at least three horses. In particular, there has to be a horse which was not removed in order to conclude that the two removed horses share its color. Rest assured that this is a standard induction argument, and I don’t assume anything about the set of n+1 horses (H in the above proof).
So in fact, if it were true that any set of n = 3 horses is unicolored, then it would be true that any set of n > 3 horses is unicolored.
You’re right, I misread your “proof”. For some reason I thought I read that you started with the assumption about n+1 horses. Must have been before I had my coffee.
@mitchellkaplan You actually hinted at another common mistake with induction (not sure if j2kun has another false proof demonstrating it):
1. Take the case with
(incorrectly!)
to the case with 
2. Reduce it to the case with
3. Apply the induction hypothesis on the reduced case
4. Expand the case with
For example, I remember seeing this in graph-related proofs where you would remove a node from the graph except the resulting graph didn’t satisfy certain constraints (and hence the induction hypothesis did not apply to it!).
Another similar mistake is to take the
case and make the erroneous claim that every 
case can be extended from a 
case. I also saw this with respect to graphs where not every graph with constraint “Foo” and 
nodes could be constructed from a graph with constraint “Foo” and 
nodes.
Induction’s pretty hard? 🙂
Before I read the explanation, I had deduced that the problem was with the case of n = 1, because you need at least two different things in order for “same as” to make sense. (Never trust a proof that uses “obviously” or trivially”.)
I disagree, because I am certainly the same height as myself, as am I the same age and weight and myself. I don’t see why that is invalid to say.
OK. I guess x = x is legitimate. Perhaps my unease with it has to do with rhetorical tautologies being frowned upon.
“We will show, by induction, that for any set of n horses, every horse in that set has the same color….Now suppose for all sets of n horses, every horse in the set has the same color”
So, I should suppose the thing that you are about to prove?
This is how induction works. Here n is a fixed number, and you’re using it to prove the statement holds for n+1.
>> Now suppose for all sets of n horses, every horse in the set has the same color.
We don’t “suppose” the thing we’re trying to prove.
It is called mathematical induction. This proof does not quite use it properly, but this sentence is not where the problem is.
I think you need to be clearer about how you’re using n.
In the first sentence, you mean for all values on n, right? But next you say “suppose for all sets of n horses, every horse in the set has the same color”. But if I did this (with the same sense of n) , we’d be finished – there wouldn’t be anything left to prove. So I presume you now mean “n” to have a specific value, correct? In other words, you mean “suppose that there is some value of n for which all sets of n horses are the same color”?
Then later you say it fails for n=2: “The proof fails for n=2 because the general argument works precisely when there are at least three horses
….
So in fact, if it were true that any set of n = 3 horses is unicolored, then it would be true that any set of n > 3 horses is unicolored.
”
But it’s obvious that if all sets of just 2 horses are the same color, then all horses are the same color (since, if there was more than one color of horse, I could always construct a set of 2 horses of different colors).