It's false because the induction step assumes n > 2.
You can't send out a non-redhead, bring them in, and then send out a different non-redhead if you only have one non-redhead.
SPUI's comment is mistaken on two counts:
a) If you have no people in a room, it is true that they are all redheads! This is because the converse is 'there is a person in the room who is not a redhead' which is false.
b) You don't need to do the "true for n=0" -> "true for n=1" step since we know it's true for n=1 anyway.
Oh, and how come these last three noders know words like probability, set, integer, function, and (gasp) bijection, when their grasp of maths is clearly about as good as my grasp of pre-twelfth-century formal Korean?...
Aozilla. You are entirely correct, but so am I. Our arguments are just slight variations on one another. The point we are both making is that when n=2, you cannot do the second sending-out and still have a red-head left in the room. My version was "You have to keep your original red-head, so there's no-one you can send out", and yours was "If you send out the other person, you have lost your red-head".