Mathematical induction ''all horses are the same color''

[gfd43tg]

Homework Statement

Find the error in the following proof that \all horses are the same color" 4.

Claim: In any set of h horses, all horses are the same color.

Proof: By induction on $h$:

Base Case: For $h = 1$. In any set containing just one horse, all horses are clearly the same color.

Induction step: For $k \ge 1$ assume that the claim is true for $h = k$ and prove that it is true for
$h = k + 1$. Take any set $H$ of $k + 1$ horses. We will now show that all the horses in this set are
the same color:

$\bullet$ Remove one horse from this set to obtain the set $H_{A}$ with just k horses. By the induction
hypothesis, all the horses in $H_{A}$ are the same color.
$\bullet$ Now return the removed horse and remove a different one to obtain a new set $H_{B}$ with just
$k$ horses. By the same argument, all the horses in $H_{B}$ are the same color.
$\bullet$ Since $H_{A}$ and $H_{B}$ have some overlapping horses, it must be that all the horses in $H$ must
be the same color, and the proof is complete.1. Carefully follow the induction steps of the proof when going from two horses to three horses and
indicate if there is a step in the proof which is invalid (i.e. start by assuming that, in any set of
two horses, all horses are the same color):
Answer:2. Carefully follow the induction steps of the proof when going from one horse to two horses and
indicate if there is a step in the proof which is invalid (i.e. start from the obvious fact that, in
any set of one horse, all horses are the same color):
Answer:

Homework Equations

The Attempt at a Solution

This is such a weird question that ended up on an exam in a previous year. Well, I know for induction you start with the base case, assume its case $k$ is true, then show it is true for $k+1$. But I have no clue what to make out of this one

 

[PeroK]

Think about the value of h for which the inductive step fails. Hint: it only fails for one value of h.

 

[AlephZero]

The Attempt at a Solution

This is such a weird question that ended up on an exam in a previous year. Well, I know for induction you start with the base case, assume its case $k$ is true, then show it is true for $k+1$. But I have no clue what to make out of this one

That's correct.

The conclusion that "all horses are the same color" is obviously wrong. The question is asking you to go carefully through the argument when k = 2 and k = 1, and find exactly where it goes wrong.

It's hard to give too many hints without just telling you the answer, but think about any assumptions that are made in the proof, but not actually proved.

 

[.Scott]

In order to see the problem, you need to see why it might work.
If you knew that all sets of 10 horses had the same color, then you would also know that all sets of 11 horses were the same color because:
In the set of 11 horses, the first 10 are the same color, and the last 10 are the same color. But there's one more statement you need to make before you can say that all 11 are the same color. It's so obvious, that it's easy to just think it without saying it.