# 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.

## Sources

- 1982: P.M. Cohn:
*Algebra Volume 1*(2nd ed.) ... (previous) ... (next): $\S 2.2$: Divisibility and factorization in $\mathbf Z$: Exercise $7$