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

Math Help - Divisibility of central binomial coefficient

  1. #1
    Newbie
    Joined
    Jul 2009
    Posts
    16

    Divisibility of central binomial coefficient

    Hello!

    I have a question! Is it true that the central binomial coefficient \binom{2n}{n} is divisible by a p prime number if \left\{ \frac{n}{p}\right\} \geq\frac{1}{2}, where \left\{ \frac{n}{p}\right\} means fractional part?

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by Ben92 View Post
    Hello!

    I have a question! Is it true that the central binomial coefficient \binom{2n}{n} is divisible by a p prime number if \left\{ \frac{n}{p}\right\} \geq\frac{1}{2}, where \left\{ \frac{n}{p}\right\} means fractional part?

    Thanks!
    The number of times  p appears in the numerator is  \left\lfloor\frac{2n}{p}\right\rfloor+\left\lfloor  \frac{2n}{p^2}\right\rfloor+\left\lfloor\frac{2n}{  p^3}\right\rfloor+\ldots

    The number of times  p appears in the denominator is  2\left(\left\lfloor\frac{n}{p}\right\rfloor+\left\  lfloor\frac{n}{p^2}\right\rfloor+\left\lfloor\frac  {n}{p^3}\right\rfloor+\ldots\right)

    See if you can use this to get your answer.
    Last edited by chiph588@; July 10th 2010 at 04:11 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by chiph588@ View Post
    The number of times  p appears in the numerator is  \left\lfloor\frac{2n}{p}\right\rfloor+\left\lfloor  \frac{2n}{p^2}\right\rfloor+\left\lfloor\frac{2n}{  p^3}\right\rfloor+\ldots

    The number of times  p appears in the denominator is  \left(\left\lfloor\frac{n}{p}\right\rfloor+\left\l  floor\frac{n}{p^2}\right\rfloor+\left\lfloor\frac{  n}{p^3}\right\rfloor+\ldots\right)^2

    See if you can use this to get your answer.
    .
    Last edited by chiph588@; July 10th 2010 at 04:23 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Jul 2009
    Posts
    16
    Thanks!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1
    I think that OP question can also be proved by using: Bertrand's postulate - Wikipedia, the free encyclopedia
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148
    Quote Originally Posted by Ben92 View Post
    Hello!

    I have a question! Is it true that the central binomial coefficient \binom{2n}{n} is divisible by a p prime number if \left\{ \frac{n}{p}\right\} \geq\frac{1}{2}, where \left\{ \frac{n}{p}\right\} means fractional part?

    Thanks!
    Here is what I've tried. n=pb+r, with p/2\leq r<p (becuase r/p is the fractional part). Then \left \lfloor \frac{n}{p} \right \rfloor=b and \left \lfloor \frac{2n}{p} \right \rfloor=\left \lfloor 2b+\frac{2r}{p} \right \rfloor=2b+\left \lfloor \frac{2r}{p} \right \rfloor\geq 2b+1 (since 2r\geq p). So, 2\left \lfloor \frac{n}{p} \right \rfloor<\left \lfloor \frac{2n}{p} \right \rfloor. (Remember this).

    In general, \left \lfloor a+b \right \rfloor\geq\left \lfloor a \right \rfloor+\left \lfloor b \right \rfloor, so \left \lfloor \frac{2n}{p^k} \right \rfloor=\left \lfloor \frac{n}{p^k}+\frac{n}{p^k} \right \rfloor\geq\left \lfloor \frac{n}{p^k} \right \rfloor+\left \lfloor \frac{n}{p^k} \right \rfloor=2\left \lfloor \frac{n}{p^k} \right \rfloor. Therefore, \sum_{k=1}^{\infty}\left \lfloor \tfrac{2n}{p^k} \right \rfloor>\sum_{k=1}^{\infty}2\left \lfloor \tfrac{n}{p^k} \right \rfloor, since when k=1 we have a strict inequality.

    Now, due to Legendre, the exponent of the largest power of p that divides \frac{(2n)!}{n!n!} is \sum_{k=1}^{\infty}\left \lfloor \tfrac{2n}{p^k} \right \rfloor-\sum_{k=1}^{\infty}2\left \lfloor \tfrac{n}{p^k} \right \rfloor<br />
