Prove or disprove: every infinite sequence of real numbers has either a nondecreasing subsequence or a nonincreasing subsequence.
Solution
The assertion is true.
1. Call an index \(n\) a tail maximum if\[ x_n\ge x_m \qquad \text{for every }m>n. \]If there are infinitely many tail maxima, the sequence has a nonincreasingsubsequence.
List infinitely many tail-maximum indices in increasing order: \[ n_1<n_2<n_3<\cdots. \] Since \(n_{j+1}>n_j\) and \(n_j\) is a tail maximum, \[ x_{n_j}\ge x_{n_{j+1}} \] for every \(j\). Hence \[ x_{n_1},x_{n_2},x_{n_3},\ldots \] is nonincreasing.
2. If there are only finitely many tail maxima, the sequence has astrictly increasing subsequence.
Choose \(N\) larger than every tail-maximum index, taking \(N=1\) if there are none. Then no \(n\ge N\) is a tail maximum. Therefore, for every \(n\ge N\), there exists \(m>n\) such that \[ x_m>x_n. \]
Set \(n_1=N\). Once \(n_j\) has been chosen, choose \[ n_{j+1}>n_j \] with \[ x_{n_{j+1}}>x_{n_j}. \] This recursion continues indefinitely and produces a strictly increasing, hence nondecreasing, subsequence.
3. Every infinite real sequence therefore has a monotone subsequence.
Either there are infinitely many tail maxima or there are only finitely many. Step 1 handles the first case and step 2 handles the second.
4. Q.E.D.
Step 3 proves the stated assertion.