Section 3.2 Number of Primes
Definition 3.2.1.
An integer \(\vert n\vert \gt 1\) is composite provided it is not prime.
Theorem 3.2.2.
If \(p_n\) is the \(n\)th prime number, then \(p_n\leq 2^{2^{n-1}}.\)
Proof.
By induction. If \(n = 1,\) then
\begin{equation*}
p_1 = 2\leq 2^{2^{0}}=2.
\end{equation*}
Now assume that the theorem is true for all natural numbers less than \(n.\) Then, by the proof above,
\begin{equation*}
p_{n+1}\leq p_1p_2...p_n+1\leq 2\cdot 2^2...2^{2^{n-1}}+1=2^{1+2+2^2+...+2^{n-1}}+1.
\end{equation*}
Let us remember the identity that \(1+2+2^2+...+2^{n-1}=2^n-1.\) This gives
\begin{equation*}
p_{n+1}\leq 2^{2^n-1}+2^{2^n-1}=2\cdot 2^{2^n-1}=2^{2^{n}},
\end{equation*}
so that by induction we have the desired result.
Corollary 3.2.3.
There are at least \(n + 1\) primes less than \(2^{2^{n}}\)