# 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 1$, $x\#<4^x$

Proof: Considering $n=\lfloor x\rfloor$ it is sufficient to prove the lemma for natural numbers $x=n$. The proof is by mathematical induction.

• $n = 1$: $n\# = 1 < 4 = 4^1.$
• $n = 2$: $n\# = 2 < 16 = 4^2.$
• $n > 2$ is even: $n\# = (n-1)\# < 4^{n-1} < 4^n.$
• $n > 2$ is odd. Let $n = 2m + 1$, then by binomial theorem:
$\binom{2m + 1}{m} = \frac{1}{2} \left[\binom{2m + 1}{m} + \binom{2m + 1}{m + 1}\right] < \frac{1}{2}\sum_{k = 0}^{2m+1} \binom{2m + 1}{k} = \frac{1}{2}(1 + 1)^{2m + 1} = 4^m.$
Each prime p with $m+1 divides $\textstyle\binom{2m + 1}{m}$, giving us:
$\frac{(2m + 1)\#}{(m + 1)\#} = \prod_{p > m + 1}^{p \leq 2m + 1} p \leq \binom{2m+1}{m} < 4^m.$
By induction for $m+1:
$n\# = (2m + 1)\# < 4^m \cdot (m + 1)\# < 4^m \cdot 4^{m + 1} = 4^{2m + 1} = 4^n.$

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.

## References

1. ^ Ramanujan, S. (1919), "A proof of Bertrand's postulate", Journal of the Indian Mathematical Society 11: 181–182