Questions on "All Horse are the Same Color" Proof by Complete Induction I'm bugged by the following that's summarized on p. 109 of this PDF.


  False theorem: All horses are the same color.
  
  Proof by induction:
  
  $\fbox{$P(n)$ is the statement: In every set of horses of size $n$, all $n$ horses are the same color.}$
  $\fbox{Base Case or $P(1)$:}$ One horse is the same color as itself. This is true by inspection.
  $\fbox{Induction Step:}$ Assume $P(k)$ for some $k \geq 1$.
  $\fbox{Proof of $P(k + 1) :$}$
  Since $\{H_1, H_2, ... , H_n\}$ is a set of $n$ horses, the induction hypothesis applies to this set. Thus, all the horses in this set are the same color.
  Since $\{H_2, H_3, ... , H_{n+1}\}$ is also a set of $n$ horses, the induction step likewise holds for this set. Thus, all the horses in this set are the same color too.   
  
  Therefore, all $n +1$ horses in $\{H_1, H_2, H_3, ... , H_n , H_{n+1}\}$ are the same color. QED.


The issue the instructor was trying to point out is clearly valid. For the case $n = 1$, there is only ${H_1}$. So this case says nothing about possible overlapping elements of each set of $(n + 1)$, for instance $H_2$ in the above proof.  

But it was proposed in the class discussion that this was the only problem. Had you been able to prove $P(2)$ true, then a proof of the above format would have been fine.  

My interpretation is that yes, you could prove all horses are the same color, if you can prove that any set of two horses will be the same color. But this format would not work.

Why not? The problem I see is that the above proof is for the existence of at least one particular pair of sets of horses of sizes $n$ and $n + 1$, such that in each set, all horses are the same color.  Particularly when the set of size $n$ is a subset of the set of size $n + 1$.  In order to prove the induction step, don't you need to prove that sets of sizes $n$ and $n + 1$, do not necessarily contain the same, overlapping elements?

You could prove that any horse can be added to a set of 2 horses.  Take the last two, and they must be the same color, and so on.  Wwhatever color the first two happen to be, all other horses must thus be the same color.  

Am I misinterpreting the example, or am I making a logical error? Thanks in advance.
It’s clear from the question and from your discussion with @DonAntonio that you don’t actually understand the induction step of the argument. You seem to think that it involves comparing some previously chosen set of $n$ horses with some new set of $n+1$ horses, but it does not. Let me see if I can explain more clearly just how it does work.

We assume as our induction hypothesis that if $H$ is any set whatsoever of $n$ horses, then the horses in $H$ are all the same color. Now let $H=\{h_1,h_2,\dots,h_{n+1}\}$ be any set of $n+1$ horses; our goal is to show that all of the horses in $H$ are the same color. To do this, we look at the subsets

$$H_0=\{h_1,\dots,h_n\}\quad\text{and}\quad H_1=\{h_2,\dots,h_{n+1}\}\;.$$

Each of these subsets contains $n$ horses, so by hypothesis all of the horses in $H_0$ are the same color, and all of the horses in $H_1$ are the same color. 


  Note: The two $n$-horse sets that we’re looking at here were not given to us ahead of time: they are just two different $n$-horse subsets of $H$. And in fact any two different $n$-horse subsets of $H$ will work equally well for the argument.


Now if $n\ge 2$, the horse that I’ve called $h_2$ is in both $H_0$ and $H_1$. (In fact every horse except $h_1$ and $h_{n+1}$ is in both $H_0$ and $H_1$.) Since $h_2$ is in $H_0$, and we already know from the induction hypothesis that all of the horses in $H_0$ are the same color, it follows that every horse in $H_0$ is the same color as $h_2$. But $h_2$ is in $H_1$ as well, so by exactly the same reasoning we conclude that every horse in $H_1$ is the same color as $h_2$. But every horse in $H$ is in $H_0$ or $H_1$ (or both), so every horse in $H$ is the same color as $h_2$, and therefore the horses in $H$ are all the same color. This completes the induction step.



There is absolutely nothing wrong with that argument — provided that $n\ge 2$. In particular, it does not involve starting with some particular set of $n$ horses known to be the same color and trying to use that set to show that the horses in some arbitrary set of $n+1$ horses are all the same color. The argument starts with a set of $n+1$ horses and proceeds by looking at two $n$-horse subsets of the given set. It’s important here to realize that the induction hypothesis does not say that there is some particular set of $n$ horses that are all the same color: it says that in any set of of $n$ horses, all of the horses are the same color.

The argument fails only when $n=1$. In that case it fails because the sets $H_0=\{h_1\}$ and $H_1=\{h_2\}$ no longer overlap: there is no horse in both sets. Thus, while it’s true that all of the horses in $H_0$ are the same color and that all of the horses in $H_1$ are the same color, we can no longer infer that those two colors must be the same. But if we could somehow show that in every set of two horses, both horses were the same color, the induction argument as given would work just fine: we’d always be considering some $n\ge 2$, so the sets $H_0$ and $H_1$ would overlap.
Just want to add a quick summary.

The proof is "almost" perfect. It simply fails on n=1.

Yes obviously any set with 1 horse will have the same color. However, you can't extend that to n=2.

If you can somehow proof that any set of 2 horses have the same color then yes, you got something right, that any set with any number of horses will have the same color.