Prove there are more than $n$ prime numbers $p \leq x$ for $x \geq 3$.

Question

Let $x$ be greater than or equal to $3$. Prove there are more than $\frac {\ln(\ln(x))}{\ln 2}$ prime numbers $p \leq x$.
Hint: use Euclid's proof and induction.

I have run across this question in a book on L-functions that I am reading. I am only at the beginning of the book and this is the first exercise. So far I have been able to understand everything without difficulty, but I have no idea how I am supposed to approach this problem. If someone can help out I will greatly appreciate it.

Answer 1

$\frac {\ln(\ln(x))}{\ln 2} = \log_2 (\ln x)$

Euclid's proof.

There are infinitely many prime numbers

Proof:

Suppose there are finitely many.

$P={p_1,p_,\cdots,p_n}$ is the set of prime numbers.

Multiply together all the elements in P. subtract 1. Either this number is prime. Or it has a prime factor that is not in $P.$

How to apply it to what we have here.

Since each $p_n < x$

If there are $n$ prime numbers less than or equal to $x$

There are at least $n+1$ prime numbers less than or equal to $x^n$

There are $2$ prime numbers less than or equal to $2^2$

$\log_2(\ln(2^2) = \log_2 2 + \log_2 \ln 2\\ \log_2 \ln 2 < 0\\ 1 + \log_2 ln 2 < 2$

There are $3$ at least prime numbers less than or equal to $(2^3)$

$2(2^2) = 2^3$

$\log_2(\ln(2^3)) = \log_2 3 + \log_2\ln 2 < 3 $

I say: There are at least $n$ prime numbers less than or equal to $2^{2^{n}}$

The base case is sufficiently covered.

Suppose for all $k\le n$ there are at least $k$ prime numbers $< 2^{2^{k}}$

Then we must show there are least n+1 prime numbers $< 2^{2^{n+1}}$

If there are exactly $n$ prime numbers numbers $\le 2^{2^{n}}$

Then we can multiply them all all together. There will be a prime number less the product will be less than $\prod_\limits{k=1}^{n} 2^{2^k} = 2^{\sum 2^k} = 2^{2^{n+1}-1}<2^{2^{n+1}}$

There are at least $n+1$ less than $2^{2^{n+1}}$

$\log_2 \ln 2^{2^{n+1}} = (n+1) + \log_2 \ln 2 < n+1$

For any $x\ge 2^2$ there are at least $\log_2 \ln x$ prime numbers less than $x.$

Which still leaves one case left to show $x = 3$