# Induction Proofs for Sequences

• Apr 30th 2008, 05:46 PM
beachbum87
Induction Proofs for Sequences
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
• Apr 30th 2008, 06:08 PM
ThePerfectHacker
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 $\displaystyle \{ a_n\}$ be a sequence in a totally ordered set $\displaystyle A$. Define $\displaystyle a_m$ to be dominant if $\displaystyle a_m > a_k$ for all $\displaystyle k>m$.

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

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