Let $ \pi(n)$ be the number of primes less or equal to n.

Show that

$$
n^{\pi(2n)-\pi(n)}

Question

Let $ \pi(n)$ be the number of primes less or equal to n.

Show that

$$
 n^{\pi(2n)-\pi(n)}<4^{n}

$$

anonymous · Answer

What can we use as the basis for our proof? May we assume PNT?

anonymous · Answer

You can if you want. There is an elementary proof of it not involving the PNT

anonymous · Answer

The PNT is for large enough n. Here one has to prove the inequality fo each n.

anonymous · Answer

If there's an elementary proof, I have no idea how to start this... will think over it, for tomorrow... seems pretty interesting.

anonymous · Answer

*

anonymous · Answer

Hint
$$
(1+1)^{2n}=4^n
$$

anonymous · Answer

$$
4^n=(1+1)^{2n}> {2n \choose n}
$$

anonymous · Answer

oh very nice

for   $n\le p_k\le 2n$

$$\prod p_k  | \frac{(n+1)(n+2)...(2n)}{n!}={2n \choose n} \Rightarrow\prod p_k <{2n \choose n}$$$$n^{\pi(2n)-\pi(n)}< \prod p_k<\binom{2n}{n}< 2^{2n}=4^{n} $$

anonymous · Answer

Bah, humbug, you got me... but you were right, there *was* a nice proof! Figured it out sometime earlier during class.