What follows is Erdős’ elegant proof of Bertrand’s postulate that builds upon two previous analyses I have shared on my blog:

  1. A few interesting results on p-adic orders

  2. Interesting properties of the Chebyshev functions

Given those analyses, we may use the following lemmas:

Lemma 1:

\begin{equation} \forall n \in \mathbb{N}^*, {2n \choose n} \geq \frac{4^n}{2n+1} \end{equation}

Lemma 2:

\begin{equation} \forall p \in \mathbb{P}, \frac{2n}{3} < p \leq n \implies v_p\big({2n \choose n}\big) = 0 \end{equation}

Lemma 3:

\begin{equation} v_p \big({2n \choose n}\big) \geq 1 \implies v_p \big({2n \choose n}\big) \leq \log_p (2n) \end{equation}

Lemma 4:

\begin{equation} e^{\vartheta(n)} \leq 4^n \end{equation}

Proof of Bertrand’s postulate:

Bertrand’s postulate may be verified algorithmically for \(n \leq 467\).

For \(n \geq 468\), we may proceed with a proof by contradiction. Let’s assume that there is no prime \(p, n < p \leq 2n\).

Given that \({2n \choose n}\) has at most \(\sqrt{2n}\) prime factors smaller than \(\sqrt{2n}\), we may draw two inferences from Lemma 3:

\(1.\) The contribution of each of those factors to \({2n \choose n}\) does not exceed \(2n\).

\(2.\) For every prime \(p > \sqrt{2n}, v_p \big({2n \choose n}\big) \leq 1\).

Combining Lemmas 2, 3 and 4 we obtain:

\begin{equation} {2n \choose n} \leq (2n)^{\sqrt{2n}} \cdot \prod_{\sqrt{2n} < p \leq 2n/3} p \leq (2n)^{\sqrt{2n}} \cdot \prod_{p=2}^{2n/3} p \leq (2n)^{\sqrt{2n}} \cdot 4^{2n/3} \end{equation}

Now, due to Lemma 1 this simplifies to:

\begin{equation} \frac{4^n}{2n+1} \leq (2n)^{\sqrt{2n}} \cdot 4^{2n/3} \implies 4^n \leq (2n+1) \cdot (2n)^{\sqrt{2n}} \cdot 4^{2n/3} \end{equation}

and it may be checked that (6) fails for \(n \geq 468\) using a computer.

References:

  1. Aigner, Martin; Ziegler, Günter (2009). Proofs from THE BOOK (4th ed.). Berlin, New York: Springer-Verlag.

  2. P. Ërdos, Beweis eines Satzes von Tschebyshef, Acta Sci. Math (Szeged) 5 (1930-1932)