Bertrand postulate proof sketch

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

Below is a classical proof of

$$ \forall n\in\Bbb N,\;n>1\;\Longrightarrow\;\exists\,p\in\Bbb 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_{\substack{p\le x\\p\;\text{prime}}}\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\ge2$,

$$ A\,x\;\le\;\theta(x)\;\le\;B\,x. $$

One may take for instance

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

for every $x\ge2$. (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.11\,n \;=\;(1.84-1.11)\,n \;=\;0.73\,n \;>\;0 \quad(\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 $\;A\,x\le\theta(x)\le B\,x$.
• In 1932, Erdős found a shorter “combinatorial” proof using properties of the central binomial coefficient $\binom{2n}{n}$.
• The statement is often referred to as Bertrand’s postulate, though it is now a theorem.