# 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 $\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!
• 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 $\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)$

• Jul 10th 2010, 02:11 PM
chiph588@
Quote:

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

.
• 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 $\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 (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
$
, and this expresstion is positive. This implies that $p$ divides $\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. $n=pb+r$, with $p/2\leq r (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.

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

Originally Posted by chiph588@

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

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}
$
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 $\left\{ \frac{n}{p}\right\} \geq\frac{1}{2}
$
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$.
• Jul 10th 2010, 06:39 PM
simplependulum
$\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}$
• Jul 10th 2010, 06:56 PM
melese
Quote:

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

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

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