Upper Bounds for Prime Numbers/Result 3

Theorem

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

Then $\forall n \in \N$, the value of $p \left({n}\right)$ is bounded above.

In particular:

$\forall n \in \N_{>1}: p \left({n}\right) < 2^n$

Proof

Let us write $p_n = p \left({n}\right)$.

From Bertrand's Conjecture, for each $n \ge 2$ there exists a prime $p$ such that $n < p < 2 n$.

For all $n \in \N_{>0}$, let $P \left({n}\right)$ be the proposition:

$p_n < 2^n$

$P(1)$ is the statement:

$p_1 = 2 = 2^1$

As this does not fulfil the criterion:

$p \left({n}\right) < 2^n$

it is not included in the result.

Basis for the Induction

$P(2)$ is true, as this just says:

$p_2 = 3 < 2^2 = 4$

This is our basis for the induction.

Induction Hypothesis

Now we need to show that, if $P \left({k}\right)$ is true, where $k \ge 2$, then it logically follows that $P \left({k+1}\right)$ is true.

So this is our induction hypothesis:

$p_k < 2^k$

Then we need to show:

$p_{k+1} < 2^{k+1}$

Induction Step

This is our induction step:

Suppose that $p_k < 2^k$ for some $k \ge 2$.

By Bertrand's Conjecture, there exists a prime $q$ such that $2^k < q < 2^{k+1}$.

So:

$p < 2^k < q < 2^{k+1}$

But as $q$ is a prime exceeding $p_k$, it means:

$p_{k+1} \le q < 2^{k+1}$

So $P \left({k}\right) \implies P \left({k+1}\right)$ and the result follows by the Principle of Mathematical Induction.

Therefore:

$\forall n \in \N_{>1}: p \left({n}\right) < 2^n$

$\blacksquare$