# Prime number upper bound

I am reading some written notes about a proof I do not understand, maybe some informations are missing. The result that has to be proved is the following:

if $p_n$ is the $n$-th prime number, then $p_n \leq 2^{n^2}$.

The proof is by induction on $n$, the case $n=1$ is trivial. So suppose $n>1$. There is $i \in \mathbb{N}$ such that $$2^i \leq p_n \leq 2^{i+1}.$$ Then we consider a generic $m \leq p_n$, where $m=p_1^{\alpha_1} \cdots p_n^{\alpha_n}$ with $a_j \in \{0,1,\dots i\}$. Then (probably using the fact that there are $p_n$ naturals less or equal than $p_n$ and that $m$ is determined by $a_j$'s ??????) we get $$p_n \leq (i+1)^n$$...

[CUT]

How do we get this last inequality?

• Looks confusing to me indeed. – Peter Franek Jul 17 '14 at 20:04

What you write in parentheses is exactly the idea. Consider the set $S$ of natural numbers that can be written in the form $p_1^{\alpha_1}\cdots p_n^{\alpha_n}$ with each $\alpha_j \in \{0,1,\ldots,i\}$. Since each such expression is unique, this set is in bijection with the set of $n$-tuples $(\alpha_1,\ldots,\alpha_n)$ with each $\alpha_j \in \{0,1,\ldots,i\}$, of which there are $(i+1)^n$ elements. That is, $S$ has $(i+1)^n$ elements. However, every $m\leq p_n$ is in this set, as every $m \leq p_n$ can be written as a product of the primes $p_1,\ldots,p_n$. So $\{1,2,\ldots,p_n\} \subseteq S$, from which the inequality follows.