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?
Best Answer
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*}