Limit on nth Prime

Theorem
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}\]

Add comment

Security code
Refresh