Here's the problem I have to prove:

Every sequence in a totally ordered set has a monotonic subsequence.

We have to use induction to prove this statement, but I am not too good and writing induction proofs as I don't know how to start them and what to put in my induction hypothesis. Any suggestions would be appreciated! Thanks