# Upper Bounds for Prime Numbers/Result 1

## Theorem

Let $p: \N \to \N$ be the prime enumeration function.

Then $\forall n \in \N$, the value of $\map p n$ is bounded above.

In particular:

$\forall n \in \N: \map p n \le 2^{2^{n - 1} }$

## Proof

Proof by strong induction:

Let us write $p_n = \map p n$.

For all $n \in \N_{>0}$, let $\map P n$ be the proposition:

$\map p n \le 2^{2^{n - 1} }$

### Basis for the Induction

$\map P 1$ is true, as this just says $2 \le 2^{2^0} = 2$.

This is our basis for the induction.

### Induction Hypothesis

Suppose that, for some $k \in \N$, each of $\map P 1, \map P 2, \ldots, \map P k$ is true.

It remains to show that it logically follows that $\map P {k + 1}$ is true.

That is, that:

$\map p {k + 1} \le 2^{2^k}$

This is our induction hypothesis.

### Induction Step

This is our induction step:

 $\ds \map p {k + 1}$ $\le$ $\ds p_1 p_2 \cdots p_k + 1$ Euclid's Theorem $\ds$ $\le$ $\ds 2 \times 2^2 \times 2^{2^2} \times \cdots \times 2^{2^{k - 1} } + 1$ Induction Hypothesis $\ds$ $=$ $\ds 2^{1 + 2 + 2^2 + 2^3 + \cdots + 2^{k - 1} } + 1$ Exponent Combination Laws $\ds$ $=$ $\ds 2^{2^k - 1} + 1$ Sum of Geometric Sequence $\ds$ $\le$ $\ds 2^{2^k - 1} + 2^{2^k - 1}$ since $1 \le 2^{2^k - 1}$ for all $k$ $\ds$ $=$ $\ds 2^{2^k}$

The result follows by the Second Principle of Mathematical Induction.

$\blacksquare$

## Note

It can be seen that the limit found is wildly extravagantly large.

However, it is an easily established result, and it has its uses.