Induction proof verificiation

P(n) = in a line of n people show that somewhere in the line a woman is directly in front of a man. The first person will always be a woman and the last person in the line will always be a man

I wanted to prove this with induction and I was a little unsure of how to express this problem in the inductive step and whether I had the right cases and if I had shown them correctly.

Base case: n=2:

P(2) holds as a woman (front of line) will be directly in front of the man at the back of line since there are only 2 people.

Inductive hypothesis:

Assume P(k) holds for some integer k >= 2 there will be a woman directly in front of a man somewhere in the line, where the kth person is at the back of the line.

Inductive step:

Assuming P(k) holds, show P(k+1) holds too:

In a group of k+1 people consider the cases: (this is where I am slightly unsure)

(1) There are k males and 1 female

(2) There are k females and 1 male

If there are k males and 1 female, k males will always be behind the 1 female at the front by the rule in the statement and so the 2nd male from the front will be directly behind the female at the front and so there is always at least one case where a female is directly in front of a male while there are k males and 1 female in a group of k+1 people

If there are k females and 1 male, k females will always be in front of the 1 male at the back of the line by the rule of the statement and so the kth person who is a female will be directly in front of the k+1 person who is a male.

So in both cases there will always be at least one case where a female is directly in front of a male in a line of k + 1 people which concludes the inductive step.

As mentioned, I'm unsure if I've included the correct and all cases necessary in the inductive step and if I've explained them correctly for this proof. Could you verify and provide any pointers?

Answer

Your two cases are far from exhausting the possibilities. If $k=10$, for instance, the number of women can be anywhere from $1$ through $10$, and so can the number of men. You need to come up with an argument that covers all possibilities.

Try this: remove the man at the end of the line. Either the new line has a man at the end, in which care you can apply your induction hypothesis to it, or it has a woman at the end. How do you finish the argument in that second case?