Bertrand's postulate

There is always a prime number at least with $n < p < 2n$.

Proof

we use a contradiction:an integer $n \geq 2$ such that there is no prime $p$ with $n < p < 2n$.

Define $R(p,n)$ to be $\begin{pmatrix} 2n \\ n \end{pmatrix}$'s exponent of a prime factor.

$\begin{pmatrix} 2n \\ n \end{pmatrix} = \prod_{1<p<2n}p^{R(p,n)}$

$\begin{pmatrix} 2n \\ n \end{pmatrix}=\frac{(2n)!}{(n!)^2}$ when $\frac{2}{3}n < p < n$, there is a two numbers $p$, $2p$ in $(2n)!$. there is a two numbers in the nominator, too. therefore, $\begin{pmatrix} 2n \\ n \end{pmatrix}$ don't have a factor of $p$. By a contradiction, all prime factor of $\begin{pmatrix} 2n \\ n \end{pmatrix}$ is greater than $\frac{2}{3}n$.

$\begin{pmatrix} 2n \\ n \end{pmatrix} = \prod_{p < \frac{2}{3}n}p$

also, $p > \sqrt{2n}$ has one exponent of a factor in $\begin{pmatrix} 2n \\ n \end{pmatrix}$.

$\begin{pmatrix} 2n \\ n \end{pmatrix} < \prod_{1<p\leq\sqrt{2n}}p^{R(p,n)}\prod_{\sqrt{2n}<p\leq\frac{2}{3}n}p \quad\text{- \ \ \ (1) }$

The exponent of $p$ in $n!$ is

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

[Legendre's formula](file://./legendre_formula.html) so,

$R(p,n) = \sum^{\infty}_{j=1}\lfloor\frac{2n}{p^j}\rfloor - 2\sum^{\infty}_{j=1}\lfloor\frac{n}{p^j}\rfloor=\sum^{\infty}_{j=1}(\lfloor\frac{2n}{p^j}\rfloor - 2\lfloor\frac{n}{p^j}\rfloor)$

if $\frac{n}{p^j}$ has a first number of decimal representation is greater than 5, the last summation is zero. otherwise, it is one. but all terms with $j > \log_p2n$ is zero. therefor,

$R(p,n) \leq \log_p2n$

$\prod_{1<p\leq\sqrt{2n}}p^{R(p,n)}\prod_{\sqrt{2n}<p\leq\frac{2}{3}n}p < (2n)^{\sqrt{2n}}\prod_{1<p\leq\frac{2}{3}n}p \quad\text{-\ \ \ (2) }$

(Lemma) For all real numbers $x \geq 3$, $\prod_{1<p\leq n}p < 2^{2n-3}$

Proof

$\frac{\prod_{1<p\leq 2n-1}p}{\prod_{1<p\leq n}p} \leq \begin{pmatrix}2n-1 \\ n\end{pmatrix} = \frac{1}{2}(\begin{pmatrix} 2n \\ n \end{pmatrix} - \begin{pmatrix} 2n \\ n-1 \end{pmatrix}) < \frac{1}{2}(1+1)^{2n} < 2^{2n-2}$

therefore, $\prod_{1<p\leq 2n-1}p < 2^{2n-2}\prod_{1<p\leq n}p$

using mathmatical induction, assume that $\prod_{1<p\leq m}p < 2^{2n-3}$

• odd case
  • If $n = 3$, $\prod_{1<p\leq n}p = 6 < 2^5$
  • If $n = 2m-1$, $\prod_{1<p\leq 2m-1}p<2^{2m-2}\prod_{1<p\leq m}p<2^{2m-2}2^{2m-3}=2^{4m-5}=2^{2(2m-1)-3}$
• even case
  • If n = 4, $\prod_{1<p\leq n}p = 6 < 2^6$
  • If $n = 2m$, $\prod_{1<p\leq 2m}p<2^{2m-1}\prod_{1<p\leq m}p<2^{2m-1}2^{2m-2}=2^{4m-3}=2^{2(2m)-3}$

QED

apply above lemma,

$(2n)^{\sqrt{2n}}\prod_{1<p\leq\frac{2}{3}n}p < (2n)^{\sqrt{2n}} 2^{\frac{4}{3}n-3}<(2n)^{\sqrt{2n}} 2^{\frac{4}{3}n}$

therefore,

$\begin{pmatrix} 2n \\ n \end{pmatrix} < (2n)^{\sqrt{2n}} 2^{\frac{4}{3}n}$

and $\begin{pmatrix} 2n \\ n \end{pmatrix}$ is less than

$4^n = (1+1)^{2n} = \sum^{2n}_{k=0} \begin{pmatrix} 2n \\ k \end{pmatrix} = 2+\sum^{2n-1}_{k=1}\begin{pmatrix} 2n \\ k \end{pmatrix} \leq 2n\begin{pmatrix} 2n \\ n \end{pmatrix}$

$\frac{2^{2n}}{2n} \leq \begin{pmatrix} 2n \\ n \end{pmatrix}$

so,

$\frac{2^{2n}}{2n} \leq\begin{pmatrix} 2n \\ n \end{pmatrix} < (2n)^{\sqrt{2n}} 2^{\frac{4}{3}n}$

$2^{2n} \leq (2n)^{\sqrt{2n}+1} 2^{\frac{4}{3}n}$

take $log_2$ yield to

$2n \leq (\sqrt{2n}+1)\log_2(2n) + \frac{4}{3}n$

$\frac{2}{3}n \leq (\sqrt{2n}+1)\log_2(2n)$

we obtain $n \leq 467$ but when $n \leq 467$, the prime numbers 3, 5, 7, 13, 23, 43, 83, 163, 317, 631 is chosen, such that $n < p < 2n$. it is contradiction.