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?
Best Answer
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, ...$.