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