1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Induction proof

  1. Dec 26, 2007 #1
    [SOLVED] induction proof

    1. The problem statement, all variables and given/known data
    Given a set of n+1 integers between 1 and 2n (inclusive), show that at least one member of the set must divide another member of the set.
    Use induction.

    2. Relevant equations



    3. The attempt at a solution
    When n=1, this is obvious.
    Assume the result is true for n=k. Now we have a set of k+2 integers between 1 and 2k+2 and we want to show that one member divides another. If 2k+2 or 2k+1 is NOT in our set, then we have k+1 integers between 1 and 2k, and we apply the induction hypothesis. I am having trouble with the case where 2k+2 and 2k+1 are both in the set. If 1, 2 or k+1 is also in our set we are done. If not, we have k-1 integers in {3,4,...,k} union {k+2,...,2k}, and I am unsure where the induction hypothesis comes in.
     
  2. jcsd
  3. Dec 28, 2007 #2
    Look what you have left when you take out 2k+1 and 2k+2.
     
  4. Dec 28, 2007 #3
    Better check for n=2.
     
  5. Dec 28, 2007 #4

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    That is the only case you need to trouble yourself with. Assume that the conjecture is true for n=1,...,k but false for n=k+1, and get a contradiction. If the conjecture is true for n=k, then there at most k integers in {1,2k} that are all relatively prime with respect to each other. To disprove the conjecture for n=k+1, you will need those k integers plus two more, or 2k+1 and 2k+2.

    He has to find 3 integers in {1,2,3,4}, none of which divides the other. One is obviously out, leaving {2,3,4}, and 2 divides 4.
     
  6. Dec 28, 2007 #5
    Two numbers being relatively prime and two numbers having the property that neither is divisible by the other is not the same thing. The former implies the latter, but the latter does not imply the former.

    For example, 8 does not divide 6 and 6 does not divide 8, but 6 and 8 are not relatively prime.
     
    Last edited: Dec 28, 2007
  7. Dec 28, 2007 #6
    Yes. 1 divides every integer.
     
  8. Dec 28, 2007 #7

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Sorry, I used the wrong term. My logic still stands. You need 2k+1 and 2k+2 in your set of k+2 numbers, none of which divides another, to falsify the conjecture for n=k+1.
     
  9. Dec 28, 2007 #8
    I do not see why you're logic still stands.

    There at most k integers in {1,2k} that have the property that none divides another. Because I just showed that relative primeness is more general than that, there could be more than k integers that are relatively prime.
     
  10. Dec 28, 2007 #9

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    ARGGHH. I said "I used the wrong term". How does the term "set of mutually non-dividing integers" suit you? Rather than edit my old post, here is the correction:

    This is the only case you need to trouble yourself with. Assume that the conjecture is true for n=1,...,k but false for n=k+1, and get a contradiction. If the conjecture is true for n=k, then there at most k integers in {1,2k} none of which divides another. To disprove the conjecture for n=k+1, you will need k+2 mutually non-dividing integers, or those k integers for n=k plus two more. The only two that are available are 2k+1 and 2k+2.

    Note that if the largest subset of mutually non-dividing integers of the set {1,2k} is fewer than k elements the conjecture must hold for n=k+1.
     
  11. Dec 28, 2007 #10
    I am sorry, I still don't see where the contradiction is. I agree that

    "there at most k integers in {1,2k} none of which divides another"

    and that

    "To disprove the conjecture for n=k+1, you will need k+2 mutually non-dividing integers, or those k integers for n=k plus two more. The only two that are available are 2k+1 and 2k+2."

    But there could be a set S of EXACTLY k integers in {1,2k} none of which divides another. Then when you add 2k+1 and 2k+2 to S, you MIGHT get k+2 mutually non-dividing integers in {1,2k+2}.
    I think we need to show that either 2 or k+1 must be in S.
     
  12. Dec 28, 2007 #11

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    I am not doing your homework for you, just giving you hints. I did not say their is a contradiction; I said you need to establish a contradiction. I left that act of establishing the contradiction as an exercise for you to complete.
     
  13. Dec 28, 2007 #12

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    For k=7, the set S={4,5,6,7,9,11,13} has 7 members and contains neither 2 nor 8. The existence of 4 in the set does get rid of the 16 for k=8).
    For k=11, there are several sets S with 11 members that do not contain 2 or 11. They do contain 4 or 6 (or both).
     
  14. Dec 28, 2007 #13
    My idea is this:

    We want to show that a (k+1) element subset S of {1,2,...,2k+2} cannot be mutually nondividing. We reduced the problem to the case where S contains 2k+1 and 2k+2. I think we want to show that if 1, 2, or k+1 are not in S then, there must be x,y in {3,4,...,k} union {k+2,...,2k} and in S such that x divides y. That is what I am having so much trouble trying to prove!

    Note that the last sentence in my original post is wrong: "we have k-1 integers" should be "we have k integers".

    Note also that this problem is driving me INSANE.
     
  15. Dec 28, 2007 #14
    What you have left in your set is k integers in {1,...,2k}. What do you do with that information?
    By the strong induction hypothesis, we know that any set of k+1 elements in {1,...,2k} is not mutually non-dividing. But we only have k elements in this set!
     
    Last edited: Dec 28, 2007
  16. Dec 28, 2007 #15

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    So with all you done so far, you have k numbers in 1...2k which are mutually nondividing (call this set K), since KU{2k+1,2k+2} is mutually nondividing, right? You've already observed that k+1 is not in K. If you form the set KU{k+1} then your induction hypothesis says that it IS mutually dividing. Therefore either a number in K divides k+1 or k+1 divides a number in K. Which is it? Now finish the problem.
     
  17. Dec 28, 2007 #16
    AHA. How could I miss that?

    k+1 does not divide anything less than or equal to 2k, so there exists x in K such that x divides k+1. But then x divides 2k+2 which contradicts the fact that K union {2k+1,2k+2} is mutually non-dividing.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Induction proof
  1. Proof by induction (Replies: 2)

  2. Proof by induction (Replies: 9)

  3. Proof by induction (Replies: 32)

  4. Induction Proof (Replies: 14)

  5. Proof by Induction (Replies: 6)

Loading...