Upper Bounds for Prime Numbers/Result 1

From ProofWiki
Jump to navigation Jump to search

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

Retrieved from "https://proofwiki.org/w/index.php?title=Upper_Bounds_for_Prime_Numbers/Result_1&oldid=601553"