Page 1 of 2 12 LastLast
Results 1 to 15 of 18

Math Help - induction problem on set of positive numbers

  1. #1
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    induction problem on set of positive numbers

    hi

    Here is a problem I am trying to do from Kenneth Rosen's
    "Discrete mathematics..."

    Use mathematical 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.

    Now I checked the base case for n=1. The problem also
    assumes that there might be integers which repeat among these
    n+1 integers. So, for n=1 all the following
    sets need to be considered.

    \{1,1\},\{1,2\},\{2,2\}

    So we can establish that base case P(1) holds.

    Now let P(n) be the proposition 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.

    For the induction case, let n\geqslant 1 be arbitrary
    and also assume P(n).To prove
    P(n+1) we assume that there is a set with
    n+2 positive integers, none exceeding
    2(n+1)=2n+2.

    Lets call this set A.

    \because n\geqslant 1\;\therefore n+2\geqslant 3

    So there are at least 3 elements in A.
    Let m be the maximum element of set A.
    Now I am considering three cases here.

    Case 1)

    m\leqslant 2n

    here we can define a new set

    A_1=A\setminus \{m\}

    now all the elements in A_1 do not exceed
    2n and also A_1 has n+1
    elements and I can now use inductive hypothesis here.

    Case 2)

    m\leqslant 2n+1

    Again, we can define a new set

    A_1=A\setminus \{m\}

    now all the elements in A_1 do not exceed
    2n and also A_1 has n+1
    elements and I can now use inductive hypothesis here.

    Case 3)

    m\leqslant 2n+2

    Now here I see problem. There could be a case where both
    2n+1 and 2n+2 are in A. So even after removing
    m, we can have a set where 2n+1 is still in the set. And
    we can't use the inductive hypothesis here. How do I handle this case ?

    Thanks

    \smile
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: induction problem on set of positive numbers

    well, one thing is to see that we don't lose any generality by assuming the numbers are distinct. why? becuase if two numbers are the same, say k is the repeated element, then k|k.

    now, consider A - {2n+1,2n+2}. we can apply the induction hypothesis to that set. and if we have a divisible pair in that set, we have a divisible pair in A.

    but....for this to be "legal", we must check an additional base case: n = 2.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    Re: induction problem on set of positive numbers

    hi Deveno

    Here I outline the whole solution as deviced by me.
    I have already proven this for n=1. Now let n=2.
    Now I am assuming all the elements are distinct. So
    the possible sets are

    \{1,2,3\},\{2,3,4\},\{1,2,4\},\{1,3,4\}

    As we can see in every set there is at least one integer
    which divides another integer. So P(2).Now we to the
    induction case.

    To prove P(n+1), we assume that there is a set of
    n+2 positive integers, none exceeding
    2(n+1)=2n+2. Lets call this set A.
    Let m be the maximum of A. Also we assume the
    inductive hypothesis P(n) and let n\geqslant 2
    be arbitrary.
    I am assuming that all elements of A are distinct ...

    Case 1: m\leqslant 2n

    define new set B=A\setminus \{m\}

    So B has n+1 positive numbers and
    none exceed 2n. Using P(n) ,
    there is at least one integer in this set
    that divides another integer in the set.
    Since

    A=B\cup \{m\}

    there is at least one integer in A that divides
    another integer in A. Hence P(n+1).

    Case 2: m=2n+1

    define new set B=A\setminus \{m\}

    So B has n+1 positive numbers and
    none exceed 2n. Using P(n) ,
    there is at least one integer in this set
    that divides another integer in the set.
    Since

    A=B\cup \{m\}

    there is at least one integer in A that divides
    another integer in A. Hence P(n+1).

    Case 3: m=2n+2

    here we have two possibilities,

    2n+1 \notin A

    2n+1 \in A

    in the first case, define new set

    B=A\setminus \{m\}

    So B has n+1 positive numbers and
    none exceed 2n. Using P(n) ,
    there is at least one integer in this set
    that divides another integer in the set.
    Since

    A=B\cup \{m\}

    there is at least one integer in A that divides
    another integer in A. Hence P(n+1).

    in the second case, define new set

    B=A\setminus\{2n+1,m\}

    also define a set

    C=\{1,2,\cdots,2n\}\setminus B

    Now B has n elements and

    \because n\geqslant 2\;\therefore \forall n\geqslant 2\; C\neq \varnothing

    So we can choose an element in C, say 'a'. By the construction of
    C, 'a' doesn not exceed 2n. Define new set

    G=B\cup\{a\}

    so G has n+1 elements, none of which exceed 2n.
    Using P(n), there is at least one integer in this set
    that divides another integer in the set.
    Let

    K=G\cup \{m\}

    there is at least one integer in this set
    that divides another integer in the set.. also
    K has n+2 elements , none of which
    exceed 2n+2 . Hence P(n+1).

    Since all cases are exhausted , so P(n+1).

    Is it correct reasoning ?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780

    Re: induction problem on set of positive numbers

    Quote Originally Posted by Deveno View Post
    now, consider A - {2n+1,2n+2}. we can apply the induction hypothesis to that set. and if we have a divisible pair in that set, we have a divisible pair in A.
    But if 2n + 1, 2n + 2 ∈ A, then |A - {2n + 1, 2n + 2}| = n, so the induction hypothesis cannot be used (it applies to sets of size n + 1).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780

    Re: induction problem on set of positive numbers

    Quote Originally Posted by issacnewton View Post
    Let

    K=G\cup \{m\}

    there is at least one integer in this set
    that divides another integer in the set.. also
    K has n+2 elements , none of which
    exceed 2n+2 . Hence P(n+1).
    You had to prove that A has an integer that divides another, and you instead constructed a new set K.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    Re: induction problem on set of positive numbers

    Oh I see , any set which has the property of A or K should have at least one integer in set that divides another integer in the set...

    But am I close to the solution or far away ?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780

    Re: induction problem on set of positive numbers

    Quote Originally Posted by issacnewton View Post
    But am I close to the solution or far away ?
    To be honest, I don't know how to prove this at this time. Obviously, the difficult case in the induction step is when both 2n + 1 and 2n + 2 (the maximum) are in A where |A| = n + 2. Maybe somebody else can help.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: induction problem on set of positive numbers

    Quote Originally Posted by emakarov View Post
    But if 2n + 1, 2n + 2 ∈ A, then |A - {2n + 1, 2n + 2}| = n, so the induction hypothesis cannot be used (it applies to sets of size n + 1).
    1) one could use strong induction, instead.

    2) if we have proved two base cases, we are free to use the n AND n-1 cases (sets of size n+1, and sets of size n).

    here is how it works:

    true for 1, true for 2.

    true for 3 if true for 2 or true for 1, thus true.

    true for 4 if true for 3 or true for 2, thus true.

    and so on......

    3) do two separate cases: n even, n = 2k, or n odd, n = 2k-1, and use induction on k (twice)

    all of these are valid methods.....
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780

    Re: induction problem on set of positive numbers

    Quote Originally Posted by emakarov View Post
    But if 2n + 1, 2n + 2 ∈ A, then |A - {2n + 1, 2n + 2}| = n, so the induction hypothesis cannot be used (it applies to sets of size n + 1).
    Quote Originally Posted by Deveno View Post
    1) one could use strong induction, instead.
    The induction hypothesis can't be used not because the size of the set is 2 (not 1) less than the size in the conclusion of the induction step, but because |A - {2n + 1, 2n + 2}| = n, but you can only guarantee that max(A - {2n + 1, 2n + 2}) <= 2n. To remind, the induction statement P(n) is

    For any set A of positive integers such that |A| = n + 1 and max(A) <= 2n, one element of A divides another.

    There are not enough elements in A - {2n + 1, 2n + 2} to invoke the induction hypothesis.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: induction problem on set of positive numbers

    one can do an induction argument where you "go up by twos" as long as you prove 2 "base cases". you should convince yourself that this is so, i'm not just making it up. a schema for this would look something like:

    if [P(0) & P(1)] & [(P(k-1) v P(k))-->P(k+1)] then P(n) for all n.

    this is just a limited form of strong induction, except we only rely on one of the last two cases to be true, instead of all previous cases. do you doubt that strong induction is a valid form of inductive proof?

    EDIT: oh, i see what you are saying...if we take two elements out of A, then P(n-1) requires all the numbers to be less than or equal to 2n-2, and we might still have 2n-1 and 2n in our set.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    Re: induction problem on set of positive numbers

    Quote Originally Posted by Deveno View Post

    if [P(0) & P(1)] & [(P(k-1) \wedge P(k))-->P(k+1)] then P(n) for all n.

    this is just a limited form of strong induction, except we only rely on one of the last two cases to be true, instead of all previous cases. do you doubt that strong induction is a valid form of inductive proof?
    it should be like this
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    Re: induction problem on set of positive numbers

    Hello

    Let me try to prove what Deveno is saying.....

    Theorem:Show that the following form of mathematical induction
    is a valid method to prove that P(n) is true for all positive integers
    n.

    Basis Step: P(1),P(2) are true
    Inductive Step: For each positive integer k
    if P(k) and P(k+1) both are true then  P(k+2) is true.

    Proof: Suppose that a statement \forall n P(n) has been proved
    by this method.Let S be the set of counterexamples to P. So let

     S=\{n\lvert \;\neg P(n)\}

    We will show that S=\varnothing. If S\neq \varnothing , then
    let n be the minimum element of S (which exists by the well-ordering property).
    Clearly n\neq 1, n\neq 2 , by the base cases of our proof method.
    So n\geqslant 3. Since n is the least element of S, we know that
    P(n-1),P(n-2) are true. Therefore by inductive step of our proof method, we know
    that P(n) is also true. This contradicts the choice of n.
    Therefore S=\varnothing as desired.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780

    Re: induction problem on set of positive numbers

    Quote Originally Posted by issacnewton View Post
    Let me try to prove what Deveno is saying.....
    That's correct. Note that the well-ordering property is just the contrapositive of strong induction. The fact in the previous post can also be proved by regular induction using Q(n) = P(n) /\ P(n + 1). Similarly, strong induction can be proved using regular one where Q(n) is "for all k < n, P(n)". But if this topic needs further discussion, it's better to start a new thread.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780

    Re: induction problem on set of positive numbers

    OK, I got it. So, the difficult case is when 2n + 1, 2n + 2 ∈ A and |A| = n + 2. We have the induction hypothesis:

    for any set B of positive integers such that |B| = n + 1 and max(B) <= 2n, one element of B divides another.

    Hint: consider A ∪ {n + 1} - {2n + 1, 2n + 2}.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    Re: induction problem on set of positive numbers

    makarov you beat me. I had already solved the problem using that line of
    thought. here's the solution


    I think I have found the solution. Lets hope its right this
    time. The only case where I got stuck was the case where
    set A had both 2n+1 and 2n+2. We have to
    prove that there is at least one integer in A which divides
    another integer. I am going to try proof by contradiction.
    So assume that there is no pair of integers in A such that
    one divides the other.

    \because (n+1)\lvert (2n+2)\therefore (n+1)\notin A


    Now define the set B as

    B=A\setminus \{2n+1,2n+2\}

    also define the set C as

    C=B\cup \{n+1\}

    \because n\geqslant 1\therefore n+1\leqslant 2n

    So, C has n+1 positive integers and none exceed
    2n. We can use inductive hypothesis on C and
    conclude that there is at least one integer in C which
    divides another. By assumption, there is no such pair
    of integers among the elements of B. So it must be true that
    either n+1 divides another integer in C or
    some another integer divides n+1.

    Case 1: some another interger in C divides n+1.

    Let's call this integer, k.

    \because (n+1)\lvert (2n+2)\therefore k\lvert (2n+2)

    So, there is a pair of integers in A so that one divides another.
    A contradiction.

    Case 2: n+1 divides another integer in C.

    Let's call this another integer in C , k. Since k is different from
    n+1 , k\in A

    \because (n+1)\lvert k\;\therefore (n+1)j=k\quad j\geqslant 1

    If j=1 then n+1 \in A which is contradiction.

    If j>1\;\;\Rightarrow k\geqslant (2n+2)

    which is a contradiction since k doesn't exceed 2n.


    Since the cases are exhausted, original assumption is incorrect. Hence
    A has at least one interger which divides another.Hence
    P(n+1).

    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: November 24th 2011, 04:05 PM
  2. [SOLVED] induction problem with fibonacci numbers
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 5th 2011, 09:00 PM
  3. Prove positive real numbers a,b,c.
    Posted in the Algebra Forum
    Replies: 31
    Last Post: August 7th 2011, 03:04 PM
  4. Positive Real Numbers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 30th 2011, 04:36 AM
  5. Let x and y be positive real numbers...
    Posted in the Algebra Forum
    Replies: 2
    Last Post: October 26th 2008, 06:09 AM

/mathhelpforum @mathhelpforum