# For any sequence of real numbers, one can always find a subsequence that is monotone

Homework Exercise: Let $$(x_n)$$ be $${\bf any}$$ sequence of real numbers. $${\bf carefully}$$, that is, from first principles, prove that there exists a subsequence that is monotone.

## My sol:

Let $$x \in \mathbb{R}$$. Then, $$(x_n)$$ either converges to $$x$$ or not. So, we can do cases.

$${\bf Case 1.}$$ If $$x_n \to x$$, then for any $$\epsilon > 0$$ one can take $$N$$ so that for all $$n > N$$ (in particular, for $$n=n_1$$) we have $$|x_{n_1} - x| < \epsilon$$

Applying the definition again with $$\epsilon = |x_{n_1} - x| > 0$$ and taking $$n = n_2 > n_1 > N$$ we observe that $$|x_{n_2} - x| < |x_{n_1} - x|$$

Now, choose $$\epsilon = |x_{n_2} - x| > 0$$ and take $$N > 0$$ so that for all $$n_3 > n_2 > n_1 > N$$ one has $$|x_{n_3} - x | < |x_{n_2} - x |$$

If we continue in this fashion, we observe that for $$n_k > n_{k-1} > ... > n_1$$ we have $$x_{n_1} < x_{n_2} < .... < x_{n_k}$$. In particular $$(x_{n_k})$$ is a monotone subsequence of $$(x_n)$$

$${\bf Case2.}$$ Suppose $$x_n$$ not converges to $$x$$. We know $$\exists$$ some $$\epsilon > 0$$ and some subsequence $$(x_{n_k})$$ so that $$|x_{n_k}-x| \geq \epsilon$$ $$\forall k \in \mathbb{N}$$

So, notice that $$x_{n_k} - x \geq \epsilon \implies x_{n_k} \geq x + \epsilon$$. Also, $$x_{n_{k+1} } - x < - \epsilon \implies -x_{n_{k+1}} >-x+\epsilon$$

So that $$x_{n_k} - x_{n_{k-1}} \geq 2 \epsilon > 0$$ so that $$x_{n_k} > x_{n_{k+1}}$$ and thus the subsequence is monotone. QED

Is this a correct and 'careful' proof?

• In case 2, note that $|a| \geq b$ implies $a \geq b$ AND $a \geq -b$ – Ricky_Nelson May 22 '20 at 8:32
• Am I missing something, or can the monotone subsequence be finite? (If so, this question becomes kind of trivial, so maybe that's not what was intended, but I don't see anything that requires it unless that's somehow inherent in the definition of "monotone subsequence".) – David Z May 22 '20 at 17:34
• @DavidZ: In the context from which this pretty clearly comes it is generally very safe to assume that subsequence means infinite subsequence. – Brian M. Scott May 22 '20 at 18:34
• For a completely different approach you might want to take a look at this question. (I wasn’t online to see your request to me until after the answers below had been posted.) – Brian M. Scott May 22 '20 at 20:53
• This question has nothing to do with convergence: it is more elementary than that. See here for a proof that doesn't use convergence. – TonyK May 23 '20 at 23:21

Neither case is good. Case 1 is not good because you are just saying that successive elements $$x_{n_k}$$ are closer to $$x$$, but nothing about their order (consider the sequence $$x_n = (-1)^n/n$$). Although I suspect you just forgot to write out the details of this (it is easily fixable, the minor fix is given in the final paragraph). Case 2 is not good because it is mentioned in the comments by Ricky Nelson.

Here is a sort of cleaned up proof that reduces the problem to something like your Case 1: $$x_n$$ is either bounded or unbounded. If it is unbounded, assume without loss of generality that it is unbounded above. Then the problem is done.

Now assume it is bounded. If the sequence does not converge, then take a convergent subsequence using Bolzano Weierstrass to reduce to the case when $$x_n$$ converges.

Now we do a clean proof of the case where $$x_n \to x$$. Either there are infinitely many $$x_n \geq x$$ or infinitely many $$x_n \leq x$$. Assume without loss of generality that there are infinitely many $$x_n \leq x$$ (this is the step you missed in your proof). If there exists $$\epsilon > 0$$ such that there exists some $$x_n < x - \epsilon$$, then take that to be the first element $$x_{n_1}$$. Continue recursively, and if there is no such $$\epsilon > 0$$, then let the rest of the elements of the subsequence be $$x$$. Then this sequence is monotonically increasing, so we are done.

EDIT: hm, the final paragraph is weirdly wordy, instead of "If there exists $$\epsilon > 0$$ such that there exists some $$x_n < x - \epsilon$$", we could just say "If there exists some $$x_n < x$$".

• We don't need to use the concept of convergence here at all (see this question). The statement is true in $\Bbb Q$ as well as $\Bbb R$, after all. – TonyK May 23 '20 at 23:18

Unfortunately it isn't. In case 1, your subsequence is getting closer to the limit but it might still be alternating above and below. Consider applying your procedure to the sequence: $$1, -\frac{1}{2}, \frac{1}{3}, -\frac{1}{4}, \frac{1}{5}, -\frac{1}{6}, ...$$.

You can fix this by splitting it into two subsequences: above and below. One of these might be finite or empty but they cannot both be. So, you will have at least one monotone subsequence.

Case 2 also has problems. Consider the sequence $$1, -1, 1, -1, 1, -1, 1, -1, ...$$.

• How in your "fix" do you know that "you will have at least one monotone subsequence"? – Adayah May 22 '20 at 15:53
• The terms in the OP's sequence will be getting closer to the limit but they might fail to be monotone as some may be above the limit and some below as in my example. Split the subsequence into two: those above and those below. These subsubsequences now must be monotone. Maybe one is finite or empty but they cannot both be as the OP's subsequence is not finite. – badjohn May 22 '20 at 16:20
• $\frac2n+(-1)^n\frac1n$ is a non-monotone sequence where all terms are above the limit. – Teepeemm May 22 '20 at 16:28
• Yes, but the OP's procedure should extract a monotone subsequence from it. My procedure is not complete. It is an add on to the OP's. – badjohn May 22 '20 at 16:32