Euclid guarantees that the primes never run out — but he says nothing about where the next one is. After a prime, the trail can go cold: you can manufacture a run of a million consecutive composites whenever you like. So here is a genuinely worrying question. If you double a number — step from n up to 2n — are you certain to have stepped over at least one prime, or could you land in a desert so wide that doubling isn't enough to escape it?

Bertrand's postulate answers: you are certain. Between any number and its double there is always a prime, no matter how large you go. It is the first genuinely quantitative control on how primes are spread out — a hard, unconditional guarantee that primes are never more than a factor of two apart. And it has one of the loveliest proofs in all of mathematics, found by a nineteen-year-old.

The statement

The two forms say the same thing. Applying the interval statement to n = p_k produces a prime p with p_k < p \le 2p_k; that prime cannot equal 2p_k (which is even), so the very next prime p_{k+1} \le p < 2p_k. The half-open interval matters: (n, 2n] includes the endpoint 2n but excludes n itself, which keeps the statement clean at n = 1 (the prime is 2).

A quick reality check

Before proving anything, let's watch the postulate deliver. For each n we only need to exhibit one prime in (n, 2n]:

Notice a pattern building: near the bottom the interval often holds exactly one prime (at n=1,2,3 there is nothing to spare), while higher up they start to pile up. The postulate is tight at the very start and increasingly generous later — which is exactly what the picture below shows.

Seeing it: the interval is never empty

The curve below counts the primes in (n, 2n] — the quantity \pi(2n) - \pi(n), where \pi is the prime-counting function. Bertrand's postulate is exactly the claim that this count is never zero. And it isn't just clinging to 1: it trends steadily upward, so the real supply of primes between n and 2n grows without bound (the Prime Number Theorem later pins the growth at \sim n/\ln n).

The line hugs the axis at the far left — that early tightness is real — and then climbs, jagged but relentless. Bertrand only promises the curve stays above 0; the deeper theory explains why it soars.

History: a conjecture, a proof, and a rhyme

Joseph Bertrand stated the claim in 1845 and checked it by hand for every n up to about 3{,}000{,}000 — strong evidence, but not a proof. The first proof came from Pafnuty Chebyshev in 1852, as a by-product of his powerful (and heavier) estimates c_1\,\tfrac{x}{\ln x} \le \pi(x) \le c_2\,\tfrac{x}{\ln x} for the prime-counting function. That is why the result is often called the Bertrand–Chebyshev theorem.

Then, in 1932, a nineteen-year-old Paul Erdős published a proof so clean and so elementary — no calculus, no complex analysis, just clever bookkeeping on a single binomial coefficient — that it remains the textbook proof to this day. It was one of his first published papers, and it announced the arrival of one of the great problem-solvers of the century.

The star of the proof: the central binomial coefficient

Erdős's whole argument revolves around one number, the central binomial coefficient

The idea is a squeeze. We will trap \binom{2n}{n} between two sizes, and separately dissect its prime factorisation. If no prime lived in (n, 2n], the factorisation would be forced to be too small to reach the lower size — a contradiction. First, the two easy size bounds.

Both fall out of the binomial theorem. The full row of Pascal's triangle sums to \sum_{k=0}^{2n}\binom{2n}{k} = (1+1)^{2n} = 4^n, a sum of 2n+1 positive terms. The central term \binom{2n}{n} is just one of them, so it is \le 4^n. And it is the largest of the terms (the row grows to its middle), so it is at least the average, 4^n/(2n+1). That's the squeeze in place: something of order 4^n, give or take a polynomial factor.

Dissecting the prime factorisation

Now the arithmetic heart. Write the prime factorisation \binom{2n}{n} = \prod_p p^{\,R(p)}. The exponent R(p) of a prime p is given by Legendre's formula applied to (2n)!/(n!)^2:

Each bracket is either 0 or 1 — because \lfloor 2x \rfloor - 2\lfloor x \rfloor \in \{0,1\} for any real x — and the terms vanish as soon as p^{\,j} > 2n. Four consequences follow, and together they pin the number down completely.

