If
\[p_n\]
is the nth prime number then \[p_n \le 2^{2^{n-1}}\]
Proof
Let
\[P(n)\]
be the statement of the theorem. \[P(1)\]
is true since \[p_1 =2 \le 2^{2^{1-1}}=2\]
.Suppose
\[P(n)\]
is true for \[n=1, \; 2, \; 3...,k\]
. We must prove \[P(k+1)\]
is true. \[p_{k+1} \le p_1p_2...p_k+1\]
by Euclid's Theorem.\[p_{k+1} \le p_1p_2...p_k+1 \le 2^{2^{1-1}}2^{2^{2-1}}...2^{2^{k-1}}+1\]
by the induction hypothesis.\[p_{k+1} \le 2^(1+2+4+8+...+2^{k-1})+1=2^{2^k-1}+1 \le 2^{2^k}\]