Induction Proofs for Sequences

Quote:

Originally Posted by beachbum87

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

Here is how Donald Newman would prove it.

Let $\{ a_n\}$ be a sequence in a totally ordered set $A$ . Define $a_m$ to be dominant if $a_m > a_k$ for all $k>m$ .

Case 1: There are infinitely many dominant terms. Then choose $a_{n_1},a_{n_2}, ...$ to be dominant terms, in increasing substrict order as you go along the sequence. Then $a_{n_1} > a_{n_2} > ...$ is a monotone subsequence.

Case 2: There are finitely many dominant terms. Let $N$ be larger of all indexes of the dominant terms, i.e. if $n\geq N$ then $a_n$ is not dominant. Pick $a_N$ , this is not dominant so there is $n_2$ so that $a_{n_2}\geq a_N$ . But $a_{n_2}$ is not dominant so pick $n_3$ so that $a_{n_3}\geq a_{n_2}$ . And so on. Thus, $\left< a_N, a_{n_2}, a_{n_3}, ... \right>$ is a monotone subsequence.