Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

DISCRETE MATH: Use math. induction to show that at least 1 integer can divide another

  1. Feb 21, 2007 #1
    1. The problem statement, all variables and given/known data

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

    2. Relevant equations

    Mathematical induction, others, I am not sure

    3. The attempt at a solution

    Let [itex]P(n)[/itex] be the claim that there will be two integers [itex](x,\,y)[/itex] such that y divides x.

    [tex]\left{1,\,2,\,\dots,\,2\,n\right}[/tex] <----- Choose only [itex]n\,+\,1[/itex] of these.

    Basis: Does [itex]P(1)[/itex] hold?

    [tex]\left{1,\,\dots,\,2\,n\right}\,=\,\left{1,\,2\right}[/tex] <----- for [itex]n\,=\,1[/itex]

    2 is divisible by 1, so x = 2 and y = 1. [itex]P(1)[/itex] is true.

    Inductive hypothesis:

    [tex]\left{1,\,2,\,\dots,\,2\,n,\,2\,n\,+\,1,\,2\,n\,+\,2\right}[/tex] <----- Choose only [itex]n\,+\,2[/itex] of these

    How do I prove that though?
  2. jcsd
  3. Feb 22, 2007 #2


    User Avatar
    Science Advisor
    Homework Helper

    Here's the start of a proof...

    Let m be the largest integer in the set of n+1 integers.

    If m <= 2(n-1), there are n integers in the set less than 2(n-1) , so by induction P(n) is true.

    Now think about the cases where m = 2n-1 or m = 2n.
  4. Feb 22, 2007 #3


    User Avatar
    Science Advisor

    By the way- there is no requirement that the n integers be distinct. In the n= 1 case, the two integers may be {1, 2}, {1, 1} or {2,2}. Of course, if they are NOT distinct, then obviously one of the duplicates divides the other so you really only need to consider the case that they are distinct- but you should say that.
  5. Sep 28, 2010 #4
    Re: DISCRETE MATH: Use math. induction to show that at least 1 integer can divide ano

    Resurrecting old thread, I also really need help with this problem. I'm completely lost, I couldn't even come with what the OP got on my own.

    Thanks anyway
  6. Feb 19, 2012 #5
    Re: DISCRETE MATH: Use math. induction to show that at least 1 integer can divide ano

    I believe there is that requirement, as the claim states that it is a set of positive integers. Sets contain unique elements.

    Since Induction in general was part of your question, I would recommend looking at inductiveproofs.com -- they have a nice template for writing inductive proofs that you might find helpful.

    Does the question hint at using weak or strong induction? (if you haven't heard of strong induction yet, that is helpful :) since we know it should use weak then!) The thing to think about is how can we get back to the smaller subset? AKA In the inductive step, we have a set of n+2 elements, all no higher than 2n+2, how do we talk about a subset of n+1 elements all no higher than 2n? What do we know about the other sets that don't contain that subset?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook