The Monotone Subsequence Theorem

Monotonic Sequences and Subsequences

Recall from the Monotone Sequences of Real Numbers the definition of a monotone sequence. Now that we have defined what a monotonic sequence and subsequence is, we will now look at the very important Monotonic Subsequence Theorem.

The Monotone Subsequence Theorem

Theorem (Monotone Subsequence): Every sequence $(a_n)$ of real numbers has a monotonic subsequence $(a_{n_k})$.

• Proof: Let $(a_n)$ be a sequence of real numbers, and call the $m^{\mathrm{th}}$ term of the sequence $a_m$ a "peak" if for all $n ≥ m$ we have that $a_m ≥ a_n$. In other words, we will call the $m^{\mathrm{th}}$ term a peak if every successive term is less than or equal in size. We note that an increasing sequence will have no peaks as each successive term is larger than the previous, while a decreasing sequence will have infinitely many peaks as each successive term is smaller than the previous. Now consider the follow two cases.

• Case 1: Suppose that the sequence $(a_n)$ has infinitely many peaks. Form a subsequence with these peaks denoted $a_{n_1}, a_{n_2}, ..., a_{n_k}, ...$. Since each of these terms is a peak and $n_1 < n_2 < ... < n_k < ...$ we have that $a_{n_1} ≥ a_{n_2} ≥ ... ≥ a_{n_k} ≥ ...$ and so $(a_{n_k})$ is a monotonic decreasing subsequence of $(a_n)$.

• Case 2: Suppose that the sequence $(a_n)$ only has a finite number of peaks denoted $a_{n_1}, a_{n_2}, ..., a_{n_k}$. Let $s_1 = n_k + 1$, that is let $s_1$ be the first index after the last peak in the sequence $(a_n)$. Then we have that $a_{s_1}$ is not a peak, and so then there exists an $s_2$ such that $s_1 < s_2$ and $a_{s_1} ≤ a_{s_2}$. Also, $a_{s_2}$ is not a peak and so there exists an $s_3$ such that $s_2 < s_3$ and $a_{s_2} ≤ a_{s_3}$. Continue on and crease a subsequence $a_{s_1} ≤ a_{s_2} ≤ ... ≤ a_{s_m} ≤ ...$, and so $(a_{s_m})$ is a monotonic increasing subsequence of $(a_n)$.

• Thus we have shown that whether $(a_n)$ has infinitely many or finitely many peaks, then $(a_n)$ regardless has a monotonic subsequence. $\blacksquare$