# Math Help - monotonic subsequences.

1. ## monotonic subsequences.

Firstly, i'm sorry for getting stuck three times in one day! I'm pretty much hogging this board which isn't that nice.

Anyway, i'm stuck on this:

Prove that every sequence has a monotonic subsequence.
Kindly (?), the homework sheet offers some hints in the form of more questions!

1). If there are an infinite number of floor terms, show they form a monotonic increasing subsequence.

2).If there are a finite number of floor terms and the last one is $a_F$, construct a monotonic decreasing subsequence with $a_{F+1}$ as it's first term.

3). If there are no floor terms, construct a monotonic decreasing subsequence with $a_1$ as it's first term.
My answer to 1).

Since $a_n \geq a_f \ \forall \ n\geq f$ (ie. the definition of a floor term) then let $n=f+1 \Rightarrow \ a_{f+1} \geq \ a_f$

Therefore there are an infinite number of floor terms and the next floor term is greater than the previous one.

My answer to 2).

Starting once more from the definition $a_n \geq a_f \ \forall \ n \geq f$. $a_{F+1}$ is the first term and $a_F$ is the last term.

Let $n=F$ and $f=F+1$.

Therefore $a_{F} \geq a_{F+1} \ \forall \ F \ \geq F+1$

Therefore there is a monotonic decreasing subsequence as required.

(I think so anyway. Could someone double check this?)

My answer to 3).

I decided to choose $a_n=n$ since this doesn't have a lower bound. Would floor terms be in the sequence $a_f=f-1$?

Therefore making f=1:

$a_1=1-1=0$
$a_2=2-1=1$
$a_3=3-1=2$ etc

However, this doesn't create a monotonic decreasing subsequence and I can't think of a sequence that does!

Could I have some help with these "hints" so I can use them to solve the question?

Thank you kindly to anyone who posts!

