Are all horses really the same color? A "proof" by induction.

I will prove that given any size group of horses, all horses in the group must all be the same color as each other. Since there are no restrictions on the size of the group, I will have shown that all horses in the world are the same color! Since a quick trip to any local stable will show that this result is false, there must be an error somewhere in the proof. But where? Be specific.

I make the simplifying assumption that each horse is a single color (this may not really be accurate, but this is not the error that you should be looking for).

Base step: It is clearly true that if a group contains only 1 horse, then all horses in the group are the same color.

Induction hypothesis: Assume that in any group of n horses, all horses must have the same color. Does this imply that the same must be true for any group of n+1 horses?

Let's consider a group of n+1 horses, numbered 1, 2, 3, ... up to n+1.

Text Box: 1	2


Horses 1 - n form a group of n horses, so by the induction hypothesis they must all be the same color - say, brown.

n brown horses in a yellow pen

Text Box: 1	             2


Horses 2 - (n+1) also form a group of n horses, so again by the hypothesis they too must all share one color.

n horses in a green pen. By hypothesis they are all one color

Text Box: 1	             2


What color are the horses in the 2nd group? Since the second group overlaps the first group (notice the horses in the middle of the diagram, numbered 2-n, that are counted in both groups), we know that at least some of the horses in this group are brown. And since all horses in this group are the same color, they must all be brown.

Therefore, all n+1 horses are brown.

Since we have shown that the property works for 1, and that if it works for n it must also work for n+1, our proof by induction is complete. All horses are the same color!


Think of any two positive integers, and call them m and n. Ill prove that m=n in other words, given the chance to pick any two positive integers, you picked the same number twice.

Without loss of generality, we can assume m≤n. I will induct on n.


Base case: Suppose n=1. Then m must be a positive integer, but no larger than 1. The only possibility that leaves for m is 1, so m=n=1.


Induction hypothesis: Suppose our property holds for some number N, ie if the larger number is N, than the two numbers selected must be equal (both must be N).


Induction step: What if the larger number n=N+1? Then we have two selected 2 numbers,

{m,n} = {m,N+1}


Consider for a moment the set of two numbers obtained by subtracting 1 from each of our chosen numbers: {m-1,n-1} = {m-1,N}. This new set contains two numbers the larger of which is N, so by our induction hypothesis they are equal, i.e. m-1=N. Therefore m=N+1, proving that our original set {m,n} is really {N+1,N+1}, and again the two numbers must be equal!


We therefore have our base case and our induction step proved, and so we can conclude that given the opportunity to pick any two positive integers, you will always pick the same one twice. Or is there a flaw somewhere?