# Proving that $\pi(2n) < \pi(n)+\frac{2n}{\log_2(n)}$

Given that $\pi(x)$ is the prime-counting function, prove that, for $n\geq 3$,

1: $\pi(2n) < \pi(n)+\frac{2n}{\log_2(n)}$

2:$\pi(2^n) < \frac{2^{n+1}\log_2(n-1)}{n}$

For $x\geq8$ a real number, prove that

$\pi(x) < \frac{2x\log_2(\log_2(x)}{\log_2(x)}$.

I understand that I should show what I've tried, but I have no idea what to do next. The only thing I know about this function is the prime number theorem, but I don't see how that could help me here.

What's strange is that this question was part of a national olympiad exam, suggesting this can be solved using elementary mathematics.

Does anyone know if these can be solved easily, without going into too advanced mathematics? Hints would be preferred over full solutions.

Question comes from 1989 Irish Mathematical Olympiad.

## 1 Answer

We note that$$\binom{2n}{n} \le 4^n$$and is divisible by all primes such that $n < p < 2n$.

Prove that if $n \ge 3$ is an integer, then$$\pi(2n) < \pi(n) + {{2n}\over{\log_2(n)}}.$$

$\pi(2n) - \pi(n)$ is the number of primes such that $n < p < 2n$. If there are $k$ such primes, we have the inequality$$n^k \le 4^n \implies k < {{2n}\over{\log_2 n}} \implies \pi(2n) < \pi(n) + {{2n}\over{\log_2n}}.$$

Prove that if $n \ge 3$ is an integer, then$$\pi(2^n) < {{2^{n+1}\log_2(n-1)}\over{n}}.$$

We proceed by induction. Base case $n = 3$ is trivial to check. We have$$\pi(2^{n+1}) < \pi(2^n) + {{2^{n+1}}\over{n}} < {{2^{n+1}\log_2(n-1)}\over{n}} + {{2^{n+1}}\over{n}}.$$Let us prove$${{2^{n+1}\log_2(n-1)}\over{n}} + {{2^{n+1}}\over{n}} \le {{2^{n+2} \log_2 n}\over{n+1}}.$$Dividing $2^{n+1}$ and taking off the $\log_2$ gives$$(2n-2)^{n+1} \le n^{2n},$$which is true since$$4n \le (n+1)^2 \text{ and } n \le 2^n.$$

Deduce that, for all real numbers $x \ge 8$,$$\pi(x) < {{4x \log_2(\log_2(x))}\over{\log_2(x)}}.$$

Let$$n=\lfloor\log_2x\rfloor.$$Then$$n \le \log_2x <n+1.$$Therefore,$$\pi(x) \le \pi(2^{n+1}) \le \frac{2^{n+2}\log_2n}{n+1} \le \frac{4x \log_2(\log_2x)}{\log_2x},$$as desired.