Results 1 to 2 of 2

Math Help - Induction Proofs for Sequences

  1. #1
    Newbie
    Joined
    Apr 2008
    Posts
    1

    Exclamation Induction Proofs for Sequences

    Here's the problem I have to prove:
    Every sequence in a totally ordered set has a monotonic subsequence.
    We have to use induction to prove this statement, but I am not too good and writing induction proofs as I don't know how to start them and what to put in my induction hypothesis. Any suggestions would be appreciated! Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by beachbum87 View Post
    Here's the problem I have to prove:
    Every sequence in a totally ordered set has a monotonic subsequence.
    We have to use induction to prove this statement, but I am not too good and writing induction proofs as I don't know how to start them and what to put in my induction hypothesis. Any suggestions would be appreciated! Thanks
    Here is how Donald Newman would prove it.

    Let \{ a_n\} be a sequence in a totally ordered set A. Define a_m to be dominant if a_m > a_k for all k>m.

    Case 1: There are infinitely many dominant terms. Then choose a_{n_1},a_{n_2}, ... to be dominant terms, in increasing substrict order as you go along the sequence. Then a_{n_1} > a_{n_2} > ... is a monotone subsequence.

    Case 2: There are finitely many dominant terms. Let N be larger of all indexes of the dominant terms, i.e. if n\geq N then a_n is not dominant. Pick a_N, this is not dominant so there is n_2 so that a_{n_2}\geq a_N. But a_{n_2} is not dominant so pick n_3 so that a_{n_3}\geq a_{n_2}. And so on. Thus, \left< a_N, a_{n_2}, a_{n_3}, ... \right> is a monotone subsequence.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proofs by Induction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 30th 2010, 10:11 AM
  2. Induction proofs
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: October 14th 2009, 08:32 PM
  3. proofs by induction
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: September 28th 2009, 05:29 AM
  4. Sequences and proofs
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: May 20th 2009, 03:28 PM
  5. proofs by induction
    Posted in the Algebra Forum
    Replies: 7
    Last Post: September 25th 2007, 04:14 AM

Search Tags


/mathhelpforum @mathhelpforum