Results 1 to 10 of 10

Math Help - monotonic subsequences.

  1. #1
    Super Member Showcase_22's Avatar
    Joined
    Sep 2006
    From
    The raggedy edge.
    Posts
    782

    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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    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.
    Last edited by Laurent; October 14th 2008 at 02:33 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member Showcase_22's Avatar
    Joined
    Sep 2006
    From
    The raggedy edge.
    Posts
    782
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    Quote Originally Posted by Showcase_22 View Post
    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<a_3 for instance.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member Showcase_22's Avatar
    Joined
    Sep 2006
    From
    The raggedy edge.
    Posts
    782
    Quote Originally Posted by Laurent View Post
    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<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.

    (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. <br />
\forall n\geq f<br />
, <br />
a_n\geq a_f<br />
.

    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

    Am I thinking about this correctly?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    Quote Originally Posted by Showcase_22 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member Showcase_22's Avatar
    Joined
    Sep 2006
    From
    The raggedy edge.
    Posts
    782
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    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)).
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    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},....
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    Quote Originally Posted by ThePerfectHacker View Post
    (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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Subsequences
    Posted in the Differential Geometry Forum
    Replies: 6
    Last Post: June 28th 2011, 05:41 PM
  2. Subsequences
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: February 17th 2010, 07:59 PM
  3. subsequences
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: January 14th 2010, 02:05 AM
  4. subsequences in R^n
    Posted in the Calculus Forum
    Replies: 1
    Last Post: October 22nd 2008, 08:09 PM
  5. subsequences
    Posted in the Calculus Forum
    Replies: 1
    Last Post: October 10th 2008, 10:17 AM

Search Tags


/mathhelpforum @mathhelpforum