Bertrand postulate proof sketch

Prove that ∀n∈ℕ(n>1⟹∃p∈ℙ(n<p<2n)).

Below is a classical proof of

$$\mathrm{\forall }n\in \mathbb{N},n>1⟹\mathrm{\exists }p\in \mathbb{P}\text{ with }n<p<2n,$$

first conjectured by Bertrand in 1845 and proved (independently) by Chebyshev in 1852. It is often called Bertrand’s postulate.

---

1. Chebyshev’s θ-function

Define

$$\theta (x)=\sum _{\begin{array}{c}p\le x\\ p\text{prime}\end{array}}\ln p.$$

Chebyshev showed by completely elementary means (bounding factorials via products) that there are absolute constants $A,B>0$ such that for all $x\ge 2$,

$$Ax\le \theta (x)\le Bx.$$

One may take for instance

$$0.92x\le \theta (x)\le 1.11x,$$

for every $x\ge 2$. (The proof is a straightforward—but somewhat lengthy—analysis of the prime‐power factors of $n!$.)

---

2. From θ to “a prime in $(n,2n)$”

Observe that

$$\theta (2n)-\theta (n)=\sum _{n<p\le 2n}\ln p.$$

If there were no prime in the open interval $(n,2n]$, then $\theta (2n)-\theta (n)=0$. But by Chebyshev’s bounds,

$$\theta (2n)-\theta (n)\ge 0.92(2n)-1.11n=(1.84-1.11)n=0.73n>0(\mathrm{\forall }n>1).$$

Hence

$$\sum _{n<p\le 2n}\ln p>0,$$

so there must be at least one prime $p\in (n,2n]$. This completes the proof.∎

---

Historical remarks

• Chebyshev’s original 1852 proof bounds factorials $n!\approx \sqrt{2\pi n}(n/e{)}^n$ from above and below elementarily, then translates those bounds into $Ax\le \theta (x)\le Bx$.
• In 1932, Erdős found a shorter “combinatorial” proof using properties of the central binomial coefficient $(\genfrac{}{}{0ex}{}{2n}{n})$.
• The statement is often referred to as Bertrand’s postulate, though it is now a theorem.