# Proof that each prime power of ${2n \choose n}$ is $\leq \log_p 2n$

I'm trying to work through this proof of the prime number theorem.

Def: Let $$P_p(x)$$ be the prime power of $$p$$ in the prime factorization of $$x$$. I.e. for any natural number $$x$$, $$x = \prod_{p\in \text{primes}} p^{P_p(x)}$$.

I am trying to prove the following lemma.

Lemma: $$\forall p \in \text{primes}, \forall n\in \mathbb N: P_p\left({2n \choose n}\right) \leq \log_p(2n)$$

My attempt at a proof: (tldr, I end up getting $$P_p\left({2n \choose n} \right) \leq \log_p(n^2) + \frac{1}{p-1}$$, how do I get the $$2n$$ in the log instead of the $$n^2$$?)

For any $$a, b \in \mathbb N$$, we have that $$P_p(ab) = P_p(a) + P_p(b)$$. Similarly, if $$a/b \in \mathbb N$$ then $$P_p(a/b) = P_p(a) - P_p(b)$$. Consider the $$p=2$$ case:

\begin{align*} P_2(n!) &= P_2(1) + P_2(2) + P_2(3) + P_2(4) + \dots\\ &= P_2(2) + P_2(4) + \dots\\ &= P_2(2\cdot 1)+ P_2(2\cdot 2) + \dots\\ &= \lfloor n/2 \rfloor \cdot P_2(2) + P_2(1) + P_2(2) + \dots + P_2(\lfloor n/2 \rfloor)\\ &= \lfloor n/2 \rfloor + P_2(\lfloor n/2 \rfloor !) \end{align*}

Similarly, for general $$p$$, \begin{align*} P_p(n!) &= \lfloor n/p \rfloor + P_p(\lfloor n/p \rfloor!)\\ &= \lfloor n/p \rfloor + \lfloor n/p^2 \rfloor + P_p(\lfloor n/p^2 \rfloor !)\\ &= \sum_{i=1}^{\log_p n} \lfloor n/p^i \rfloor \end{align*}

Then we can bound it as $$P_p(n!) \leq \sum_{i=1}^{\log_p n} n/p^i$$ and $$P_p(n!) > \sum_{i=1}^{\log_p n}\left(n/p^i-1 \right)$$. So then $$\frac{n-1}{p-1} - \log_p n < P_p(n!) \leq \frac{n-1}{p-1}$$

Then we finally get that \begin{align*} P_p\left({2n \choose n} \right) &= P_p((2n)!) - 2P_p(n!)\\ &< \frac{2n-1}{p-1} - 2\frac{n-1}{p-1} + 2\log_p n\\ &= 2\log_p n + \frac{1}{p-1} \end{align*}

How can I fix this so that I prove the desired lemma?

• Instead of estimating $\lfloor n/q\rfloor$ and $\lfloor 2n/q\rfloor$ separately, try estimating the specific combination you care about. What are the possible values of $\lfloor 2n/q\rfloor - 2\lfloor n/q\rfloor$ (indeed, of the function $\lfloor 2t\rfloor - 2\lfloor t\rfloor$)? Dec 29, 2020 at 21:59
• Oh beautiful, thank you!
– Joe
Dec 29, 2020 at 22:02
• @Joe Consider Kummer's theorem. Dec 29, 2020 at 22:02
• A proof of this fact is given in Wikipedia here: en.wikipedia.org/wiki/…. Dec 30, 2020 at 0:50

Thanks to @Greg Martin for his answer. For completeness, I'll include the result here. As I have above, $$P_p\left(n!\right) = \sum_{i=1}^{\lfloor \log_p n\rfloor } \lfloor n/p^i\rfloor$$. So
\begin{align*} P_p\left({2n \choose n}\right) &= P_p((2n)!) - 2P_p(n!)\\ &= \sum_{i=1}^{\lfloor\log_p2n\rfloor}\lfloor 2n/p^i\rfloor - 2\sum_{i=1}^{\lfloor\log_p n\rfloor}\lfloor n/p^i\rfloor\\ &= \sum_{i=1}^{\lfloor\log_p2n\rfloor} \left(\lfloor 2n/p^i\rfloor - 2\lfloor n/p^i\rfloor \right)\\ &\leq \sum_{i=1}^{\lfloor\log_p2n\rfloor}1\\ &\leq \log_p2n \end{align*}