, and this expresstion is positive. This implies that p divides \binom{2n}{n}.

    I hope this helps...
    Last edited by melese; July 10th 2010 at 04:44 PM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by melese View Post
    Here is what I've tried. n=pb+r, with p/2\leq r<p (becuase r/p is the fractional part). Then \left \lfloor \frac{n}{p} \right \rfloor=b and \left \lfloor \frac{2n}{p} \right \rfloor=\left \lfloor 2b+\frac{2r}{p} \right \rfloor=2b+\left \lfloor \frac{2r}{p} \right \rfloor\geq 2b+1 (since 2r\geq p). So, \left \lfloor \frac{n}{p} \right \rfloor<\left \lfloor \frac{2n}{p} \right \rfloor. (Remember this).

    In general, \left \lfloor a+b \right \rfloor\geq\left \lfloor a \right \rfloor+\left \lfloor b \right \rfloor, so \left \lfloor \frac{2n}{p^k} \right \rfloor=\left \lfloor \frac{n}{p^k}+\frac{n}{p^k} \right \rfloor\geq\left \lfloor \frac{n}{p^k} \right \rfloor+\left \lfloor \frac{n}{p^k} \right \rfloor=2\left \lfloor \frac{n}{p^k} \right \rfloor. Therefore, \sum_{k=1}^{\infty}\left \lfloor \tfrac{2n}{p^k} \right \rfloor>\sum_{k=1}^{\infty}2\left \lfloor \tfrac{n}{p^k} \right \rfloor, since when k=1 we have a strict inequality.
    Two comments:

    You've shown \left \lfloor \frac{n}{p} \right \rfloor<\left \lfloor \frac{2n}{p} \right \rfloor, but this doesn't imply  2\left \lfloor \frac{n}{p} \right \rfloor<\left \lfloor \frac{2n}{p} \right \rfloor.

    Also it's possible to have  \left\{\frac np\right\}=0 and still have  p\mid \binom{2n}{n} . Ex:  2\mid\binom{28}{14} .
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148

    Reply to comments.

    Quote Originally Posted by chiph588@ View Post
    Two comments:

    You've shown \left \lfloor \frac{n}{p} \right \rfloor<\left \lfloor \frac{2n}{p} \right \rfloor, but this doesn't imply  2\left \lfloor \frac{n}{p} \right \rfloor<\left \lfloor \frac{2n}{p} \right \rfloor.

    Also it's possible to have  \left\{\frac np\right\}=0 and still have  p\mid \binom{2n}{n} . Ex:  2\mid\binom{28}{14} .
    chiph588@, thanks for your comments!

    Your first comment: I meant 2\left \lfloor \frac{n}{p} \right \rfloor<\left \lfloor \frac{2n}{p} \right \rfloor (I've already edited). This is because 2\left \lfloor \frac{n}{p} \right \rfloor=2b and \left \lfloor \frac{2n}{p} \right \rfloor \geq 2b+1.

    Your second comment: I agree with your example, however, the OP says that \left\{ \frac{n}{p}\right\} \geq\frac{1}{2}<br />
so I went from there....
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by melese View Post
    Your second comment: I agree with your example, however, the OP says that \left\{ \frac{n}{p}\right\} \geq\frac{1}{2}<br />
so I went from there....
    I was hoping with the addition of  \left\{\frac np\right\}=0 and a constraint on the size of  p , this was an if and only if statement, i.e. "if  0<\left\{\frac np\right\}<\frac12 , then  p\not|\binom{2n}{n} .

    This turns out to be false as  3\mid\binom{14}{7} and  \left\{\frac73\right\}=\frac13 .
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Super Member
    Joined
    Jan 2009
    Posts
    715
     \lfloor{ a + b \rfloor} = \lfloor{ a \rfloor} + \lfloor{ b \rfloor} + \lfloor{ \{ a \} + \{ b \}  \rfloor}



    Then  \lfloor{ \frac{2n}{p^k} \rfloor} = 2 \lfloor{ \frac{n}{p^k} \rfloor} +  \lfloor{ 2 \{ \frac{n}{p^k} \} \rfloor}

    or   \lfloor{ \frac{2n}{p^k} \rfloor} - 2 \lfloor{ \frac{n}{p^k} \rfloor} =  \lfloor{ 2 \{ \frac{n}{p^k} \} \rfloor} so the value of the power of the prime still be contained in the central coefficient is :

     \displaystyle{ \sum_{k\in \mathb{N} }}   \lfloor{ \frac{2n}{p^k} \rfloor} - 2 \lfloor{ \frac{n}{p^k} \rfloor} =  \displaystyle{ \sum_{k\in \mathb{N} }} \lfloor{ 2 \{ \frac{n}{p^k} \} \rfloor  .

    We need to ensure that there exists k such that  2 \{ \frac{n}{p^k} \}  \geq 1  or equivalently   \{ \frac{n}{p^k} \} \geq \frac{1}{2} . I believe  k is not necessarily to be  1 . For example ,  n = 16 ~~ ,~~ p = 5 we have

     \frac{16}{5} = 3.2   and  \frac{16}{25} = 0.64 but we still have  5 | \binom{32}{16}
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148
    Quote Originally Posted by simplependulum View Post
     \lfloor{ a + b \rfloor} = \lfloor{ a \rfloor} + \lfloor{ b \rfloor} + \lfloor{ \{ a \} + \{ b \}  \rfloor}



    Then  \lfloor{ \frac{2n}{p^k} \rfloor} = 2 \lfloor{ \frac{n}{p^k} \rfloor} +  \lfloor{ 2 \{ \frac{n}{p^k} \} \rfloor}

    or   \lfloor{ \frac{2n}{p^k} \rfloor} - 2 \lfloor{ \frac{n}{p^k} \rfloor} =  \lfloor{ 2 \{ \frac{n}{p^k} \} \rfloor} so the value of the power of the prime still be contained in the central coefficient is :

     \displaystyle{ \sum_{k\in \mathb{N} }}   \lfloor{ \frac{2n}{p^k} \rfloor} - 2 \lfloor{ \frac{n}{p^k} \rfloor} =  \displaystyle{ \sum_{k\in \mathb{N} }} \lfloor{ 2 \{ \frac{n}{p^k} \} \rfloor  .

    We need to ensure that there exists k such that  2 \{ \frac{n}{p^k} \}  \geq 1  or equivalently   \{ \frac{n}{p^k} \} \geq \frac{1}{2} . I believe  k is not necessarily to be  1 . For example ,  n = 16 ~~ ,~~ p = 5 we have

     \frac{16}{5} = 3.2   and  \frac{16}{25} = 0.64 but we still have  5 | \binom{32}{16}
    Nice argument...!
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by simplependulum View Post
     \lfloor{ a + b \rfloor} = \lfloor{ a \rfloor} + \lfloor{ b \rfloor} + \lfloor{ \{ a \} + \{ b \}  \rfloor}



    Then  \lfloor{ \frac{2n}{p^k} \rfloor} = 2 \lfloor{ \frac{n}{p^k} \rfloor} +  \lfloor{ 2 \{ \frac{n}{p^k} \} \rfloor}

    or   \lfloor{ \frac{2n}{p^k} \rfloor} - 2 \lfloor{ \frac{n}{p^k} \rfloor} =  \lfloor{ 2 \{ \frac{n}{p^k} \} \rfloor} so the value of the power of the prime still be contained in the central coefficient is :

     \displaystyle{ \sum_{k\in \mathb{N} }}   \lfloor{ \frac{2n}{p^k} \rfloor} - 2 \lfloor{ \frac{n}{p^k} \rfloor} =  \displaystyle{ \sum_{k\in \mathb{N} }} \lfloor{ 2 \{ \frac{n}{p^k} \} \rfloor  .

    We need to ensure that there exists k such that  2 \{ \frac{n}{p^k} \}  \geq 1  or equivalently   \{ \frac{n}{p^k} \} \geq \frac{1}{2} . I believe  k is not necessarily to be  1 . For example ,  n = 16 ~~ ,~~ p = 5 we have

     \frac{16}{5} = 3.2   and  \frac{16}{25} = 0.64 but we still have  5 | \binom{32}{16}
    We can assume  k=1 because it's in the hypothesis (I assume you're talking about the OP's original question).
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Super Member
    Joined
    Jan 2009
    Posts
    715
    Yes , so the if-then statement is correct , by the way i am not sure if this can help in this situation :

    The max. power of a given prime   p denoted by  a such that  p^a | \binom{2n}{n} can be obtained by this formula ( without a formal proof , could be wrong ) :  \frac{ 2S(n) - S(2n) }{p-1} where  S(n) is the sum of the digits of  n in the representation of base  p .


    For example ,  n = 15 ~,~ p = 2 we have  15 = 1111_{(2)} ~,~ 30 = 11110_{(2)} so  2S(15) - S(30) = 2(1+1+1+1) - (1+1+1+1) = 4 so  a = 4/1 = 4 which is true because

     \binom{30}{15} = 2^4 \times 9694845 .
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Newbie
    Joined
    Jul 2009
    Posts
    16
    My proof:

    Let p a prime number, so the highest power of p which divides n! is \sum_{k=1}^{\infty}\left\lfloor \frac{n}{p^{k}}\right\rfloor , so the highest power of p which divides the central binomial coefficient is \sum_{k=1}^{\infty}\left(\left\lfloor \frac{2n}{p^{k}}\right\rfloor -2\left\lfloor \frac{n}{p^{k}}\right\rfloor \right). And that is completely trivial \left\lfloor 2x\right\rfloor -2\left\lfloor x\right\rfloor will be 1 for all real number if \left\{ x\right\} \geq\frac{1}{2}, and we know that there are only two values possible: 0 or 1, so the summation is nonnegative. Thus, it is anough if \left\lfloor \frac{2n}{p^{k}}\right\rfloor -2\left\lfloor \frac{n}{p^{k}}\right\rfloor =1 happens at least once in the summation, and the initial condition shows that, because \left\{ \frac{n}{p}\right\} \geq\frac{1}{2}.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148
    Quote Originally Posted by Ben92 View Post
    My proof:

    Let p a prime number, so the highest power of p which divides n! is \sum_{k=1}^{\infty}\left\lfloor \frac{n}{p^{k}}\right\rfloor , so the highest power of p which divides the central binomial coefficient is \sum_{k=1}^{\infty}\left(\left\lfloor \frac{2n}{p^{k}}\right\rfloor -2\left\lfloor \frac{n}{p^{k}}\right\rfloor \right). And that is completely trivial \left\lfloor 2x\right\rfloor -2\left\lfloor x\right\rfloor will be 1 for all real number if \left\{ x\right\} \geq\frac{1}{2}, and we know that there are only two values possible: 0 or 1, so the summation is nonnegative. Thus, it is anough if \left\lfloor \frac{2n}{p^{k}}\right\rfloor -2\left\lfloor \frac{n}{p^{k}}\right\rfloor =1 happens at least once in the summation, and the initial condition shows that, because \left\{ \frac{n}{p}\right\} \geq\frac{1}{2}.
    Just a minor remark. \sum_{k=1}^{\infty}\left\lfloor \frac{n}{p^{k}}\right\rfloor is the exponent of the highest power of p that divides n!.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Binomial coefficient
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: August 20th 2011, 01:35 PM
  2. binomial coefficient.
    Posted in the Algebra Forum
    Replies: 3
    Last Post: May 12th 2010, 10:30 PM
  3. Binomial Theorem or Binomial Coefficient
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: October 2nd 2009, 01:06 PM
  4. Replies: 6
    Last Post: September 28th 2009, 04:16 PM
  5. central limit theorem and binomial distribution
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: February 10th 2008, 03:18 AM

Search Tags


/mathhelpforum @mathhelpforum