4 ms·
It's similar to the proof that all horses are the same color. Suppose we have $n$ horses. It suffices to show they are all the same color. We do so by induct
by pmiller2 17y ago
It's similar to the proof that all horses are the same color.
Suppose we have $n$ horses. It suffices to show they are all the same color. We do so by induction on $n$.
If $n=0$ or $n=1$, then, certainly all $n$ horses are the same color, so the base case holds.
For the inductive hypothesis, assume we've shown that all the horses in any group of $n-1$ or fewer horses are the same color, and suppose we are faced with a group of $n$ horses. Choose some horse arbitrarily and remove it, leaving a group of $n-1$ horses for our consideration. By the induction hypothesis, these horses are all the same color. Replace the horse we removed and then remove a different horse from the group. Likewise, these horses are all the same color. This then implies that all $n$ horses are the same color. Since $n$ is arbitrary, this shows that all horses are the same color.
- Fizzley 17y agoCute. I know it's a joke, but the inductive step fails for n = 2. Each of the two groups of 1 horses being the same colour does not imply that all the horses are the same colour. :)
- pmiller2 17y agoYeah, but it's still hella fun to throw at a class of undergrads on a Friday afternoon. :-)