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.

  • $\begingroup$ $$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. $\endgroup$ – Mr Pie Sep 10 '17 at 5:09
  • 3
    $\begingroup$ $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}.$ $\endgroup$ – 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.

  • $\begingroup$ 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? $\endgroup$ – sequence Sep 10 '17 at 5:54
  • 1
    $\begingroup$ @sequence $2^1=10, 2^2=100, 2^3=1000, 2^4=10000...$. Summing them all is like $1111....1110$. $\endgroup$ – Joao Noch Sep 10 '17 at 6:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.