# Divisibility of central binomial coefficient

Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• Jul 10th 2010, 01:34 PM
Ben92
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!
• Jul 10th 2010, 02:03 PM
chiph588@
Quote:

Originally Posted by Ben92
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.
• Jul 10th 2010, 02:11 PM
chiph588@
Quote:

Originally Posted by chiph588@
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.

.
• Jul 10th 2010, 02:58 PM
Ben92
Thanks! :)
• Jul 10th 2010, 03:03 PM
Also sprach Zarathustra
I think that OP question can also be proved by using: Bertrand's postulate - Wikipedia, the free encyclopedia
• Jul 10th 2010, 04:09 PM
melese
Quote:

Originally Posted by Ben92
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...
• Jul 10th 2010, 04:22 PM
chiph588@
Quote:

Originally Posted by melese
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.

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}$.
• Jul 10th 2010, 05:00 PM
melese
Quote:

Originally Posted by chiph588@

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}$.

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....
• Jul 10th 2010, 05:28 PM
chiph588@
Quote:

Originally Posted by melese
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$.
• Jul 10th 2010, 06:39 PM
simplependulum
$\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}$
• Jul 10th 2010, 06:56 PM
melese
Quote:

Originally Posted by simplependulum
$\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...!
• Jul 10th 2010, 07:01 PM
chiph588@
Quote:

Originally Posted by simplependulum
$\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).
• Jul 10th 2010, 07:13 PM
simplependulum
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$ .
• Jul 11th 2010, 04:31 AM
Ben92
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}$.
• Jul 11th 2010, 01:54 PM
melese
Quote:

Originally Posted by Ben92
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!$.
Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last