Let $n$ be a positive integer and $p$ a prime, how can I prove that the highest power of $p$ that divides $\binom{2n}{n}$ is exactly the number of $k\geq1$ such that $\lfloor 2n/p^k\rfloor$ is odd?
On a property of the binomial coefficient
-
0In going from $n$ to $n+1$, ${2n \choose n}$ is multiplied by $\frac{2(2n+1)}{n+1}$. How does the highest power of $p$ change? How does the number of $k$ change? – 2011-08-28
2 Answers
Let us write out this binomial coefficient a bit more
$\binom{2n}{n} = \frac{2n \cdot (2n-1) \cdot \ldots \cdot (n+1)}{n \cdot (n-1) \cdot \ldots \cdot 1}$
Above we have all numbers between $n + 1$ and $2n$, while below we have all numbers from $1$ to $n$. Now suppose $\lfloor 2n/p\rfloor = 2m + 1$. Then there are exactly $m + 1$ numbers between $(n+1)$ and $2n$ that are divisible by $p$, and $m$ numbers between $1$ and $n$ divisible by $p$. So this gives that $p \ | \ \binom{2n}{n}$, and in fact this gives exactly one factor $p$. Alternatively, if $\lfloor 2n/p\rfloor = 2m$ then the factors above and below cancel out, giving no remaining factor $p$.
Similarly, suppose $\lfloor 2n/p^2\rfloor = 2m + 1$. Then we get an extra factor $p^2$ above, compared to below the bar. However, we already counted the single factors $p$ when we checked the parity of $\lfloor 2n/p\rfloor$, so we only get one extra factor $p$. You can continue this for higher $k$, until at some point $p^k > 2n$ and $\lfloor 2n/p^k\rfloor = 0$ for all $k$.
If you want more of an intuition for this, consider e.g. $\binom{132}{66}$ and $p = 5$. Then $\lfloor 132/5\rfloor = 26$, so both above and below we get $13$ numbers divisible by $5$. These are $70, 75, \ldots, 130$ above and $5, 10, \ldots, 65$ below. So these factors $p$ cancel. Since $\lfloor 132/25\rfloor = 5$ we get $3$ numbers ($75, 100, 125$) above and $2$ numbers ($25, 50$) below contributing another $p$ to the product. Finally $125$ contributes another factor $p$ to the number, so $\binom{132}{66} = 5^2 q$, with $5 \not| \ \ q$.
Edit: You could perhaps make the above a bit more rigorous and shorter by explaining exactly how many factors $p$ are in the product $2n \cdot (2n-1) \cdot \ldots \cdot (n+1)$, and how many factors $p$ there are in the product $n \cdot (n-1) \cdot \ldots \cdot 1$. The number of factors $p$ in the product $(2n)!$ is simply:
$\lfloor \frac{2n}{p} \rfloor + \lfloor \frac{2n}{p^2} \rfloor + \ldots + \lfloor \frac{2n}{p^k} \rfloor + \ldots$
The number of factors in $n!$ is exactly
$\lfloor \frac{n}{p} \rfloor + \lfloor \frac{n}{p^2} \rfloor + \ldots + \lfloor \frac{n}{p^k} \rfloor + \ldots$
So the number of factors in $\binom{2n}{n}$ is
$\left(\lfloor \frac{2n}{p} \rfloor + \lfloor \frac{2n}{p^2} \rfloor + \ldots + \lfloor \frac{2n}{p^k} \rfloor + \ldots\right) - 2\left(\lfloor \frac{n}{p} \rfloor + \lfloor \frac{n}{p^2} \rfloor + \ldots + \lfloor \frac{n}{p^k} \rfloor + \ldots\right)$
You can then complete the proof by noting that
$\lfloor \frac{2n}{p^k} \rfloor - 2 \lfloor \frac{n}{p^k} \rfloor = \begin{cases} 1 & \text{if } \lfloor 2n/p^k \rfloor \text{ odd} \\ 0 & \text{if } \lfloor 2n/p^k \rfloor \text{ even} \end{cases}$
HINT:
This is a useful general approach to questions regarding the divisibility of factorials and binomials. What is the highest power of $p$ that divides $n!$? Well $p, 2p, 3p,...$ and all further multiples up to $n$ divide $n!$, so at least $ \left\lfloor \frac{n}{p} \right\rfloor $. But that was not counting $2$ powers for every square, $p^2, 2p^2...$. So we need to tack on another $\left\lfloor \frac{n}{p^2} \right\rfloor$. And now we need to account for cubes and so on, so the highest power of $p$ that divides $n!$ is $ \sum_{k=1}^{\infty} \left\lfloor \frac{n}{p^k} \right\rfloor. $
Now, since $ \binom{2n}{n} = \frac{(2n)!}{(n!)^2} $, the highest power of $p$ to divide that is given by: $ \sum_{k=1}\left( \left\lfloor \frac{2n}{p^k} \right\rfloor - 2\left\lfloor \frac{n}{p^k}\right\rfloor \right) $
Investigate the general term in cases and deduce your result.
Edit: Thijs, your recent edit ended up being essentially my post.