Prove that every sequence of real numbers has a monotone subsequence.

Step-by-step solution

1. 1

   Define the right notion: a peak. Call an index $n$ a peak of the sequence if

   $a_n\ge a_m\quad\text{for every }m>n$

   that is, no later term ever exceeds $a_n$. Every index is either a peak or not, so the whole proof splits into just two cases — this dichotomy is the entire idea.

2. 2

   Case 1: there are infinitely many peaks. List them as $n_1<n_2<n_3<\cdots$. Since $n_k$ is a peak and $n_{k+1}>n_k$, the defining property gives

   $a_{n_k}\ge a_{n_{k+1}}$

   for every $k$, so $\{a_{n_k}\}$ is a non-increasing subsequence. Done in this case.

3. 3

   Case 2: there are only finitely many peaks. Let $N$ be larger than every peak, so no index $n\ge N$ is a peak. By the definition of "not a peak", for each such $n$ there exists some $m>n$ with

   $a_m>a_n$

4. 4

   Build a strictly increasing subsequence recursively. Set $n_1=N$. Since $n_1$ is not a peak, choose $n_2>n_1$ with $a_{n_2}>a_{n_1}$. Since $n_2\ge N$ is also not a peak, choose $n_3>n_2$ with $a_{n_3}>a_{n_2}$, and so on. This produces indices $n_1<n_2<n_3<\cdots$ with

   $a_{n_1}<a_{n_2}<a_{n_3}<\cdots$

   a strictly increasing subsequence.

5. 5

   Conclude. In both cases a monotone subsequence exists, and the two cases are exhaustive, so

   $\boxed{\text{Every real sequence has a monotone subsequence}}$

6. 6

   Note the consequence and check the edge cases. Combined with the fact that a bounded monotone sequence converges, this immediately yields the Bolzano–Weierstrass theorem. Two sanity checks on the statement: for $a_n=(-1)^n$ the peaks are the even indices (infinitely many), giving the constant — hence non-increasing — subsequence $1,1,1,\ldots$; for $a_n=n$ there are no peaks at all, and Case 2 produces the increasing subsequence $1,2,3,\ldots$. Note the theorem asserts monotone, not convergent: an unbounded sequence has a monotone subsequence but no convergent one.