Why is $n^{\pi (2)− \pi ()} ≤ {2 \choose }$?

273 Views Asked by At

A follow-up from a previous question I asked: if $\pi ()$ counts the number of primes less than or equal to $n$ and $M = \pi (2 n)− \pi (n)$, i.e. the number of primes greater than $n$ but less than or equal to $2n$, then how can we explain why

$$n^{\pi (2n)− \pi (n)} \leq {2 \choose } ?$$

1

There are 1 best solutions below

3
On BEST ANSWER

You need that for any prime $p$ with $n<p\leq 2n,$ you have that $p\mid \binom{2n}{n}.$

Since there are $\pi(2n)-\pi(n)$ distinct such primes, their product is more than $n^{\pi(2n)-\pi(n)}.$ But the product of these primes must divide $\binom{2n}{n}.$ So:

$$n^{\pi(2n)-\pi(n)}\leq \prod_{n<p\leq 2n} p\mid \binom{2n}{n}$$