# 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.

-
+1 for showing your thoughts about the problem - you are an exemplary new user! Welcome to math.SE! –  Zev Chonoles Nov 16 '11 at 5:30
More -and similar- answers may be found at the much related question from about two monthes ago at MSE: math.stackexchange.com/questions/65630 –  Gottfried Helms Nov 16 '11 at 7:43
Is there a thing as primes in descending order. –  orlp Nov 16 '11 at 10:04

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

-
The key idea of Andre's proof was to give a canonical bound on $p_{k+1}$. The way to think about this is "you're trying to find an integer which will have for sure a new prime factor". One way to do this is to make sure it is not divisible by all the previous one, hence the choice $(p_1 \cdots p_k) + 1$. –  Patrick Da Silva Nov 16 '11 at 5:41
I feel like I'm missing something with the math here. The sum of that geometric sequence would be (2^k)-1? Thus giving me the result p_k+1 <= 2^(2^k)-1 + 1, from my understanding. –  Ryan Wilkins Nov 16 '11 at 5:55
@Ryan Wilkins: It gives the result that $(p_1p_2\cdots p_k)+1\le 2^{2^k}$. But recall that $(p_1p_2\cdots p_k)+1$ has at least one prime factor different from the $p_i$. That gives a total of at least $k+1$ primes $\le 2^{2^k}+1$. –  André Nicolas Nov 16 '11 at 6:38

The other way to prove this inequality is to use Bertrand's postulate .

So we have to prove that :

$p_{k+1} \leq (p_k)^2\leq2^{2^k}$

By the Bertrand's postulate we know that :

$p_{k+1} \in (p_k , 2p_k)$ so we have to show that $(p_k)^2 \geq 2p_k$

Let's denote $n=p_k$

$n^2-2n\geq 0 \Rightarrow n\geq 2 \Rightarrow p_k\geq 2$

So for all primes greater or equal to $2$ it is true that $(p_k)^2 \geq 2p_k$

Therefore we may conclude that :

$p_{k+1} \leq (p_k)^2\leq2^{2^k} \Rightarrow p_{k+1} \leq 2^{2^k}$

-
I nearly put this as an answer but thought it was overkill to use such an advanced result for something that can be solved using more elementary methods. –  Rankeya Nov 16 '11 at 6:21