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 $\displaystyle a_F$, construct a monotonic decreasing subsequence with $\displaystyle a_{F+1}$ as it's first term.

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

Since $\displaystyle a_n \geq a_f \ \forall \ n\geq f$ (ie. the definition of a floor term) then let $\displaystyle 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.

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

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

Therefore $\displaystyle 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?)

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

Therefore making f=1:

$\displaystyle a_1=1-1=0$
$\displaystyle a_2=2-1=1$
$\displaystyle 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 $\displaystyle a_f$ is such that: $\displaystyle \forall n\geq f$, $\displaystyle 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 $\displaystyle f(k)$, $\displaystyle k\in\mathbb{N}^*$: $\displaystyle a_{f(1)}$ is the first floor term, $\displaystyle a_{f(2)}$ for the second one, and so on]

2st case: there are finitely many floor terms (and at least one). Let $\displaystyle a_F$ be the last one. Then, after $\displaystyle 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 $\displaystyle a_{F+1}$ (after $\displaystyle 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 $\displaystyle a_{k(1)}=a_{F+1}$. Suppose you defined the first $\displaystyle m$ terms of the subsequence, say $\displaystyle a_{k(1)},\ldots,a_{k(m)}$ where $\displaystyle k(1)\leq\cdots\leq k(m)$, then define which term is $\displaystyle 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 $\displaystyle a_1$, then to the term smaller than $\displaystyle 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):

$\displaystyle 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 ]
$\displaystyle a_F$ is the last floor term so after $\displaystyle a_{F+1}$ there is no floor term.

I understand this part. What about $\displaystyle a_{F+1}$? Is that a floor term? (I don't think it is since $\displaystyle 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:

$\displaystyle 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:

$\displaystyle 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 $\displaystyle a_{k(2)}$. Then the same holds for this term (it is not a floor term either, since there is none), etc. And $\displaystyle a_1>a_{k(2)}>\cdots>a_{k(m)}>\cdots$.

The second case works exactly the same: there is no floor term after $\displaystyle 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 $\displaystyle a_1>a_2$ and $\displaystyle a_2<a_3$ 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 $\displaystyle a_{k(2)}$. Then the same holds for this term (it is not a floor term either, since there is none), etc. And $\displaystyle a_1>a_{k(2)}>\cdots>a_{k(m)}>\cdots$.

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

$\displaystyle 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:

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

And since there are no floor terms after $\displaystyle 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 $\displaystyle a_1>a_2$ and $\displaystyle a_2<a_3$ 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.

$\displaystyle (a_n)^\infty_{n=1}=n$ would have infinitely many floor terms since you could take $\displaystyle (a_n)^\infty_{n=1}=n-1$ as s subsequence and all the terms would be less than the terms in $\displaystyle (a_n)^\infty_{n=1}=n$ ie. $\displaystyle \forall n\geq f$,$\displaystyle 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. $\displaystyle 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. $\displaystyle 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 $\displaystyle 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 $\displaystyle a_F$, for instance $\displaystyle 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 $\displaystyle a_k$ be a term in a sequence. We call $\displaystyle a_k$ Hackerian iff $\displaystyle a_k > a_j$ for all $\displaystyle 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 $\displaystyle a_{n_1}$ be any term past the Hackerian terms, since $\displaystyle a_{n_1}$ is not Hackerian there is $\displaystyle a_{n_2}$ with $\displaystyle a_{n_1} \leq a_{n_2}$ (and $\displaystyle n_2 > n_1$) continuing again there is $\displaystyle a_{n_3}$ with $\displaystyle a_{n_2} \leq a_{n_3}$ and this process continues until we form $\displaystyle a_{n_1},a_{n_2}, a_{n_3},...$.

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

Let $\displaystyle a_k$ be a term in a sequence. We call $\displaystyle a_k$ Hackerian iff $\displaystyle a_k > a_j$ for all $\displaystyle 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 $\displaystyle a_{n_1}$ be any term past the Hackerian terms, since $\displaystyle a_{n_1}$ is not Hackerian there is $\displaystyle a_{n_2}$ with $\displaystyle a_{n_1} \leq a_{n_2}$ (and $\displaystyle n_2 > n_1$) continuing again there is $\displaystyle a_{n_3}$ with $\displaystyle a_{n_2} \leq a_{n_3}$ and this process continues until we form $\displaystyle 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 $\displaystyle >$ instead of $\displaystyle \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.