Divisibility of central binomial coefficient

**Ben92** · July 10th 2010, 01:34 PM

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!

**chiph588@** · July 10th 2010, 02:03 PM

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)$

See if you can use this to get your answer.

**chiph588@** · July 10th 2010, 02:11 PM

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$

See if you can use this to get your answer.

.

**Ben92** · July 10th 2010, 02:58 PM

Thanks!

**Also sprach Zarathustra** · July 10th 2010, 03:03 PM

I think that OP question can also be proved by using: Bertrand's postulate - Wikipedia, the free encyclopedia

**melese** · July 10th 2010, 04:09 PM

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

**chiph588@** · July 10th 2010, 04:22 PM

Originally Posted by melese

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

**melese** · July 10th 2010, 05:00 PM

Originally Posted by chiph588@

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

**chiph588@** · July 10th 2010, 05:28 PM

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

**simplependulum** · July 10th 2010, 06:39 PM

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

**melese** · July 10th 2010, 06:56 PM

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...!

**chiph588@** · July 10th 2010, 07:01 PM

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).

**simplependulum** · July 10th 2010, 07:13 PM

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

**Ben92** · July 11th 2010, 04:31 AM

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

**melese** · July 11th 2010, 01:54 PM

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

Thread: Divisibility of central binomial coefficient

LinkBack

Thread Tools

Display

Divisibility of central binomial coefficient

Reply to comments.

Similar Math Help Forum Discussions

Binomial coefficient

binomial coefficient.

Binomial Theorem or Binomial Coefficient

[SOLVED] Divisibility property of a prime's central binomial coefficient

central limit theorem and binomial distribution

Search Tags