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

Given those analyses, we may use the following lemmas:

## Lemma 1:

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

## Lemma 2:

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

## Lemma 3:

$$v_p \big({2n \choose n}\big) \geq 1 \implies v_p \big({2n \choose n}\big) \leq \log_p (2n)$$

## Lemma 4:

$$e^{\vartheta(n)} \leq 4^n$$

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

$${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}$$

Now, due to Lemma 1 this simplifies to:

$$\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}$$

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)