Prove that the power of prime factors of $\binom{2n}{n}$ has an upper bound of $\left\lfloor \frac{\ln(2n)}{\ln p} \right\rfloor$

126 Views Asked by At

The proof of $ \ln\binom{2n}{n}\leq\sum_{p\leq 2n}\left\lfloor\dfrac{\ln(2n)}{\ln(p)}\right\rfloor\ln(p)$ is :

Let's define $\nu_p(n)$ be the highest power of a prime factor $p$ of $n$.

Note that in the set of numbers $\{1,2,\cdots,n\}$ there are $\left\lfloor n/p \right\rfloor$ multiples of $p$, $\left\lfloor n/p^2 \right\rfloor$ multiples of $p^2$, and so on, each contributing $1$ to $\nu_p(n!)$. Therefore, $\nu_p(n!)=\sum_m\left\lfloor\dfrac{n}{p^m}\right\rfloor$.

We have $\binom{2n}{n}=\dfrac{2n!}{n!n!}$ and $\nu_p(a/b)=\nu_p(a)-\nu_p(b)$ which implies $\nu_p\binom{2n}{n}=\sum_m \bigg(\left\lfloor 2n/p^m \right\rfloor-2\left\lfloor n/p^m\right \rfloor\bigg)$

Then it is stated that the largest $m$ is $\left\lfloor \dfrac{\ln(2n)}{\ln p} \right\rfloor$

How do we prove that the upper bound of the power of prime factors of $\binom{2n}{n}$ satisfies $\color{red}{m\leq \left\lfloor \dfrac{\ln(2n)}{\ln p} \right\rfloor}$ ?

and the proof follows as, $$ \nu_p\binom{2n}{n}=\sum_{1\leq m\leq \left\lfloor \frac{\ln(2n)}{\ln p} \right\rfloor} \bigg(\left\lfloor 2n/p^m \right\rfloor-2\left\lfloor n/p^m\right \rfloor\bigg)\\ \leq \sum_{1\leq m\leq \left\lfloor \frac{\ln(2n)}{\ln p} \right\rfloor}1\\ \nu_p\binom{2n}{n}\le\left\lfloor \frac{\ln(2n)}{\ln p} \right\rfloor $$ By Stirling's formula $n\leq \log\binom{2n}{n}\leq 2n$, so all the prime factors of $\binom{2n}{n}$ are between $0$ and $2n$ and each factor $p$ cannot appear more than $\left\lfloor \frac{\ln(2n)}{\ln p}\right\rfloor$ times. Therefore, $$ \binom{2n}{n}\leq \prod_{1\leq p\leq 2n}p^{\left\lfloor \frac{\ln(2n)}{\ln p}\right\rfloor}\implies \ln\binom{2n}{n}\leq \sum_{1\leq p\leq 2n}{\left\lfloor \frac{\ln(2n)}{\ln p}\right\rfloor}\ln p $$ Note : $\left\lfloor x \right\rfloor$ is the floor function which gives the greatest integer less than or equal to $x$

1

There are 1 best solutions below

0
On BEST ANSWER

We know that for $m$ large enough then $\frac{2n}{p^m}$ (and then $\frac{n}{p^m}$) will be smaller that $1$ so the floors will be $0$. So ask yourself: when is still $\frac{2n}{p^m} \ge 1$?

Solve for $m$.