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?
 A: 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, ...$.
A: 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$".
