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


*

*Case (1):


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


*

*Case (2):


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?
 A: 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 case 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?
A: Let $P(n)$ be true iff there is at least one woman directly in front of a man in a line of length $n, n \ge 2$, and containing only men and women, with the person at the front being a woman and at the back being a man.
Base case:
If $n = 2$, then the woman at the front is directly in front of the man at the back
$\therefore P(2) = true$
Inductive Step:
Assuming the second last person in line must either be a man or a woman:
If the second last person in line is a woman, the man at the end is behind that woman $\therefore P(n) = true$
If the second last person in line is a man, that man is the last in a shorter line which also begins with a woman $\therefore P(n) = P(n-1)$
$\therefore P(n-1) \implies P(n)$ independent of the gender of the second-last person in line. (there is no case where $P(n-1)$ is true and $P(n)$ is false)
$P(2) \land (P(n-1) \implies P(n))$
$ \therefore P(n), \forall n \ge 2$
A: Starting from the last person in the line, in front of him must be a woman (solved) or a man. in front of this man must be a woman (solved), or another man. Eventually a woman must appear, because the first person in the queue is a woman (solved).
Also if true for $k$, then inserting a man or a women anywhere but the change is ok, but so is inserting a man/woman in between the change.
For example, WWWMM -> WMWWMM (ok) or WWW(W/M)MM (ok)
