Let $p_n$ be the $n_{th}$ prime (e.g. $p_1 = 2$; $p_2 = 3$; $p_3 = 5$). Show that $p_n \leq 2^{2^n}$ for all $n$.
I don't see how I can approximate the value of $p_n$. Do I need something like prime number theorem? But the course didn't even teach that yet.
Best Answer
The idea is that you use induction, and that you expand on Euclid's argument that there are infinitely many primes to show that $p_n$ is bounded above by $2^{2^n}$.
Suppose $p_i \leq 2^{2^i}$ for all $i \leq n$. Now $p_1 \cdot p_2 \cdot \ldots \cdot p_n + 1$ is not divisible by any of the primes $p_1, \ldots, p_n$, so
$$p_{n+1} \leq \prod_{i=1}^n \ p_i + 1$$
Substituting the earlier bounds on $p_i$ and using $\sum_{i=1}^n 2^i = 2^{n+1} - 2$, we get
$$p_{n+1} \leq \left(\prod_{i=1}^n \ 2^{2^i}\right) + 1 = \left(2^{\sum_{i=1}^n 2^i}\right) + 1 = 2^{2^{n+1} - 2} + 1 \leq 2^{2^{n+1}}$$