Proof of Bertrand's postulate

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).

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.}$

If ${\displaystyle p}$ is odd 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.)

An upper bound is supplied for 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}$.

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

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=m}$ is an integer, ${\displaystyle m\geq 3.}$ Since ${\displaystyle {\binom {2m-1}{m}}}$ is an integer and all the primes ${\displaystyle m+1\leq p\leq 2m-1}$ appear in its numerator but not in its denominator, we have

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

The proof proceeds by complete induction on ${\displaystyle n.}$

• If ${\displaystyle n=3}$, then ${\displaystyle n\#=6<8=2^{2n-3}.}$
• If ${\displaystyle n=4}$, then ${\displaystyle n\#=6<32=2^{2n-3}.}$
• If ${\displaystyle n\geq 5}$ is odd, ${\displaystyle n=2m-1}$, then by the above estimate and the induction assumption, since ${\displaystyle m\geq 3}$ and ${\displaystyle m<n}$ it is

${\displaystyle n\#=(2m-1)\#<m\#\cdot 2^{2m-2}<2^{2m-3}2^{2m-2}=2^{4m-5}=2^{2n-3}.}$

• If ${\displaystyle n=2m}$ is even and ${\displaystyle n\geq 6,}$ then by the above estimate and the induction assumption, since ${\displaystyle m\geq 3}$ and ${\displaystyle n-1<n}$ it is

${\displaystyle n\#=(n-1)\#<2^{2(n-1)-3}<2^{2n-3}}$.

Only ${\displaystyle x\#<4^{x}}$ is used in the proof.

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

Lemma 1 can be expressed as

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

for ${\displaystyle n\geq 13}$, and because ${\displaystyle {\frac {\pi (n)}{n}}<{\frac {1}{2}}}$ for ${\displaystyle n\geq 13}$, we can say that the product ${\displaystyle p^{R}}$ is at most ${\displaystyle (2n)^{\sqrt {\frac {n}{2}}}}$, which gives

${\displaystyle {\frac {\log 4}{3}}n\leq \!\left({\sqrt {\frac {n}{2}}}+1\right)\log 2n\;}$

which is true for ${\displaystyle n=81}$ and false for ${\displaystyle n=82}$.