# $(n+1)th$ prime $p_{n+1}$ less than or equal to $p_1p_2\dots p_n+1$

I'm trying to understand some particulars of the following proposition:

First, let me write down the theorem on which the subsequent proposition relies.

Theorem. (Euclid). There are infinitely many primes.

Proof: Suppose that there are finitely many primes, say, $p_1, p_2, \dots, p_n$. Consider $$m=p_1 p_2 \dots p_n$$ Consider $$m=p_1 p_2 \dots p_n+1\ge 2$$

By the Fundamental Theorem of Arithmetics, $m$ is a product of primes. Thus $p_k \vert m$ for some $1\le k \le n$. Since $p_k\vert m$ and $p_k\vert p_1 p_2 \dots p_n$, we have that $p_k \vert (m-p_1 p_2 \dots p_n)$, i.e. $p_k\vert 1$, which leads to a contradiction. Thus there are infinitely many primes.



Proposition: For $n\in\mathbb{N}$, we have $p_n\le 2^{2^n}$, where $p_n$ is the $n-$th prime number. The proof by induction goes as follows. For $k=1$, we have $p_1 = 2\le 2^2=4$. Suppose that the result holds for $1\le k \le n$ . We have seen in the proof of the Theorem above that

$$p_{n+1}\le p_1p_2\dots p_n+1$$

Thus, by our induction hypothesis,

$$p_{n+1}\le 2^{2^1} 2^{2^2}\dots 2^{2^n}+1=2^{2^{n+1}-2}+1\le 2^{2^{n+1}}$$

By induction, proposition holds.

What I don't seem to get is how it follows from the Theorem above that $$p_{n+1}\le p_1p_2\dots p_n+1$$ Moreover, how can one immediately see (other than by proof by induction) that $2^1 + 2^2 + \dots + 2^n = 2^{n+1}-2$?

Would appreciate some clarifications.

• $$2^{n + 1} - 2 = 2(2^n - 1)$$ $$\implies \frac{2^1 + 2^2 +\cdots+ 2^n}{2} = 2^n - 1$$ $$\implies \frac{2^1}{2} + \frac{2^2}{2} +\cdots+\frac{2^n}{2} = 2^n - 1$$ $$\implies 1 + 2^1 + 2^2 +\cdots+2^{n - 1} = 2^n - 1$$ $$\implies 2^1 + 2^2 +\cdots+2^{n - 1} = 2^n - 2$$ $$\implies 2^1 + 2^2 +\cdots+2^{n - 1} = 2(2^{n - 1} - 1)$$ And so proposition holds. – Mr Pie Sep 10 '17 at 5:09
• $2^1+2^2+\cdots+2^n$ is a geometric series with first term $2$ and common ration also $2$. Then $S_n=\frac {a(r^n-1)}{r-1}.$ – Error 404 Sep 10 '17 at 5:31

To see that $p_{n+1}\le p_1p_2\dots p_n+1$, note that $p_1p_2\dots p_n+1$ must have a prime factor, but it cannot be any of $p_1, p_2, \dots, p_n$ by the same argument as in the proof. So any prime factor of $p_1p_2\dots p_n+1$ must be a new prime number less than or equal to $p_1p_2\dots p_n+1$. Therefore, the smallest prime larger than $p_n$ can be at most $p_1p_2\dots p_n+1$.
As for why $2^1 + 2^2 + \dots + 2^n = 2^{n+1}-2$, write it in binary.
• I'm not sure how to write $2^1+2^2+\dots+2^n=2^{n+1}-2$ in binary. Would you please show this? – sequence Sep 10 '17 at 5:54
• @sequence $2^1=10, 2^2=100, 2^3=1000, 2^4=10000...$. Summing them all is like $1111....1110$. – Joao Noch Sep 10 '17 at 6:04