Results 1 to 2 of 2

Math Help - Induction

  1. #1
    Junior Member
    Joined
    Nov 2006
    Posts
    43
    Thanks
    1

    Induction

    Hi! I have an induction question as follows:

    Use induction to show that given a set of n+1 positive integers, none exceeding 2n, there is at least one integer in this set that divides another integer in the set.

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member TriKri's Avatar
    Joined
    Nov 2006
    Posts
    358
    Thanks
    1
    Quote Originally Posted by feiyingx View Post
    Hi! I have an induction question as follows:

    Use induction to show that given a set of n+1 positive integers, none exceeding 2n, there is at least one integer in this set that divides another integer in the set.

    Thanks!
    Start with filling the set from n+1 to 2n. There is no free number within the interval that you can choose cause it will divide the nunber that is twise as large, and you have only chosen n numbers.

    Now, we can prove that for any set of n positive integer numbers <= 2n, where no of the numbers divides any other, and no more number can be added cause it will divide another of the numbers or be divided itself, it is impossible to change the value of one of the numbers making one place in the interval free to place yet another number in. And...

    Or something like that, just continue on and I'm sure you will solve it
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Strong induction vs. structural induction?
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: April 21st 2011, 12:36 AM
  2. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  3. induction help
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: April 19th 2010, 05:39 AM
  4. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  5. Induction!
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 7th 2008, 04:10 PM

Search Tags


/mathhelpforum @mathhelpforum