$(n+1)^{\textrm{st}}$ prime less than $2^{2^n}$

Question

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$?

Answer 1

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) $$

Answer 2

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.