The middle two deserve a line of arithmetic. For the dead zone \tfrac{2n}{3} < p \le n: then p \le n gives \lfloor n/p\rfloor = 1, while 3p > 2n forces 2n/p < 3, and since also p \le n gives 2n/p \ge 2, we get \lfloor 2n/p\rfloor = 2. The first bracket is therefore 2 - 2\cdot 1 = 0, and higher powers p^2 > (2n/3)^2 \ge 2n (for n \ge 5) contribute nothing — so R(p)=0. For the target primes n < p \le 2n: now \lfloor n/p\rfloor = 0 and \lfloor 2n/p\rfloor = 1, so the only surviving term is 1 - 0 = 1, i.e. R(p) = 1. Perfect: the primes in (n,2n] are precisely the ones that appear to the first power.

One more tool: the primorial bound

We will need to know that the primes up to some size can't multiply to too much. Let \displaystyle P(x) = \prod_{p \le x} p be the primorial — the product of all primes up to x.

This is proved by an induction that (fittingly) also leans on a central-ish binomial coefficient: every prime p with m+1 < p \le 2m+1 divides \binom{2m+1}{m}, and that coefficient is at most 4^m, which drives the induction step. We'll take it as a lemma here so we can keep our eyes on Bertrand; the details sit in any analytic number theory text. The point is simply: the product of all primes below x is at most 4^{x}.

The contradiction — Erdős's finish

Now suppose, for contradiction, that for some n there is no prime in (n, 2n]. Split the prime factorisation of \binom{2n}{n} into the pieces our four facts allow to survive. Since the target interval is empty, and the dead zone (\tfrac{2n}{3}, n] never contributes, every prime factor p satisfies p \le \tfrac{2n}{3}. Break those into small and medium:

• Small primes p \le \sqrt{2n}: there are fewer than \sqrt{2n} of them, and each contributes a block p^{R(p)} \le 2n. Their total is at most (2n)^{\sqrt{2n}}.
• Medium primes \sqrt{2n} < p \le \tfrac{2n}{3}: each has R(p) \le 1, so together they contribute at most the primorial \prod_{p \le 2n/3} p \le 4^{\,2n/3}.

Multiplying the two blocks bounds the whole coefficient from above:

But we also have the lower bound from the squeeze. Chaining them:

Collect the powers of 4. Dividing by 4^{2n/3} leaves 4^{n/3} on the left, and folding the harmless 2n+1 into the polynomial factor gives

This is where the exponential on the left must lose. Taking logarithms, the left grows linearly in n while the right grows only like \sqrt{2n}\,\ln(2n) — a hopeless mismatch for large n. Working the inequality carefully shows it fails for every n \ge 468. So for all such n the assumption is impossible: there must be a prime in (n, 2n].

That leaves only the finitely many small cases n < 468, and those are dispatched by exhibiting one explicit chain of primes, each less than twice the previous:

Every consecutive pair here satisfies p_{k+1} < 2p_k, so any n < 631 falls between two of them and has one of them sitting in (n,2n]. The two ranges together — the analytic bound for large n, the finite list for small — cover every n \ge 1. Bertrand's postulate is proved. \blacksquare

Worked example: watching the squeeze bite at n = 5

Let's see the machinery on a concrete value, n = 5, so 2n = 10 and \binom{10}{5} = 252. First the size bounds:

Now the factorisation. 252 = 2^2 \cdot 3^2 \cdot 7. Read our four facts off it:

• No prime factor exceeds 2n = 10. \checkmark
• The prime powers are 2^2 = 4 \le 10 and 3^2 = 9 \le 10 — both at most 2n. \checkmark
• The dead zone is (\tfrac{10}{3}, 5] = (3.33, 5], containing the prime 5 — and indeed 5 \nmid 252. \checkmark
• The target interval is (5, 10], containing the prime 7 — and 7 divides 252 exactly once. \checkmark

The single prime 7 that makes Bertrand's postulate true at n=5 is precisely the factor sitting inside \binom{10}{5} to the first power. That is the whole strategy in miniature: the coefficient is too big to be built out of small primes alone, so a fresh prime from (n,2n] has to be hiding inside it.