# Monotone Subseqences

If limsup$(p_k) \neq \infty$ and liminf$(p_k) \neq -\infty$, prove or disprove that $(p_k)$ has monotone increasing and monotone decreasing sub sequences.

-
What have you found out so far? – Hagen von Eitzen Oct 18 '12 at 20:35
Does monotone include constant sequences? It doesn't change the answer, but it makes one side easier. – Ross Millikan Oct 19 '12 at 3:44

Hint: Consider $p_k=(-1)^k+\frac1k$. What is $\liminf p_k$ and $\limsup p_k$? Can you find a monotone increasing subsequence?

-
How about $p_k = \frac{1}{k}$? – Stefan Smith Oct 18 '12 at 23:24
A good answer for one of the two questions and a good hint for the other. +1 – Ross Millikan Oct 19 '12 at 3:45
What do you guys think of my proof? – CodeKingPlusPlus Oct 19 '12 at 20:09

Denote $M=\{n \in \mathbb{N}\colon\quad (\forall m>n)\quad p_m>p_n\}$. Set $M$ can be either finite or infinite.
If $M$ is infinite, then it can be represented as $M=\{n_1,\, n_2,\, \ldots\,, n_k,\,\ldots \}$ with $n_1< n_2< \ldots< n_k<\ldots$ Characteristic property of $M$ implies that $p_{n_1}< p_{n_2}< \ldots< p_{n_k}<\ldots$ and in this case $\{p_{n_k} \}_{k \in \mathbb{N}}$ is (strictly) increasing subsequence. If $M$ is finite, then the set $\mathbb{N} \setminus M$ is infinite, bounded below and unbounded above. Let $n_1 \in \mathbb{N} \setminus M$ be minimal natural number such that $(\forall m\geqslant n_1) \quad m\notin M.$ Because $n_1 \notin M$ and the set $M_1=\{m:\quad (\forall m\geqslant n_1) \quad m\notin M\}$ is unbounded above we conclude that there exists $n_2>n_1$ and $n_2 \notin M.$ It means that $p_{n_2}\leqslant p_{n_1}.$ Continuing this process, we obtain non-increasing subsequence ${\lbrace p_{n_k} \rbrace}_{k\in\mathbb{N}}$ such that $\,\, \ldots \leqslant p_{n_k}\leqslant \ldots\leqslant p_{n_2} \leqslant p_{n_1}.$

-

I've got a good trick for this one, that is elegant to understand and replicate.

Proof:

Let $a_n$ be any sequence and define a dominant term of a sequence as the following:

$a_m$ is a dominant term $\iff a_m \geq a_n$ for all $n > m$

Now we have two cases to consider.

Case 1: We have infinitely many dominant terms.

Select any set of dominant terms from our sequence. Then we will have a monotone non-increasing subsequence.

Case 2: We have finitely many dominant terms. Select $n_1$ s.t. $n_1$ is beyond all dominant terms. Then we know for $N \geq n_1$ there exists $m$ s.t. $a_m > a_{n_1}$. (If this does not make sense to you think if this were not true)

So take $N = n_1$ and select $n_2$ so that: $n_2 > n_1$ and $a_{n_2} \geq a_{n_1}$. (**)

Now we will proceed with induction. Suppose for $N \geq n_1$ we have selected $n_1 < n_2 < ... < n_k$ so that $a_{n_1} \leq a_{n_2} \leq ... \leq a_{n_k}$

Now repeat (**): Take $N = n_k$ and select $n_{k+1}$ so that: $n_{k+1} > n_k$ and $a_{n_{k+1}} \geq a_{n_k}$

Thus, the $k^{th}$ step $\implies$ the $(k+1)^{th}$, and we have found a monotone non-decreasing subsequence in this case.

Therefore we have found monotone subsequences in both cases and the claim is true.

End of Proof.

The intuition behind this proof is mainly the fact that for finitely many dominant terms we can always find a term that is bigger than some other term after we have "looked past" all the dominant terms. So just select these "bigger" terms and we will get the subsequence we want.

-
If you are confused I would be happy to explain. – CodeKingPlusPlus Oct 19 '12 at 4:16