2. For steps 1 and 2, perhaps you have the right intuition (I don't know), but anyway I really don't understand what you wrote. Here are a few hints to let you improve your proof (I give you the idea, I let you formalize the proofs):

A floor term $a_f$ is such that: $\forall n\geq f$, $a_n\geq a_f$. In words, it is less than or equal to any of the following terms in the sequence.

1st case: there are infinitely many floor terms. Each floor term is less than or equal to every following term, and in particular it is less than (or equal to) the following floor term. So that the floor terms form an increasing subsequence.
[To write the proof, I suggest you begin by naming the indices of the floor terms, for instance $f(k)$, $k\in\mathbb{N}^*$: $a_{f(1)}$ is the first floor term, $a_{f(2)}$ for the second one, and so on]

2st case: there are finitely many floor terms (and at least one). Let $a_F$ be the last one. Then, after $a_{F+1}$, there is no floor term.
What does it mean not to be a floor term? It means that you can find a (strictly) smaller term among the following ones.
So there is a term strictly smaller than $a_{F+1}$ (after $a_{F+1}$), and again there is a term strictly smaller than this one, and so on... This constructs a (strictly) decreasing subsequence.
[This is a construction by recursion: the first term is $a_{k(1)}=a_{F+1}$. Suppose you defined the first $m$ terms of the subsequence, say $a_{k(1)},\ldots,a_{k(m)}$ where $k(1)\leq\cdots\leq k(m)$, then define which term is $a_{k(m+1)}$]

3rd case: there is no floor term. This is no different from the 2nd case (it could be possible to gather 2nd and 3rd cases). Every term is a non-floor term, which means that there's a stricly smaller term later in the sequence. Apply this to $a_1$, then to the term smaller than $a_1$, and so on and so forth.

I hope it clarifies the way the proof works.

3. For steps 1 and 2, perhaps you have the right intuition (I don't know), but anyway I really don't understand what you wrote.
Don't worry about it. I just wrote down what I thought was right and along the way it became a whirwind of ideas!

1st case: there are infinitely many floor terms. Each floor term is less than or equal to every following term, and in particular it is less than (or equal to) the following floor term. So that the floor terms form an increasing subsequence.
[To write the proof, I suggest you begin by naming the floor terms, for instance , : for the first one, for the second one, and so on]
Right, i'll give that a go! (This will look very similar to NonnCommAlg's post):

$a_{f(1)}\ \leq \ a_{f(2)} \ \leq \ a_{f(3)} \ \leq \ .......\leq \ a_{f(n)}$

Since each floor term is less than or equal to ever following term it creates an infinite number of floor terms (written above).

2st case: there are finitely many floor terms (and at least one). Let be the last one. Then, after , there is no floor term.
What does it mean not to be a floor term? It means that you can find a (strictly) smaller term among the following ones.
So there is a term strictly smaller than (after ), and again there is a term strictly smaller than this one, and so on... This constructs a (strictly) decreasing subsequence.
[This is a construction by recursion: the first term is . Suppose you defined the first terms of the subsequence, say where , then define which term is ]
$a_F$ is the last floor term so after $a_{F+1}$ there is no floor term.

I understand this part. What about $a_{F+1}$? Is that a floor term? (I don't think it is since $a_F$ is the last one).

3rd case: there is no floor term. This is no different from the 2nd case (it could be possible to gather 2nd and 3rd cases). Every term is a non-floor term, which means that there's a strictly smaller term later in the sequence. Apply this to , then to the term smaller than , and so on and so forth.
If there's a strictly smaller term in the sequence then that means that the sequence has to be decreasing:

$a_1 \ \geq a_2 \ \geq a_3 \geq..........\geq a_n$. Is this bit right?

I think i'm understanding how the proof works:

Case 1 shows that if a sequence is increasing then it has a strictly increasing subsequence.
Case 2 shows that if a sequence is decreasing then it has a strictly decreasing subsequence.
Case 3 shows that if there are no floor terms then the sequence is also drecreasing.
Therefore, since a function can either be increasing, decreasing or constant then all sequences must have a montonic subsequence.

4. Originally Posted by Showcase_22
If there's a strictly smaller term in the sequence then that means that the sequence has to be decreasing:

$a_1 \ \geq a_2 \ \geq a_3 \geq..........\geq a_n$. Is this bit right?
There is a strictly smaller term, but it isn't necessarily the very next one: it may be way further... Let's call it $a_{k(2)}$. Then the same holds for this term (it is not a floor term either, since there is none), etc. And $a_1>a_{k(2)}>\cdots>a_{k(m)}>\cdots$.

The second case works exactly the same: there is no floor term after $a_{F+1}$ so that you can apply the same procedure.

I think i'm understanding how the proof works:

Case 1 shows that if a sequence is increasing then it has a strictly increasing subsequence.
Case 2 shows that if a sequence is decreasing then it has a strictly decreasing subsequence.
Case 3 shows that if there are no floor terms then the sequence is also drecreasing.
Therefore, since a function can either be increasing, decreasing or constant then all sequences must have a montonic subsequence.
A sequence doesn't have to be either increasing, decreasing or constant: usually, it is neither: think about $a_1>a_2$ and $a_2 for instance.

5. Originally Posted by Laurent
There is a strictly smaller term, but it isn't necessarily the very next one: it may be way further... Let's call it $a_{k(2)}$. Then the same holds for this term (it is not a floor term either, since there is none), etc. And $a_1>a_{k(2)}>\cdots>a_{k(m)}>\cdots$.

The second case works exactly the same: there is no floor term after $a_{F+1}$ so that you can apply the same procedure.
Okay then. So for infinitely many floor terms:

$a_1>a_{k(2)}>\cdots>a_{k(m)}$

This forms a strictly decreasing subsequence (since the next term along is less than the previous one).

For a finite number of floor terms:

$a_{k(F+1)}>a_{k(F)}>\cdots>a_{k(1)}$

And since there are no floor terms after $a_{k(F+1)}$ then the sequence is finite (since F is the last floor term).

A sequence doesn't have to be either increasing, decreasing or constant: usually, it is neither: think about $a_1>a_2$ and $a_2 for instance.
I never thought of that. I'm having trouble seeing how this proof works. Is it that every sequence has a relationship with it's floor terms (for example, they either exist and there are infinitely many of them or finitely many of them or they don't exist at all). Either way, we're trying to show that regardless of how many floor terms exist they can form a subsequence. I'm still a bit shaky on what a sequence would look like if it had infintely many floor terms, finitely many and none at all.

$(a_n)^\infty_{n=1}=n$ would have infinitely many floor terms since you could take $(a_n)^\infty_{n=1}=n-1$ as s subsequence and all the terms would be less than the terms in $(a_n)^\infty_{n=1}=n$ ie. $
\forall n\geq f
$
, $
a_n\geq a_f
$
.

A sequence that would have a finite number of floor terms would be 5,4,3,2,1,0,0,0,0,0. The subsequence could be 4,3,2,0,0. $a_{f}$ (ie. the final floor term would be 0) and the subsequence has 5 floor terms so it is finite.

A sequence that doesn't have any floor terms is 1,2,1,2,1,2....
I could make the subsequence 2,2,2..... and this wouldn't satisfy the definition of a floor term (since 2>1) so the sequence doesn't have any.
However, I could just take the subsequence as 1,1,1,1,1..... and so it does have floor terms (infinitely many of). =S

6. Originally Posted by Showcase_22
A sequence that would have a finite number of floor terms would be 5,4,3,2,1,0,0,0,0,0. The subsequence could be 4,3,2,0,0. $a_{f}$ (ie. the final floor term would be 0) and the subsequence has 5 floor terms so it is finite.

A sequence that doesn't have any floor terms is 1,2,1,2,1,2....
I could make the subsequence 2,2,2..... and this wouldn't satisfy the definition of a floor term (since 2>1) so the sequence doesn't have any.
About your examples: by your definition, a floor term is such that it is less than or equal to the following terms. So that in a constant sequence every term is a floor term, and both of your examples have infinitely many floor terms.

An example without any floor term could be a decreasing non-stationnary sequence (or a strictly decreasing sequence).

An example with finitely many floor terms, and at least one, could be: 0, 1, 1/2, 1/3, 1/4, 1/5, ... : 0 is a floor term, and this is the only one.

7. aha!

I understand what you've written there but I can't see how this would help in the proof.

The hints show that a sequence can either have no, a finite number or an infinite number of floor terms. Since each of these forms a subsequence then every sequence has a monotonic subsequence.

8. I think you have all the ingredients now, haven't you?

I add something about your last post (don't feel humiliated if this is obvious to you, it would just mean that I misinterpreted something you wrote): by definition, a subsequence is a sequence, hence it always has infinitely many terms. So that a finite sequence of floor terms does not answer the question.

As a summary:
For any sequence, clearly, one of the cases 1), 2) or 3) happens. We construct different subsequences depending on the case.
In case 1), the monotonic subsequence is just the subsequence of floor terms (there are infinitely many, so this indeed is a subsequence).
In case 3), every term is a non-floor term, so that it is possible to recursively construct a strictly decreasing sequence, starting at $a_1$ (any other term would have done the work), choosing a strictly lower term among the following terms, then a strictly lower term than the previous one among the following terms, etc. The existence of these strictly lower terms follows from a litteral interpretation of the "non-floority" of the terms.
In case 2), there are a few floor terms we don't care about, and we construct a strictly decreasing subsequence exactly like in case 3) among the non-floor terms that come after the finite number of floor terms: the first term must be chosen strictly after $a_F$, for instance $a_{F+1}$ (then every following term is a non-floor term and the situation matches that of case 3)).

