Demostrando que $\pi(2n) < \pi(n)+\frac{2n}{\log_2(n)}$

Question

Dado que $\pi(x)$ es la función de recuento de primos, demuestre que, para $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}$

Para $x\geq8$ un número real, demuestre que

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

Entiendo que debería mostrar lo que he probado, pero no tengo ni idea de qué hacer a continuación. Lo único que sé sobre esta función es el teorema de los números primos, pero no veo cómo podría ayudarme aquí.

Lo extraño es que esta pregunta formaba parte de un examen de la olimpiada nacional, lo que sugiere que esto puede resolverse con matemáticas elementales.

¿Alguien sabe si esto se puede resolver fácilmente, sin entrar en matemáticas demasiado avanzadas? Se preferirían las pistas a las soluciones completas.

La pregunta proviene de la Olimpiada Matemática Irlandesa de 1989.

Answer 1

Observamos que $$\binom{2n}{n} \le 4^n$$ y es divisible por todos los primos tales que $n < p < 2n$ .

Demostrar que si $n \ge 3$ es un número entero, entonces $$\pi(2n) < \pi(n) + {{2n}\over{\log_2(n)}}.$$

$\pi(2n) - \pi(n)$ es el número de primos tales que $n < p < 2n$ . Si hay $k$ tales primos, tenemos la desigualdad $$n^k \le 4^n \implies k < {{2n}\over{\log_2 n}} \implies \pi(2n) < \pi(n) + {{2n}\over{\log_2n}}.$$

Demostrar que si $n \ge 3$ es un número entero, entonces $$\pi(2^n) < {{2^{n+1}\log_2(n-1)}\over{n}}.$$

Procedemos por inducción. Caso base $n = 3$ es trivial de comprobar. Tenemos $$\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}}.$$ Probemos $${{2^{n+1}\log_2(n-1)}\over{n}} + {{2^{n+1}}\over{n}} \le {{2^{n+2} \log_2 n}\over{n+1}}.$$ Dividiendo $2^{n+1}$ y quitando el $\log_2$ da $$(2n-2)^{n+1} \le n^{2n},$$ lo cual es cierto ya que $$4n \le (n+1)^2 \text{ and } n \le 2^n.$$

Deducir que, para todos los números reales $x \ge 8$ , $$\pi(x) < {{4x \log_2(\log_2(x))}\over{\log_2(x)}}.$$

Dejemos que $$n=\lfloor\log_2x\rfloor.$$ Entonces $$n \le \log_2x <n+1.$$ Por lo tanto, $$\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},$$ como se desee.