# How to show $p_n$ $\leq$ $2^{2^n}$?

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.

-
You could use the fact that if $p_1,\ldots,p_n$ are the first $n$ primes, then the $(n+1)$st prime is less than or equal to $p_1\cdots p_n + 1$ (Euclid's argument for the infinitude of primes). So, inductively, $p_{n+1}\leq 2^{2^1}\times\cdots\times 2^{2^n}+1 = 2^{2^1+\cdots+2^n}+1$. –  Arturo Magidin Sep 18 '11 at 23:32
It's worth pointing out that this is an incredibly crude bound. The prime number theorem states that $p_n$ is in fact approximately $n \log n \ll n^2 \ll 2^n \ll 2^{2^n}$. –  Chris Eagle Sep 18 '11 at 23:44
@Arturo: Typing my answer took longer than you typing you comment, but the idea is of course exactly the same as yours. –  TMM Sep 18 '11 at 23:46
@Thijs: Indeed; which is why I upvoted your answer. (-: –  Arturo Magidin Sep 18 '11 at 23:50

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 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} - 1$, 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} - 1} + 1 \leq 2^{2^{n+1}}$$

-

It is enough to prove that for any positive integer $n$, there are at least $n$ primes that are $\le 2^{2^n}$. We will show that in fact $2^{2^n}-1$ always has at least $n$ distinct prime divisors. (All of these are necessarily $<2^{2^n}$.)

Suppose we know that $2^{2^k}-1$ has at least $k$ distinct prime divisors. Then we must show that $2^{2^{k+1}}-1$ has at least $k+1$ distinct prime divisors.

Note that $$2^{2^{k+1}}-1=(2^{2^k}-1)(2^{2^k}+1).$$ The numbers $2^{2^k}-1$ and $2^{2^k}+1$ are relatively prime. This is because any number that divides both of them must divide their difference, which is $2$. But each of $2^{2^k}-1$ and $2^{2^k}+1$ is odd, so the greatest integer that divides both of them cannot be $2$, and therefore must be $1$.

Thus the prime divisors of $2^{2^{k+1}}-1$ are the prime divisors of $2^{2^k}-1$ (of which there are at least $k$), together with the prime divisors of $2^{2^k}+1$ (of which there is at least $1$), for a total of at least $k+1$.

Comment: The above argument also tells us that for any positive integer $n$, there are at least $n$ primes. This gives us a proof of the infinitude of the primes which is a little different from the usual "Euclid" proof.

-
(+1): very nice example how to make things simple - I think, the "least effort solution" :-) –  Gottfried Helms Sep 19 '11 at 6:36

Here we look at a smaller, and as I feel, more convenient bound:

Assume each prime would be the double of the previous, we had, beginning with the first prime q=2 the sequence $\small q, 2q, 4q, 8q, \ldots 2^n q , \ldots...$ and the n'th prime were bounded by $\small q2^n$ which is much smaller than the given $\small 2^{2^n}$ . Now if we recall that between n and 2n there is always a prime, thus the distance to the next is even smaller than n , then this is sufficient for the proof in general and we need only look at the initial cases for possible exceptions.

-
@Gottfried: The question seems more aimed at getting the student familiar with proof techniques (induction) than proving a sharp bound on the size of the $n$th prime. But indeed, one can improve the bound quite a bit ;-) –  TMM Sep 19 '11 at 1:19
@Thijs: Well, I was thinking just in that path of an exercise for proofs (and Bertrand's postulate seemed to me to be the elementary knowledge here). But possibly I'm too far away from the actual courses to have an appropriate intuition. So if I was obfuscating here, I'll apologize to the OP... –  Gottfried Helms Sep 19 '11 at 6:29