# Proof of Bertrand's postulate

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

## Lemmas and computation

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

Lemma: 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: An upper bound on prime powers dividing central binomial coefficients

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

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

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

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

so

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

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

and

${\displaystyle 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 ${\displaystyle p}$ is odd and ${\displaystyle {\frac {2n}{3}}, then ${\displaystyle R(p,n)=0.\ }$

Proof: There are exactly two factors of ${\displaystyle p}$ in the numerator of the expression ${\displaystyle {\tbinom {2n}{n}}={\frac {(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 two copies of the term ${\displaystyle p}$ in ${\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: An upper bound on the primorial

We estimate the primorial function,

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

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

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

Proof: Since ${\displaystyle x\#=\lfloor x\rfloor \#}$ and ${\displaystyle 2^{2\lfloor x\rfloor -3}\leq 2^{2x-3}}$, it suffices to prove the result under the assumption that ${\displaystyle x=n}$ is an integer, ${\displaystyle n\geq 3}$. Since ${\displaystyle {\binom {2n-1}{n}}}$ is an integer and all the primes ${\displaystyle n+1\leq p\leq 2n-1}$ appear in its numerator but not in its denumerator, we have

${\displaystyle {\frac {(2n-1)\#}{n\#}}\leq {\binom {2n-1}{n}}={\frac {1}{2}}\left({\binom {2n-1}{n-1}}+{\binom {2n-1}{n}}\right)<{\frac {1}{2}}(1+1)^{2n-1}=2^{2n-2}.}$.

The proof proceeds by mathematical induction.

• If ${\displaystyle n=3}$, then ${\displaystyle n\#=6<8=2^{2n-3}.}$
• If ${\displaystyle n=4}$, then ${\displaystyle n\#=6<16=2^{2n-3}.}$
• If ${\displaystyle n=2m-1}$ is odd and ${\displaystyle n\geq 5}$, then by the above estimate and the induction assumtion for ${\displaystyle m\geq 3}$ it's
${\displaystyle n\#=(2m-1)\#
• If ${\displaystyle n=2m}$ is even and ${\displaystyle n\geq 6}$, then by the above estimate and the induction assumtion for ${\displaystyle m\geq 3}$ it's
${\displaystyle n\#=(2m)\#=(2m-1)\#

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 ${\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 < pn: 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 pR(p,n) ≤ 2n, so the product of the pR(p,n) over the primes less than or equal to ${\displaystyle {\sqrt {2n}}}$ is at most ${\displaystyle (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:

${\displaystyle {\frac {4^{n}}{2n}}\leq {\binom {2n}{n}}=\left(\prod _{p\leq {\sqrt {2n}}}p^{R(p,n)}\right)\left(\prod _{{\sqrt {2n}}

Taking logarithms yields to

${\displaystyle {\frac {\log 4}{3}}n\leq ({\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

${\displaystyle 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 ${\displaystyle n\geq 5}$ such that there is no prime number ${\displaystyle n then ${\displaystyle n<64}$. [3]

First, refine lemma 1 to:

Lemma 1': For any integer ${\displaystyle n\geq 4}$, we have

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

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

${\displaystyle {\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 ${\displaystyle \pi (x)}$ (the number of primes at most ${\displaystyle n}$):

Lemma 5: For any natural number ${\displaystyle n}$, we have

${\displaystyle \pi (n)\leq {\frac {1}{3}}n+2.}$

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

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

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

{\displaystyle {\begin{aligned}{\frac {4^{n}}{n}}&\leq {\binom {2n}{n}}\\&=\prod _{p\leq {\sqrt {2n}}}p^{R(p,n)}\cdot \prod _{{\sqrt {2n}}

Taking logarithms to get

${\displaystyle {\frac {2}{3}}n\log 2<{\frac {1}{3}}{\sqrt {2n}}\log 2n+3\log {\frac {n}{2}}}$

and dividing both sides by ${\displaystyle {\frac {2}{3}}n}$:

${\displaystyle \log 2<{\sqrt {2}}\cdot {\frac {\log {\sqrt {n}}}{\sqrt {n}}}+{\frac {9}{4}}{\frac {\log {\frac {n}{2}}}{\frac {n}{2}}}+{\frac {\log 2}{\sqrt {2n}}}\equiv f(n)\;.}$

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

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

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