Prove that every unbounded sequence contains a monotone subsequence that diverges to inifnity.

Question

I think I have the basic framework for this proof, but I am having trouble putting everything together in a convincing way.

I plan on showing that by the definition, an unbounded sequence $(a_n)$ has infinitely many $n$ such that $a_n>M$ where $M>0$, for some natural number $n$. I'm not sure how it is implied that there exists some $a_{n_k}$ such that $a_{n_k}>M$ for some natural number $k$. Let me know if I'm on the right track, and please help me string these ideas together!

It may be necessary to also consider a monotonic subsequence converging to $-\infty$, depending on whether "unbounded" means "neither bounded above nor bounded below" or "not both, bounded above and bounded below". — Daniel Fischer, Oct 12 '13 at 23:29
I can do a case where the sequence diverges to negative infinity. How would I go about moving from the boundedness definition to the conclusion? — Heath Huffman, Oct 12 '13 at 23:33
Let's get things straight: what's your definition of boundedness? — knsam, Oct 12 '13 at 23:34
There's a term bigger than the 1st term. There's a later term bigger than the term that's bigger than the first term. There's an even later term bigger than the term that's bigger than the term that's bigger than the first term. And so on. — Gerry Myerson, Oct 12 '13 at 23:35
kan-- a sequence a_n is unbounded iff there exists some n* in the natural numbers such that a_n > M for every M>0. — Heath Huffman, Oct 12 '13 at 23:38
Gerry-- Are you suggesting I can build a subsequence that behaves like a_n but starts on, say, the second term of a_n? — Heath Huffman, Oct 12 '13 at 23:39
@user45837 Then, $a_n = -n, n > 0$ is bounded according to your definition. Are you sure this is your definition? — knsam, Oct 13 '13 at 00:21
Related: Prove that every unbounded sequence contains a monotone subsequence that diverges to inifnity. — Martin Sleziak, Nov 26 '17 at 08:27

Sammy Black · Answer 1 · 2013-10-13T00:00:58.063

7

Assuming that the sequence is unbounded above, then you can generate your monotone divergent sequence as follows.

Choose $n_1$ to be the first index such that $a_{n_1} > 1$. Now, from the remaining sequence, choose $n_2 > n_1$ to be the first index such that $a_{n_2} > 2$ and $a_{n_2} > a_{n_1}$.

Rinse. Repeat.

For each $k \in \mathbb{N}$, you have $a_{n_k} > k$ and $a_{n_k} > a_{n_{k-1}}$, so the subsequence $\left( a_{n_k} \right)$ certainly diverges to infinity.

Why do you know that you can always find such an index? If you could not, then your sequence must have been bounded.

edited Oct 13 '13 at 00:00

answered Oct 12 '13 at 23:40

Sammy Black

25,273

2

You need not only $a_{n_k} > k$, you also need $a_{n_{k+1}} > a_{n_k}$. – Daniel Fischer Oct 12 '13 at 23:47
Would I use induction to prove this? – Heath Huffman Oct 12 '13 at 23:52
Good catch, Daniel. I will edit my response to include that requirement, as well. – Sammy Black Oct 12 '13 at 23:53
You can argue by contradiction that each new term in the subsequence is available. If it's not, then either $a_n \le k$ or $a_n \le a_{n_k}$ for all $n > n_k$. Either possibility contradicts the fact that $a_n$ is unbounded. – Sammy Black Oct 13 '13 at 00:00
Why after choosing $n_1$ such that $a_{n_1} >1$ Why we choose $n_2$ such that $a_{n_2}>2$? Can it be $a_{n_2}>1.0001$? – Wang Kah Lun Dec 27 '14 at 14:07
You can make things a little more general: just choose $n_k$ s.t. $a_{n_k} > \max{(a_{n_{k-1}}, k)}$. – Aug 26 '16 at 17:36

score 3 · Answer 2 · answered Oct 02 '15 at 17:54

I believe it's because you'd like to guarantee the convergence of $a_{n_k}$ to $\infty$. Actually, you could use the terms of any divergent sequence $b_k$ to do that comparation.

For example, you could chose $n_k$ to guarantee that $a_{n_k}>k^2$. The reasoning would be the same, because $b_k = k^2 \rightarrow \infty$ when $k \rightarrow \infty $

score 3 · Answer 3 · answered Oct 12 '13 at 23:36

3

You surely should use that there are infinitely many $n$'s such that $|a_n| > M$ for any real $M$. Consider one of positive and non-positive subsequences. At least one of them is not bountded, too. So you have right to assume without lose of generality that there are infinitely many $n$'s such that $a_n > M$ for any real $M$. If follows that there are infinitely many such $n$'s greater any $n'$. And so you may choose any $a_i$ and let $M = a_i$ to find $j$ such that $j>i$ and $a_j > a_i$. Do you see how to get monotonic subsequence converging to $+\infty$?

answered Oct 12 '13 at 23:36

Smylic

6,715

By picking any a_i and finding j so that j>i and a_j>a_i, did you construct the sequence to be monotonic? – Heath Huffman Oct 12 '13 at 23:50
For any $a_i$ you may choose such $j$. Then let $i' = j$, choose $j'$ and so on. – Smylic Oct 13 '13 at 00:51

Prove that every unbounded sequence contains a monotone subsequence that diverges to inifnity.

3 Answers3

Linked

Related