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.