Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

3 Answers 3

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

share|improve this answer
    
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}.$

share|improve this answer

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.

share|improve this answer
    
If you are confused I would be happy to explain. –  CodeKingPlusPlus Oct 19 '12 at 4:16

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.