Proof involving induction and primes

I'm looking to prove that:

$$p_n \leq 2^{2^{n-1}}$$

Where $p_n$ denotes the $n$th prime in ascending order. The proof method is induction. I've solved my base case, that is: $n=1$ $p_1 = 2$, $2^{2^0}=2$, $2\leq2$ Therefore $P(1)$ is true.

And the induction hypothesis is that $P(1), P(2),\ldots P(k)$ is true for some integer $k$.

I'm stuck trying to prove $P(k+1)$, or $p_{k+1} \leq 2^{2^k}$

The closest I have come was rewriting $2^{2^k}$ as $(2^{2^{k-1}})^2$, which is the square of the value of $P(k)$. My guess at the moment is that if I can prove that a prime is strictly less then the square of the previous prime then my proof would be complete, but I can't seem to do so.

Thanks in advance for help.

Solution 1:

We give two proofs. The first is probably the intended one. The second is perhaps more interesting, and certainly more informative. For one thing it shows that there are infinitely many primes in a way quite different from the standard proof that goes back to Euclid's Elements.

First proof: Note that $p_{k+1}\le (p_1p_2\cdots p_k)+1$, since some prime $p$ divides $(p_1p_2\cdots p_k)+1$, and $p$ cannot be any of $p_1,p_2,\dots,p_k$. Now use the induction hypothesis. We have $p_1p_2\cdots p_k\le 2^{e_k}$ where $$e_k \le 2^0 +2^1+\cdots +2^{k-1}.$$ The series on the right is a geometric series with sum $2^k-1$. So $p_1p_2\cdots p_k <2^{2^k}$, and therefore $(p_1p_2\cdots p_k)+1 \le 2^{2^k}$.

Second proof: Let $n \ge 1$. We will show that $2^{2^n}-1$ has at least $n$ distinct prime factors. None of these prime factors is equal to $2$. So there are at least $n+1$ primes that are $\le 2^{2^n}$.

We prove that $2^{2^n}-1$ has at least $n$ prime factors by induction on $n$. Suppose that we know that for a particular $k\ge 1$, there are at least $k$ primes that divide $2^{2^k}-1$. We want to show that there are at least $k+1$ primes that divide $2^{2^{k+1}}-1$.

We use the familiar factorization (difference of two squares) $$2^{2^{k+1}}-1=(2^{2^k} -1)(2^{2^k} +1).$$ By the induction hypothesis, $2^{2^k} -1$ has at least $k$ prime factors. Let $p$ be a prime factor of $2^{2^k}+1$. Then $p$ cannot divide $2^{2^k} -1$, since if it did, it would divide the difference $(2^{2^k} +1)-(2^{2^k} -1)$, which is $2$. But since $2^{2^k}+1$ is odd, $p$ must be odd. So in addition to the $k$ prime factors of $2^{2^k} -1$, the number $2^{2^{k+1}} -1$ has at least one additional prime factor $p$, for a total of at least $k+1$.

Comment: The formal induction hides the simplicity of the idea. It all comes down to the fact that, for example, $$2^{2^5}-1=(2^{2^1}-1)(2^{2^1}+1)(2^{2^2}+1)(2^{2^3}+1)(2^{2^4}+1).$$