I am trying to proof the pigeonhole problem in Coq. Therefore I have the following lemma that I want to proof:
Lemma pigeon_hole :
forall m n, m < n ->
forall f, (forall i, i < n -> f i < m) ->
exists i, i < n /\
exists j, j < n /\ i <> j /\ f i = f j.
From my teacher I have got the hint that a useful tactic to automatically prove equalities and inequalities between natural numbers is
omega.
But I doubt if that is relevant here.
I thought that it could be done with induction as in https://math.stackexchange.com/questions/910741/constructive-proof-of-pigeonhole-principle.
If I try to do induction on n, I get the base case with n=0. Here I first do 'intros.' and then 'induction n.'.
But I want the base case n=2. Is there a possibility in Coq do get that or am I on the wrong track?