Show that $\binom {2n}n \leq(2n)^{\pi (2n)}$ where $\pi(2n) $ is number of prime number less than $2n$

203 Views Asked by At

Show that $$\binom {2n}n \leq(2n)^{\pi (2n)}$$ where, as usual, $\pi(2n) $ is number of prime number less than $2n$.

I was solving basic techniques of combinatorial theory by Daniel Cohen. I was stuck at ch-2 problem 72. can anyone help me out with this problem:

Let $\pi(x)$ denote the number of primes less than or equal to $x$.
(a) Use the previous problem to show that $$ \binom{2n}{n} \le (2n)^{\pi(2n)} $$

The previous problem 71 says this:

Snippet of previous problem

2

There are 2 best solutions below

0
On BEST ANSWER

The claim follows immediately from part c) of the rprevious exercise: If $r_p$ is the maximal exponent with which $p$ divides ${2n\choose n}$, then $${2n\choose n}=\prod_{p\le 2n} p^{r_p}\le \prod_{p\le 2n} 2n =(2n)^{\pi(2n)}$$

0
On

Let $\nu_p(x)$ the $p$-adic order of the integer $x$ then $$\binom{2n}{n}=\prod_{p\leq2n}p^{\nu_p\left(\binom{2n}{n}\right)}\leq\prod_{p\leq2n}p^{\ln_p(2n)}=\prod_{p\leq2n}2n=(2n)^{\pi(2n)}.$$ where we used the inequality $$\nu_p\left(\binom{2n}{n}\right)=\nu_p\left((2n)!\right)-2\nu_p\left(n!\right)= \sum_{k\geq 1}\left(\left\lfloor\frac{2n}{p^k}\right\rfloor-2\left\lfloor\frac{n}{p^k}\right\rfloor\right)\leq\sum_{k=1}^{\lfloor\ln_p(2n)\rfloor}1\leq\ln_p(2n).$$