# Proof of Bertrand's postulate

In mathematics, Bertrand's postulate (actually a theorem) states that for each $n\ge 1$ there is a prime $p$ such that $n. It was first proven by Pafnuty Chebyshev, and a short but advanced proof was given by Srinivasa Ramanujan.[1] The gist of the following elementary proof is due to Paul Erdős. The basic idea of the proof is to show that a certain central binomial coefficient needs to have a prime factor within the desired interval in order to be large enough. This is made possible by a careful analysis of the prime factorization of central binomial coefficients.

The main steps of the proof are as follows. First, one shows that every prime power factor $p^r$ that enters into the prime decomposition of the central binomial coefficient $\tbinom{2n}{n}:=\frac{(2n)!}{(n!)^2}$ is at most $2n$. In particular, every prime larger than $\sqrt{2n}$ can enter at most once into this decomposition; that is, its exponent $r$ is at most one. The next step is to prove that $\tbinom{2n}{n}$ has no prime factors at all in the gap interval $\left(\tfrac{2n}{3}, n\right)$. As a consequence of these two bounds, the contribution to the size of $\tbinom{2n}{n}$ coming from all the prime factors that are at most $n$ grows asymptotically as $O(\theta^n)$ for some $\theta<4$. Since the asymptotic growth of the central binomial coefficient is at least $4^n/2n$, one concludes that for $n$ large enough the binomial coefficient must have another prime factor, which can only lie between $n$ and $2n$. Indeed, making these estimates quantitative, one obtains that this argument is valid for all $n>468$. The remaining smaller values of $n$ are easily settled by direct inspection, completing the proof of the Bertrand's postulate.

## Lemmas and computation

### Lemma 1: A lower bound on the central binomial coefficients

Lemma: For any integer $n>0$, we have

$\frac{4^n}{2n} \le \binom{2n}{n}.\$

Proof: Applying the binomial theorem,

$4^n = (1 + 1)^{2n} = \sum_{k = 0}^{2n} \binom{2n}{k}=2+\sum_{k = 1}^{2n-1} \binom{2n}{k} \le 2n\binom{2n}{n},\$

since $\tbinom{2n}{n}$ is the largest term in the sum in the right-hand side, and the sum has $2n$ terms (including the initial two outside the summation).

### Lemma 2: An upper bound on prime powers dividing central binomial coefficients

For a fixed prime $p$, define $R(p,n)$ to be the largest natural number $r$ such that $p^r$ divides $\tbinom{2n}{n}$.

Lemma: For any prime $p$, $p^{R(p,n)}\le 2n$.

