Veja se você concorda.
Essa fila deve ter no mínimo duas pessoas ( Homem, Mulher ).
Se a fila tem n pessoas, pelo PIF, vamos assumir que há uma Mulher diretamente na frente de um Homem numa posição k da fila que seria algo assim:

Mulher, ........,

Mulher,

Homem, .........,

Homem .
Essa seria a nossa hipótese de indução, essa fila satisfaz: há uma Mulher diretamente na frente de um Homem. Os parênteses contém a posição da fila.
Agora é só considerar uma fila com

pessoas. Então, essa enésima primeira pessoa será inserida:
Antes da posição k: a fila continua valendo.
Na posição k+1: a fila continua valendo independente dessa nova pessoa ser Mulher ou Homem.
Após a posição k+1: A fila continua valendo.
Logo se a fila vale para n pessoas então vale para n+1 pessoas.
Não ficou muito formal - mas acho que é isso.