Show that $\pi\left(n\right)\geq\log_{2}\left(\log_{2}\left(n-1\right)\right)$ I need to show that
$$
\pi\left(n\right)\geq\log_{2}\left(\log_{2}\left(n-1\right)\right)
$$ 
where $\pi\left(n\right)=\left|\left\{ p\mid p\text{ is prime and }p\leq n\right\} \right|$
Now i somehow think it is related with Fermat Numbers as we saw them
in class and because it is sufficient to show that
$$
F_{\pi\left(n\right)}:=2^{2^{\pi(n)}}+1\geq n
$$
But i'm not sure how to do it. any help?
Thanks in advance
 A: Let $p_1,p_2,p_3,\ldots$ be the increasing sequence of prime natural numbers.  Without Bertrand's Postulate, you can show that $p_{n+1}\leq p_1p_2\cdots p_n+1$ for every positive integer $n$.  By induction, 
$$p_{n} \leq 2^{2^{n-1}}$$
for every positive integer $n$ (and the equality holds iff $n=1$).
Now, for a fixed real number $x>2$, let $k:=\pi(x)$.  Then, we see that $x<p_{k+1} \leq p_1p_2\cdots p_k+1$, or
$$x-1<p_1p_2\cdots p_k\leq 2^{2^0}\,2^{2^1}\,\cdots \,2^{2^{k-1}}=2^{2^k-1}<2^{2^k}\,.$$
That is,
$$\pi(x)=k>\log_2\big(\log_2(x-1)\big)\text{ for all }x>2\,.$$
In fact, if Bertrand's Postulate is used, then we have $p_n\leq 2^{n-1}$ for all $n\geq 4$.  Thus, for any real number $x\geq 5$, we have
$$x<p_{k+1}\leq 2^k\,,$$
where $k:=\pi(x)\geq 3$.  That is,
$$\pi(x)=k>\log_2(x)\text{ for all }x\geq 5\,.$$
A: A useful estimate is $$2^{\pi(n)}≥ \sqrt n$$
Proof:  every natural number less than $n$ can be written uniquely as $$m^2\prod p_i^{\epsilon_i}$$
where the product is taken over all the primes $≤n$ and $\epsilon_i\in \{0,1\}$.  There are $\sqrt n$ possible choices for $m$ and at most $2^{\pi(n)}$ ways to choose the $\epsilon's$.
That inequality is stronger than what you want, at least for large $n$.  Indeed. it implies at once that $$\pi(x)≥\frac 12\times \log_2 x$$  and $$\frac 12\times \log_2 n>\log_2 (\log_2(n-1))$$  at least for $n>11$.
A: Enumerate the primes as $p_1,p_2,\dots$. If $n=p_1p_2\cdots p_k+1$, then $n$ is not divisible by any of the primes $p_1,\dots,p_k$. But $n$ is divisible by some prime. In particular, we have $p_{k+1}\leq 1+\prod_{i=1}^k p_i$ for all $k$. Now show by induction that this means $p_n\leq 2^{2^{n-1}}$.
