Results 1 to 5 of 5

Math Help - Mathematical Induction

  1. #1
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    244

    Mathematical Induction

    Can anyone verify whether the following proof is correct or incorrect? If incorrect please explain where and why I went wrong?

    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.

    S = { x_i such that i = 1,2,...,n+1, x_i \le 2n}

    Show that \exists x_i such that x_i | x_j i \not= j

    Basis Step: P(1): case 1: S={1,2} 1 | 2 so P(1) is true
    case 2: S={1,1} 1 | 1 so P(1) is true

    Inductive Step: P(k) \Rightarrow P(k+1)

    Given S = { x_i such that i = 1,2,...,k+1, x_i \le 2k}
    \exists x_i such that x_i | x_j i \not= j

    Prove that \exists x_s such that x_s | x_t, s \not= t
    where x_s \epsilon { x_i such that i = 1,2,...,k+1,(k+1)+1 x_i \le 2(k+1)}

    Note that { x_i such that i = 1,2,...,k+1,(k+1)+1 x_i \le 2(k+1)} = S \cup { x_i such that i = (k+1)+1 x_i \le 2(k+1)}

    Choose x_s = x_i that divides x_j and x_t = x_j from the given part.

    This proves P(k+1) is true, so the original statement is true by M.I.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member Focus's Avatar
    Joined
    Aug 2009
    Posts
    228
    Quote Originally Posted by oldguynewstudent View Post
    Can anyone verify whether the following proof is correct or incorrect? If incorrect please explain where and why I went wrong?

    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.

    S = { x_i such that i = 1,2,...,n+1, x_i \le 2n}

    Show that \exists x_i such that x_i | x_j i \not= j

    Basis Step: P(1): case 1: S={1,2} 1 | 2 so P(1) is true
    case 2: S={1,1} 1 | 1 so P(1) is true

    Inductive Step: P(k) \Rightarrow P(k+1)

    Given S = { x_i such that i = 1,2,...,k+1, x_i \le 2k}
    \exists x_i such that x_i | x_j i \not= j

    Prove that \exists x_s such that x_s | x_t, s \not= t
    where x_s \epsilon { x_i such that i = 1,2,...,k+1,(k+1)+1 x_i \le 2(k+1)}

    Note that { x_i such that i = 1,2,...,k+1,(k+1)+1 x_i \le 2(k+1)} = S \cup { x_i such that i = (k+1)+1 x_i \le 2(k+1)}

    Choose x_s = x_i that divides x_j and x_t = x_j from the given part.


    This proves P(k+1) is true, so the original statement is true by M.I.
    It is not wrong per say, but the reasoning is a little off. For the P(k+1) case you want to make sure that you have a set of elements that are no greater than 2k, and have k elements. Here are the three possible cases.
    Case 1:
    Now if more than one element is 2k+1 or 2k+2, then P(k+1) is true as any number is divisible by itself.
    Case 2:
    If only one element or no element is greater than 2k then we can apply the induction hypothesis (by looking at the first k+1).
    Case 3:
    Precisely one element is 2k+1 and one 2k+2, in which case we have k elements that are less than or equal to 2k (we need k+1).
    If we have 2 in our set, then 2|(2k+2) and we are done.
    Suppose that 2 is not in our set and notice that for a\neq 2, a|(2k+2) iff a|(k+1), as 2 is prime. Also k+1\leq 2k. So replace the element 2k+2 by k+1, and you get k+1 elements that are less than 2k. Apply the inductive hypothesis to conclude this case.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    If you also wish to prove this not by induction, then you may do it this way:

    Let a_1,a_2,...,a_{n+1} be our numbers. Let us define a sequence \{b_k\}_{k=1}^{n+1} as b_i = a_i (mod \ n) \ \forall 1\leq i \leq n+1.

    Now, since there are only n possible values for b_i , from the pidgeonhole principle we get that at least two elements in that sequence must equal each other (since there are n+1 elements for n possible values), and from that, one of them must divide the other.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    244

    I finally got it

    Quote Originally Posted by Focus View Post
    It is not wrong per say, but the reasoning is a little off. For the P(k+1) case you want to make sure that you have a set of elements that are no greater than 2k, and have k elements. Here are the three possible cases.
    Case 1:
    Now if more than one element is 2k+1 or 2k+2, then P(k+1) is true as any number is divisible by itself.
    Case 2:
    If only one element or no element is greater than 2k then we can apply the induction hypothesis (by looking at the first k+1).
    Case 3:
    Precisely one element is 2k+1 and one 2k+2, in which case we have k elements that are less than or equal to 2k (we need k+1).
    If we have 2 in our set, then 2|(2k+2) and we are done.
    Suppose that 2 is not in our set and notice that for a\neq 2, a|(2k+2) iff a|(k+1), as 2 is prime. Also k+1\leq 2k. So replace the element 2k+2 by k+1, and you get k+1 elements that are less than 2k. Apply the inductive hypothesis to conclude this case.
    Thanks so much for this! I've been going over it off and on for the past couple of hours and I've finally lit the led in my head!

    I've also been struggling with a stubborn home-made Macgyvered electrolysis experiment I cooked up for an inner city Chemistry class I'm observing for my sec ed class. It's been 35 years since I did chemistry and it shows. The chem teacher's specialty is Biology so I've been able to teach a couple of classes. I figured out my error there also, so things are looking up!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member Focus's Avatar
    Joined
    Aug 2009
    Posts
    228
    Quote Originally Posted by oldguynewstudent View Post
    Thanks so much for this! I've been going over it off and on for the past couple of hours and I've finally lit the led in my head!

    I've also been struggling with a stubborn home-made Macgyvered electrolysis experiment I cooked up for an inner city Chemistry class I'm observing for my sec ed class. It's been 35 years since I did chemistry and it shows. The chem teacher's specialty is Biology so I've been able to teach a couple of classes. I figured out my error there also, so things are looking up!
    Glad to hear that. Good luck with your studies. Hopefully you can spend the next 35 years doing maths .
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  2. Mathematical Induction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 7th 2010, 12:22 PM
  3. Mathematical Induction
    Posted in the Algebra Forum
    Replies: 9
    Last Post: July 8th 2009, 12:27 AM
  4. Mathematical Induction
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: February 17th 2009, 11:30 AM
  5. Mathematical Induction
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 30th 2007, 03:21 PM

Search Tags


/mathhelpforum @mathhelpforum