Proof: The exponent of $p$ in $n!$ is (see Factorial#Number theory):

$\sum_{j = 1}^\infty \left\lfloor \frac{n}{p^j} \right\rfloor,\$

so

$R(p,n) =\sum_{j = 1}^\infty \left\lfloor \frac{2n}{p^j} \right\rfloor - 2\sum_{j = 1}^\infty \left\lfloor \frac{n}{p^j} \right\rfloor =\sum_{j = 1}^\infty \left(\left\lfloor \frac{2n}{p^j} \right\rfloor - 2\left\lfloor \frac{n}{p^j} \right\rfloor\right).$

But each term of the last summation can either be zero (if $n/p^j \bmod 1< 1/2$) or 1 (if $n/p^j \bmod 1\ge 1/2$) and all terms with $j>\log_p(2n)$ are zero. Therefore

$R(p,n) \leq \log_p(2n),\$

and

$p^{R(p,n)} \leq p^{\log_p{2n}} = 2n.\$

This completes the proof of the lemma.

### Lemma 3: The exact power of a large prime in a central binomial coefficient

Lemma: If $p$ is odd and $\frac{2n}{3} < p \leq n$, then $R(p,n) = 0.\$

Proof: The factors of $p$ in the numerator come from the terms $p$ and $2p$, and in the denominator from two factors of $p$. These cancel since $p$ is odd.

### Lemma 4: An upper bound on the primorial

We estimate the primorial function,

$x\# = \prod_{p \leq x} p,\$

where the product is taken over all prime numbers $p$ less than or equal to the real number $x$.

Lemma: For all real numbers $x\ge 3$, $x\#<2^{2x-3}$[2]

Proof: Since $\binom{2n}{n}$ is an integer and all the primes $n+1 \le p \le 2n-1$ appears in its numerator $(2x-1)\#/(x)\# \le \binom{2n}{n} <2^{2x-2}$ holds. The proof is by mathematical induction.

• $n = 3$: $n\# = 6 < 8.$
• $n = 4$: $n\# =6 < 32.$
• $2m-1\# < 2^{2(2m-1)-3}$
• $2m\# < 2^{2(2m-3)}$
• $x\# = \lfloor x\rfloor\# < 2^{2x-3}$

Thus the lemma is proven.

## Proof of Bertrand's Postulate

Assume there is a counterexample: an integer n ≥ 2 such that there is no prime p with n < p < 2n.

If 2 ≤ n < 468, then p can be chosen from among the prime numbers 3, 5, 7, 13, 23, 43, 83, 163, 317, 631 (each being less than twice its predecessor) such that n < p < 2n. Therefore n ≥ 468.

There are no prime factors p of $\textstyle\binom{2n}{n}$ such that:

• 2n < p, because every factor must divide (2n)!;
• p = 2n, because 2n is not prime;
• n < p < 2n, because we assumed there is no such prime number;
• 2n / 3 < pn: by Lemma 3.

Therefore, every prime factor p satisfies p ≤ 2n/3.

When $p > \sqrt{2n},$ the number $\textstyle {2n \choose n}$ has at most one factor of p. By Lemma 2, for any prime p we have pR(p,n) ≤ 2n, so the product of the pR(p,n) over the primes less than or equal to $\sqrt{2n}$ is at most $(2n)^{\sqrt{2n}}$. Then, starting with Lemma 1 and decomposing the right-hand side into its prime factorization, and finally using Lemma 4, these bounds give:

$\frac{4^n}{2n } \le \binom{2n}{n} = \left(\prod_{p \le \sqrt{2n}} p^{R(p,n)}\right) \left(\prod_{\sqrt{2n} < p \le \frac{2n}{3}} p^{R(p,n)}\right) < (2n)^{\sqrt{2n}} \prod_{1 < p \leq \frac{2n}{3} } p = (2n)^{\sqrt{2n}} \Big( \frac{2n}{3}\Big)\# \le (2n)^{\sqrt{2n}} 4^{2n/3}.\$

Taking logarithms yields to

${\frac{\log 4}{3}}n \le (\sqrt{2n}+1)\log 2n\; .$

By concavity of the right-hand side as a function of n, the last inequality is necessarily verified on an interval. Since it holds true for n=467 and it does not for n=468, we obtain

$n < 468.\$

But these cases have already been settled, and we conclude that no counterexample to the postulate is possible.

### Proof by Shigenori Tochiori

Using Lemma 4, Tochiori refined Erdos's method and proved if there exists a positive integer $n \ge 5$ such that there is no prime number $n then $n < 64$. [3]

First, refine lemma 1 to:

Lemma 1': For any integer $n\ge 4$, we have

$\frac{4^n}n < \binom{2n}{n}.\$

Proof: By induction: $\frac{4^4}4 = 64 < 70 = \binom{8}{4},$ and assuming the truth of the lemma for $n-1$,

$\binom{2n}{n} = 2\,\frac{2n-1}{n}\binom{2(n-1)}{n-1} > 2\,\frac{2n-1}{n}\frac{4^{n-1}}{n-1} > 2\cdot 2\,\frac{4^{n-1}}{n} = \frac{4^n}{n}.$

Then, refine the estimate of the product of all small primes via a better estimate on $\pi(x)$ (the number of primes at most $n$):

Lemma 5: For any natural number $n$, we have

$\pi(n)\le\frac13n+2.$

Proof: Except for $p=2,3$, every prime number has $p\equiv 1$ or $p\equiv 5 \pmod 6$. Thus $\pi(n)$ is upper bounded by the number of numbers with $k\equiv 1$ or $k\equiv 5 \pmod 6$, plus one (since this counts $1$ and misses $2,3$). Thus

$\pi(n)\le\left\lfloor\frac{n+5}6\right\rfloor+\left\lfloor\frac{n+1}6\right\rfloor+1\le\frac{n+5}6+\frac{n+1}6+1=\frac13n+2.$

Now, calculating the binomial coefficient as in the previous section, we can use the improved bounds to get (for $n\ge5$, which implies $\sqrt{2n}\ge3$ so that $\sqrt{2n}\#\ge3\#=6$):

\begin{align} \frac{4^n}{n}&\le \binom{2n}{n} \\ &= \prod_{p \le \sqrt{2n}} p^{R(p,n)}\cdot\prod_{\sqrt{2n} < p \le \frac{2n}{3}} p^{R(p,n)}\\ &< (2n)^{\pi(\sqrt{2n})} \prod_{\sqrt{2n} < p \leq \frac{2n}{3}} p = (2n)^{\frac13\sqrt{2n}+2} \frac{(2n/3)\#}{\sqrt{2n}\#}\\ &<(2n)^{\frac13\sqrt{2n}+2}\frac{2^{2\cdot2n/3-3}}6<(2n)^{\frac13\sqrt{2n}+2}2^{4n/3-5}. \end{align}

Taking logarithms to get

$\frac23n\log 2< \frac13\sqrt{2n}\log 2n+3\log \frac n2$

and dividing both sides by $\frac23n$:

$\log 2<\sqrt{2}\cdot\frac{\log\sqrt{n}}{\sqrt{n}}+\frac94\frac{\log \frac n2}{\frac n2}+\frac{\log 2}{\sqrt{2n}}\equiv f(n)\; .$

Now the function $g(x)=\frac{\log x}x$ is decreasing for $x\ge e$, so $f(n)$ is decreasing when $n\ge e^2>2e$. But

$\frac{f(2^6)}{\log 2}=\sqrt{2}\cdot\frac{3}{8}+\frac94\cdot\frac{5}{32}+\frac{\sqrt{2}}{16}=0.97\dots<1<\frac{f(n)}{\log 2},$

so $n<2^6=64$. The remaining cases are proven by an explicit list of primes, as above.