4
$\begingroup$

Let $n \geq 3$, show ${2n \choose n}$ is not divisible by $p$ for all primes $\frac{2n}{3}

Note: This fact along with other facts about ${2n \choose n}$ are used in a proof of Bertrand's postulate.

  • 1
    Any such prime appears exactly twice both in the numerator and the denominator of $\binom{2n}{n}= \frac{(2n)!}{(n!)^2}$.2012-08-14

1 Answers 1

7

I think that the idea is rather simple (not verifying Brian's hint...) :

We need to divide $(2n)!$ by $n!^2$ so let's write the primes of the decomposition of $(2n)!$ and $n!$.

Let's suppose that $\frac n2

is such a prime larger than $2$ then :

$ \binom{2n}{n} = \frac{(2n)!}{(n!)^2}= \frac{ 2n\cdot (2n-1)\cdots(2p)\cdots (n)\cdots (p)\cdots 2\cdot 1} {(n)\cdots (p)\cdots 2\cdot 1\cdot (n)\cdots (p)\cdots 2\cdot 1} $

When $3p\le 2n$ we will have at least $3$ $p$'s at the top and the fraction will be divisible by $p$ else the two $p$ will cancel !