1
$\begingroup$

How can we show that

$\operatorname{ord}_{p}\left(\binom{2n}n\right) \le \frac{\log 2n}{\log p}$ where $p$ is a prime number and $n$ is a natural number

My attempt:

$2^{n} \le \prod _{k=1}^{n} \frac{k+n}{k} = \begin{pmatrix} 2n \\ n \end{pmatrix} = \frac{(2n)!}{n!n!} = \sum_{n\le 2n}p^{\operatorname{ord}_{p}(p)}$

$\Rightarrow \operatorname{ord}_{p}(p) \le \sum_{m=1}^{\infty}\left(\left\lfloor\frac{2n}{p^{m}}\right\rfloor-2\left\lfloor\frac{n}{p^{m}}\right\rfloor \right) \le \left\lfloor\frac{\log 2n}{\log p}\right\rfloor \le \frac{\log 2n}{\log p}$

  • 0
    Related: [this](http://math.stackexchange.com/questions/2791/binomial-coefficients-how-to-prove-an-inequality-on-the-p-adic-valuation) question.2012-03-15

1 Answers 1

3

You haven't explained any reasoning in your attempt but it appears to be in the correct direction. By Legendre's formula, $ \operatorname{ord}_p \left( \binom{2n}{n} \right) = \sum_{m=1}^{\infty}\left(\left\lfloor\frac{2n}{p^{m}}\right\rfloor-2\left\lfloor\frac{n}{p^{m}}\right\rfloor \right) .$

Each term in the sum is either $0$ or $1$ and there are at most $\displaystyle \left\lfloor\frac{\log 2n}{\log p}\right\rfloor$ non-zero terms since if $m > \log_p 2n $ then $ \displaystyle \frac{2n}{p^m}<1.$