Homework Help: Everyone has same (Induction Fallacy)

1. Sep 9, 2010

NastyAccident

1. The problem statement, all variables and given/known data
In any group of (n) people, if one person has brown hair, then everyone has the same hair color.

Suppose: For any group of people everyone has the same hair color.

Case 1: In any group of 1 person, everyone has the same hair color.

Case 2:
Now, with a group of k+1 people, remove the first person (A) from it.
This yields a group that has k people and everyone in this group has the same color hair particularly the second person (B) and third person (C).
Now, consider the group of k+1 and remove only the second person (B) from it. This yields a group of k again with all having the same hair color particularly A & C.

Question: Where is the flaw?

2. Relevant equations
Mathematical Induction

3. The attempt at a solution

I believe the flaw in this type of proof is with the case 1 statement. This flaw then ripples down the rest of the proof as well.

The flaw specifically is the fact that they are looking at a group of one person as the beginning condition. So, if we were to say that we wanted to start at P(n) with n being two instead of one, then we cannot prove that statement. In essence, P(1) holds, but if you plug in P(2) or P(3) you cannot say definitively that they all share the same hair color.

That's the only thing I can think of since mathematical induction in my mind is sort of like an assembly line of sorts. Toward the end everything seems fine, but in the beginning it seems just off slightly.

Sincerely,

NA

2. Sep 9, 2010

Petek

The case 1 argument is OK. However, consider the case in which the group consists of two people. See what happens to the case 2 argument if you try to apply it there.

Petek

3. Sep 9, 2010

HallsofIvy

I first heard this as the "horse of a different color" problem- to show why an induction proof that "all horses are of same color" was invalid. The problem, is NOT in the first statement because if you have a set with one member, it certainly is true that any member of that set is of the same color! The answer is exactly as Petek say- you cannot make the jump from 1 to 2 because if you have a set of two, you cannot construct distinct subsets containing a common element. I think that's pretty much what you said but that involves the "induction hypothesis", the second part not the first.

4. Sep 9, 2010

NastyAccident

Ahh, so in this case in point there was simply no intersection between the set with A being removed and the set with B being removed?