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$
Motivation
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$