Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
There's a theorem of Kronecker that says that the highest power of $p$ that divides $\binom{k}{\ell}$ is the number of carries when adding $k$ and $k-\ell$ in base $p$... But you probably don't want to use that. –  Arturo Magidin Aug 28 '11 at 22:28
    
no, I'd like an elementary proof –  Alex M Aug 28 '11 at 23:02
    
In 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? –  Robert Israel Aug 28 '11 at 23:48

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.