9. Prove that every sequence has a monotonic subsequence.
(This is a Donald Newman proof).

Let $a_k$ be a term in a sequence. We call $a_k$ Hackerian iff $a_k > a_j$ for all $j>k$. There are two possibilities: (i) there are infinitely many Hackerian terms (ii) there are finitely many Hackerian terms. If (i) holds then choosing all the Hackerian terms we have formed a monotonic subsequence. If (ii) holds let $a_{n_1}$ be any term past the Hackerian terms, since $a_{n_1}$ is not Hackerian there is $a_{n_2}$ with $a_{n_1} \leq a_{n_2}$ (and $n_2 > n_1$) continuing again there is $a_{n_3}$ with $a_{n_2} \leq a_{n_3}$ and this process continues until we form $a_{n_1},a_{n_2}, a_{n_3},...$.

10. Originally Posted by ThePerfectHacker
(This is a Donald Newman proof).

Let $a_k$ be a term in a sequence. We call $a_k$ Hackerian iff $a_k > a_j$ for all $j>k$. There are two possibilities: (i) there are infinitely many Hackerian terms (ii) there are finitely many Hackerian terms. If (i) holds then choosing all the Hackerian terms we have formed a monotonic subsequence. If (ii) holds let $a_{n_1}$ be any term past the Hackerian terms, since $a_{n_1}$ is not Hackerian there is $a_{n_2}$ with $a_{n_1} \leq a_{n_2}$ (and $n_2 > n_1$) continuing again there is $a_{n_3}$ with $a_{n_2} \leq a_{n_3}$ and this process continues until we form $a_{n_1},a_{n_2}, a_{n_3},...$.
Actually this is almost the same proof, with "Hackerian terms" (in other words "strictly ceiling terms") playing the same role as the "floor terms" in the suggested proof (with $>$ instead of $\leq$ and hence "strictly increasing" instead of "decreasing", and conversely, and so on). This short formulation may help to understand the proof anyway, I admit.