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

Thread: 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 $\displaystyle \binom{2n}{n}$ is divisible by a $\displaystyle p$ prime number if $\displaystyle \left\{ \frac{n}{p}\right\} \geq\frac{1}{2}$, where $\displaystyle \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 $\displaystyle \binom{2n}{n}$ is divisible by a $\displaystyle p$ prime number if $\displaystyle \left\{ \frac{n}{p}\right\} \geq\frac{1}{2}$, where $\displaystyle \left\{ \frac{n}{p}\right\} $ means fractional part?

    Thanks!
    The number of times $\displaystyle p $ appears in the numerator is $\displaystyle \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 $\displaystyle p $ appears in the denominator is $\displaystyle 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@; Jul 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 $\displaystyle p $ appears in the numerator is $\displaystyle \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 $\displaystyle p $ appears in the denominator is $\displaystyle \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@; Jul 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 $\displaystyle \binom{2n}{n}$ is divisible by a $\displaystyle p$ prime number if $\displaystyle \left\{ \frac{n}{p}\right\} \geq\frac{1}{2}$, where $\displaystyle \left\{ \frac{n}{p}\right\} $ means fractional part?

    Thanks!
    Here is what I've tried. $\displaystyle n=pb+r$, with $\displaystyle p/2\leq r<p$ (becuase $\displaystyle r/p$ is the fractional part). Then $\displaystyle \left \lfloor \frac{n}{p} \right \rfloor=b$ and $\displaystyle \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 $\displaystyle 2r\geq p$). So, $\displaystyle 2\left \lfloor \frac{n}{p} \right \rfloor<\left \lfloor \frac{2n}{p} \right \rfloor$. (Remember this).

    In general, $\displaystyle \left \lfloor a+b \right \rfloor\geq\left \lfloor a \right \rfloor+\left \lfloor b \right \rfloor$, so $\displaystyle \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, $\displaystyle \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 $\displaystyle k=1$ we have a strict inequality.

    Now, due to Legendre, the exponent of the largest power of $\displaystyle p $ that divides $\displaystyle \frac{(2n)!}{n!n!}$ is $\displaystyle \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
    $, and this expresstion is positive. This implies that $\displaystyle p $ divides $\displaystyle \binom{2n}{n}$.

    I hope this helps...
    Last edited by melese; Jul 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. $\displaystyle n=pb+r$, with $\displaystyle p/2\leq r<p$ (becuase $\displaystyle r/p$ is the fractional part). Then $\displaystyle \left \lfloor \frac{n}{p} \right \rfloor=b$ and $\displaystyle \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 $\displaystyle 2r\geq p$). So, $\displaystyle \left \lfloor \frac{n}{p} \right \rfloor<\left \lfloor \frac{2n}{p} \right \rfloor$. (Remember this).

    In general, $\displaystyle \left \lfloor a+b \right \rfloor\geq\left \lfloor a \right \rfloor+\left \lfloor b \right \rfloor$, so $\displaystyle \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, $\displaystyle \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 $\displaystyle k=1$ we have a strict inequality.
    Two comments:

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

    Also it's possible to have $\displaystyle \left\{\frac np\right\}=0 $ and still have $\displaystyle p\mid \binom{2n}{n} $. Ex: $\displaystyle 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 $\displaystyle \left \lfloor \frac{n}{p} \right \rfloor<\left \lfloor \frac{2n}{p} \right \rfloor$, but this doesn't imply $\displaystyle 2\left \lfloor \frac{n}{p} \right \rfloor<\left \lfloor \frac{2n}{p} \right \rfloor$.

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

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

    Your second comment: I agree with your example, however, the OP says that $\displaystyle \left\{ \frac{n}{p}\right\} \geq\frac{1}{2}
    $ 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 $\displaystyle \left\{ \frac{n}{p}\right\} \geq\frac{1}{2}
    $ so I went from there....
    I was hoping with the addition of $\displaystyle \left\{\frac np\right\}=0 $ and a constraint on the size of $\displaystyle p $, this was an if and only if statement, i.e. "if $\displaystyle 0<\left\{\frac np\right\}<\frac12 $, then $\displaystyle p\not|\binom{2n}{n} $.

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

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



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

    or $\displaystyle \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 \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 $\displaystyle k $ such that $\displaystyle 2 \{ \frac{n}{p^k} \} \geq 1 $ or equivalently $\displaystyle \{ \frac{n}{p^k} \} \geq \frac{1}{2} $ . I believe $\displaystyle k $ is not necessarily to be $\displaystyle 1 $ . For example , $\displaystyle n = 16 ~~ ,~~ p = 5 $ we have

    $\displaystyle \frac{16}{5} = 3.2 $ and $\displaystyle \frac{16}{25} = 0.64 $ but we still have $\displaystyle 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
    $\displaystyle \lfloor{ a + b \rfloor} = \lfloor{ a \rfloor} + \lfloor{ b \rfloor} + \lfloor{ \{ a \} + \{ b \} \rfloor} $



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

    or $\displaystyle \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 \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 $\displaystyle k $ such that $\displaystyle 2 \{ \frac{n}{p^k} \} \geq 1 $ or equivalently $\displaystyle \{ \frac{n}{p^k} \} \geq \frac{1}{2} $ . I believe $\displaystyle k $ is not necessarily to be $\displaystyle 1 $ . For example , $\displaystyle n = 16 ~~ ,~~ p = 5 $ we have

    $\displaystyle \frac{16}{5} = 3.2 $ and $\displaystyle \frac{16}{25} = 0.64 $ but we still have $\displaystyle 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
    $\displaystyle \lfloor{ a + b \rfloor} = \lfloor{ a \rfloor} + \lfloor{ b \rfloor} + \lfloor{ \{ a \} + \{ b \} \rfloor} $



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

    or $\displaystyle \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 \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 $\displaystyle k $ such that $\displaystyle 2 \{ \frac{n}{p^k} \} \geq 1 $ or equivalently $\displaystyle \{ \frac{n}{p^k} \} \geq \frac{1}{2} $ . I believe $\displaystyle k $ is not necessarily to be $\displaystyle 1 $ . For example , $\displaystyle n = 16 ~~ ,~~ p = 5 $ we have

    $\displaystyle \frac{16}{5} = 3.2 $ and $\displaystyle \frac{16}{25} = 0.64 $ but we still have $\displaystyle 5 | \binom{32}{16} $
    We can assume $\displaystyle 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 $\displaystyle p $ denoted by $\displaystyle a $ such that $\displaystyle p^a | \binom{2n}{n} $ can be obtained by this formula ( without a formal proof , could be wrong ) : $\displaystyle \frac{ 2S(n) - S(2n) }{p-1} $ where $\displaystyle S(n) $ is the sum of the digits of $\displaystyle n $ in the representation of base $\displaystyle p $ .


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

    $\displaystyle \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 $\displaystyle p$ a prime number, so the highest power of $\displaystyle p$ which divides $\displaystyle n!$ is $\displaystyle \sum_{k=1}^{\infty}\left\lfloor \frac{n}{p^{k}}\right\rfloor $, so the highest power of $\displaystyle p$ which divides the central binomial coefficient is $\displaystyle \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 $\displaystyle \left\lfloor 2x\right\rfloor -2\left\lfloor x\right\rfloor $ will be 1 for all real number if $\displaystyle \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 $\displaystyle \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 $\displaystyle \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 $\displaystyle p$ a prime number, so the highest power of $\displaystyle p$ which divides $\displaystyle n!$ is $\displaystyle \sum_{k=1}^{\infty}\left\lfloor \frac{n}{p^{k}}\right\rfloor $, so the highest power of $\displaystyle p$ which divides the central binomial coefficient is $\displaystyle \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 $\displaystyle \left\lfloor 2x\right\rfloor -2\left\lfloor x\right\rfloor $ will be 1 for all real number if $\displaystyle \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 $\displaystyle \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 $\displaystyle \left\{ \frac{n}{p}\right\} \geq\frac{1}{2}$.
    Just a minor remark. $\displaystyle \sum_{k=1}^{\infty}\left\lfloor \frac{n}{p^{k}}\right\rfloor$ is the exponent of the highest power of $\displaystyle p$ that divides $\displaystyle 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: Aug 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: Oct 2nd 2009, 01:06 PM
  4. Replies: 6
    Last Post: Sep 28th 2009, 04:16 PM
  5. central limit theorem and binomial distribution
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: Feb 10th 2008, 03:18 AM

Search Tags


/mathhelpforum @mathhelpforum