$(n+1)^{\textrm{st}}$ prime less than $2^{2^n}$ Using elementary means, show that the $(n+1)^{\textrm{st}}$ prime is less than $2^{2^n}$
please do not use fancier stuff like the prime number theorem or beyond.
using this how can you show that $\pi(x) \geq \log\log(x)$ for $x \geq2$?
 A: Using an induction approach:
the first prime is $2 \le 2^{2^1}=4$.
If the $k$th prime is, for $k < n$, $p_k\le 2^{2^k}$:
the smallest prime divisor of the number $2\times \dots\times p_{n-1} + 1$ is none of
$p_k,k <n$. Then it is a certain $p \ge p_n$.
So $$
p_n \le p \le 2\times \dots\times p_{n-1} \le 1 + \prod_{k=1}^{n-1} 2^{2^k}
= 1 +  2^{\sum_{k=1}^{n-1} 2^k} = 1 + 2^{2 (2^{n-1} - 1)} \le 2^{2^n}
$$
For the second one: an immediate consequence of the is, with $\log_2$ being the logarithm in  base 2, is
$$
\pi(n) \le \log_2(\log_2 n)
$$
A: Proof by Induction
Let the $(n+1)^{st}$ prime be $P(n)$, and $2^{2^n}$ be $T({n})$.
Base Case: can be illustrated by plugging in the first couple values.
  n  -> | 0 | 1 | 2 | 3 
P(n) -> | 2 | 3 | 5 | 7 
2^2^n-> | 2 | 4 | 16|256

Notice: The property only holds for $n\ge1$.
Induction step: Given that $P(t)<2^{2^n}$ for $t=\{1,2,...,n-1\}$, we'd like to show that $P(n) < 2^{2^n}$.
Consider $X_p$ to be the product of all previous primes plus 1: 
$$X_p = 1+ \Pi^{n-1}_1 P(i) =1+ (2 \times 3 \times 5 \times ... \times P(n-1))$$
No previous prime can divide $X_p$ because it is one more than a multiple of every previous prime. Therefore if no other primes exist within $(P(n-1),X_p]$ then $X_p$ would be the next largest prime. So whatever $P(n)$, it is at most $X_p$. $P(n) \le X_p$.
Consider $X_2$ to be the product of all previous values of $2^{2^n}$ plus 1: 
$$X_2
=1+\Pi^{n-1}_1 2^{2^i}
=1+2^{(2^1 + 2^2 + 2^3 +...+ 2^{n-1})}
=1+2^{(2^n-1)}\le2^{2^n}$$
Remember now that for $i \in {1,2,...,n-1}$
$$P(i)<2^{2^i}$$
therefore
$$1+\Pi^{n-1}_1 P(i) < 1+\Pi^{n-1}_1 2^{2^i} \implies X_p \le X_2$$
and thus we have
$$ P(n) \le X_p < X_2 \le 2^{2^n} $$
and our induction step is complete.
