The proof uses the following four lemmas to establish facts about the primes present in the central binomial coefficients.

Lemma 1 edit

For any integer ${\displaystyle n>0}$ , we have

${\displaystyle {\frac {4^{n}}{2n}}\leq {\binom {2n}{n}}.}$ 

Proof: Applying the binomial theorem,

${\displaystyle 4^{n}=(1+1)^{2n}=\sum _{k=0}^{2n}{\binom {2n}{k}}=2+\sum _{k=1}^{2n-1}{\binom {2n}{k}}\leq 2n{\binom {2n}{n}},}$ 

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

Lemma 2 edit

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

For any prime ${\displaystyle p}$ , ${\displaystyle p^{R}\leq 2n}$ .

Proof: The exponent of ${\displaystyle p}$  in ${\displaystyle n!}$  is given by Legendre's formula

${\displaystyle \sum _{j=1}^{\infty }\left\lfloor {\frac {n}{p^{j}}}\right\rfloor \!,}$ 

so

${\displaystyle R=\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 must be either zero (if ${\displaystyle n/p^{j}{\bmod {1}}<1/2}$ ) or one (if ${\displaystyle n/p^{j}{\bmod {1}}\geq 1/2}$ ), and all terms with ${\displaystyle j>\log _{p}(2n)}$  are zero. Therefore,

${\displaystyle R\leq \log _{p}(2n),}$ 

and

${\displaystyle p^{R}\leq p^{\log _{p}(2n)}=2n.}$ 

Lemma 3 edit

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

Proof: There are exactly two factors of ${\displaystyle p}$  in the numerator of the expression ${\displaystyle {\tbinom {2n}{n}}={\tfrac {(2n)!}{(n!)^{2}}}}$ , coming from the two terms ${\displaystyle p}$  and ${\displaystyle 2p}$  in ${\displaystyle (2n)!}$ , and also two factors of ${\displaystyle p}$  in the denominator from one copy of the term ${\displaystyle p}$  in each of the two factors of ${\displaystyle n!}$ . These factors all cancel, leaving no factors of ${\displaystyle p}$  in ${\displaystyle {\tbinom {2n}{n}}}$ . (The bound on ${\displaystyle p}$  in the preconditions of the lemma ensures that ${\displaystyle 3p}$  is too large to be a term of the numerator, and the assumption that ${\displaystyle p}$  is odd is needed to ensure that ${\displaystyle 2p}$  contributes only one factor of ${\displaystyle p}$  to the numerator.)

Lemma 4 edit

An upper bound is supplied for the primorial function,

${\displaystyle n\#=\prod _{p\,\leq \,n}p}$ 

where the product is taken over all prime numbers ${\displaystyle p}$  less than or equal to ${\displaystyle n}$ .

For all ${\displaystyle n\geq 1}$ , ${\displaystyle n\#<4^{n}}$ .

Proof: We use complete induction.

For ${\displaystyle n=1,2}$  we have ${\displaystyle 1\#=1<4}$  and ${\displaystyle 2\#=2<4^{2}=16}$ .

Let us assume that the inequality hold for all ${\displaystyle 1\leq n\leq 2k-1}$ . Since ${\displaystyle n=2k>2}$  is composite, we have

${\displaystyle (2k)\#=(2k-1)\#<4^{2k-1}<4^{2k}}$ 

Now let us assume that the inequality hold for all ${\displaystyle 1\leq n\leq 2k}$ . Since ${\displaystyle {\binom {2k+1}{k}}={\frac {(2k+1)!}{k!(k+1)!}}}$  is an integer and all the primes ${\displaystyle k+2\leq p\leq 2k+1}$  appear only in the numerator, we have

${\displaystyle {\frac {(2k+1)\#}{(k+1)\#}}\leq {\binom {2k+1}{k}}={\frac {1}{2}}\!\left[{\binom {2k+1}{k}}+{\binom {2k+1}{k+1}}\right]<{\frac {1}{2}}(1+1)^{2k+1}=4^{k}}$ 

therefore,

${\displaystyle (2k+1)\#=(k+1)\#\cdot {\frac {(2k+1)\#}{(k+1)\#}}\leq 4^{k+1}{\binom {2k+1}{k}}<4^{k+1}\cdot 4^{k}=4^{2k+1}}$ 

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

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

There are no prime factors p of ${\displaystyle \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 < p ≤ n: by Lemma 3.

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

When ${\displaystyle p>{\sqrt {2n}},}$  the number ${\displaystyle \textstyle {2n \choose n}}$  has at most one factor of p. By Lemma 2, for any prime p we have p^R(p,n) ≤ 2n, and ${\displaystyle \pi (x)\leq x-1}$  since 1 is neither prime nor composite. Then, starting with Lemma 1 and decomposing the right-hand side into its prime factorization, and finally using Lemma 4, these bounds give:

${\displaystyle {\frac {4^{n}}{2n}}\leq {\binom {2n}{n}}=\left(\,\prod _{p\,\leq \,{\sqrt {2n}}}p^{R(p,n)}\right)\!\!\left(\prod _{{\sqrt {2n}}\,<\,p\,\leq \,2n/3}\!\!\!\!\!\!\!p^{R(p,n)}\right)<\left(\,\prod _{p\,\leq \,{\sqrt {2n}}}\!\!2n\right)\!\!\left(\prod _{p\,\leq \,2n/3}\!\!p\right)\leq (2n)^{{\sqrt {2n}}-1}4^{2n/3}}$ 

we get the equivalent inequalities

${\displaystyle {\begin{aligned}&4^{n/3}\leq (2n)^{\sqrt {2n}}\\&2^{\sqrt {2n}}\leq (2n)^{3}\end{aligned}}}$ 

Taking logarithms yields to

${\displaystyle {\sqrt {2n}}\leq 3\log _{2}(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 ${\displaystyle n=426}$  and it does not for ${\displaystyle n=427}$ , we obtain

${\displaystyle n<427}$ 

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

Addendum to proof edit

It is possible to reduce the bound to ${\displaystyle n=50}$ .

For ${\displaystyle n\geq 17}$  we get ${\displaystyle \pi (n)<{\frac {n}{2}}-1}$ , so we can say that the product ${\displaystyle p^{R}}$  is at most ${\displaystyle (2n)^{0.5{\sqrt {2n}}-1}}$ , which gives

${\displaystyle {\begin{aligned}&{\frac {4^{n}}{2n}}\leq {\binom {2n}{n}}\leq (2n)^{0.5{\sqrt {2n}}-1}4^{2n/3}\\&4^{\sqrt {2n}}\leq (2n)^{3}\\&2{\sqrt {2n}}\leq 3\log _{2}(2n)\end{aligned}}}$ 

which is true for ${\displaystyle n=49}$  and false for ${\displaystyle n=50}$ .

• Chebyshev's Theorem and Bertrand's Postulate (Leo Goldmakher): https://web.williams.edu/Mathematics/lg5/Chebyshev.pdf
• Proof of Bertrand's Postulate (UW Math Circle): https://sites.math.washington.edu/~mathcircle/circle/2013-14/advanced/mc-13a-w10.pdf
• Proof in the Mizar system: http://mizar.org/version/current/html/nat_4.html#T56
• Weisstein, Eric W. "Bertrand's Postulate". MathWorld.