Show that $\pi(n) \geq \log_2\log_2 2n$ Doing some excercise on elementary number theory I have proved that for every $n \in \Bbb{N}, p_{n+1} \leq p_1p_2...p_n + 1$, based on this result I'm also was able to prove that for every $n \in \Bbb{N}, p_{n} < 2^{2^n}$. Based on this I have now to show that for every $n \in \Bbb{N}, \pi(n) \geq \log_2\log_2 2n$, where $\pi$ is prime counting function. Here is what I tried.
In order to $r=\log_2\log_2 2n$ be in $\Bbb{N}$, let $n=2^m, m \in N$. Then I got $r=log_2\log_2 2(2^m)=\log_2\log_2 2^{m+1}=\log_2 m+1$. Once again, let $m=2^r - 1$, then $r=\log_2 {(2^r-1) + 1}=\log_2 2^r=r$. Substituting $m$ to $n$ I have $n=2^{2^r-1}$, and initial inequality becomes $\pi(2^{2^r-1}) \leq r=\log_2\log_2{2^{2^r}}$.
From this point, If I consider prime $p_r$, it's true that $\pi(2^{2^r}) \geq r$, because it's already proven that $p_{r} < 2^{2^r}$, so there is an $r_{th}$ prime between $1$ and $2^{2^r}$. But I can't figure out why it's also true for $\pi(2^{2^r-1})$. And that's where I stuck and need some help.
Thank you in advance!
 A: You can be able to obtain a stricter bound for $\pi (x)$ since the Prime Number Theorem states that:
$$\lim_{x \to \infty} \frac{\pi (x)}{x/\log(x)}=1$$
But to obtain a lower bound different from this huge theorem is not so hard. You can use Bertrand's postulate to get a lower bound. There is an elementary proof for this postulate, you can get the "$\textbf{idea}$" of the proof on Wikipedia. Now by Bertrand's postualate:
$$\pi (n) -\pi \left(\left\lfloor\frac{n}{2}\right\rfloor\right) \geq 1$$
$$\pi \left(\left\lfloor\frac{n}{2}\right\rfloor\right)-\pi \left(\left\lfloor\frac{n}{4}\right\rfloor\right) \geq 1$$
$$...$$
$$\pi (2) - \pi (1) \geq 1$$
Now since there are $\left\lfloor \log_2 n\right\rfloor$ terms, add them together, we obtain:
$$\pi (n) \geq \log_2 n$$
The rest which is to prove $\log_2 n \geq \log_2 \log_2 2n$ is obvious since $n \geq \log_2 2n$ can be proved by induction and take logarithm to the desired inequality.
A: If we choose $n = p_{k+1} - 1$, we see that for $\pi(n) \geqslant \log_2 \log_2 (2n)$ to hold for all $n$ we must have
$$p_{k+1} \leqslant 1 + 2^{2^k-1}$$
for all $k$. Unfortunately I don't see a nice induction for that using
$$p_{n+1} \leqslant p_1p_2\cdot \ldots \cdot p_n + 1\,, \tag{1}$$
thus I'll do something more ugly and prove
$$p_k < 2^{2^{k-1} - 1} \tag{2}$$
for $k \geqslant 3$ using $(1)$ and $p_1 = 2, p_2 = 3$.
The base case is immediate,
$$p_3 \leqslant 2\cdot 3 + 1 = 7 < 8 = 2^3 = 2^{2^2 - 1}\,.$$
Then in the induction step for $n \geqslant 3$ we have
$$p_{n+1} \leqslant 1 + \prod_{k = 1}^{n} p_k < 1 + 2\cdot 3 \cdot \prod_{k = 3}^{n} 2^{2^{k-1} - 1} < 2^3\cdot 2^{2^{n} - 4 - (n-2)} < 2^{2^n-1}\,.$$
And then, for $n \leqslant 8$ we verify $\pi(n) \geqslant \log_2 \log_2 (2n)$ by inspection, for $n > 8$ we choose $k$ such that
$$2^{2^{k-1} - 1} < n \leqslant 2^{2^k - 1}\,.$$
Then $k \geqslant 3$, and by $(2)$ we have
$$\pi(n) \geqslant k = \log_2 \log_2 \bigl(2^{2^k}\bigr) \geqslant \log_2 \log_2 (2n)\,.$$
Not pretty, and that for a ridiculously weak lower bound :(
