Past exam of the mathematics course of the University of Oxford / 2015 / Prelims / Mathematics II / 1 / a / i / Solution

Call $k$ a peak of a sequence when $a_k\ge a_m$ for every $m>k$. If there are infinitely many peaks of a sequence, list their indices in increasing order, $k_1<k_2<\cdots$. Since $k_{r+1}>k_r$,This is a decreasing subsequence; throughout this argument, a decreasing monotone sequence may have equal successive terms.

If there are only finitely many peaks of a sequence, choose $N$ beyond all their indices; take $N=1$ if there are none. Every $n\ge N$ fails to be a peak of a sequence, so some $m>n$ satisfies $a_m>a_n$. Starting with $n_1=N$, choose such an $n_{r+1}>n_r$ recursively. This givesThe two cases prove the monotone subsequence theorem without any boundedness hypothesis.