Bertrand's postulate

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

Proof

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

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

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

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

(2nn)=p<23np\begin{pmatrix} 2n \\ n \end{pmatrix} = \prod_{p < \frac{2}{3}n}p

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

(2nn)<1<p2npR(p,n)2n<p23np-    (1) \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 pp in n!n! is

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

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

R(p,n)=j=12npj2j=1npj=j=1(2npj2npj)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 npj\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>logp2nj > \log_p2n is zero. therefor,

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


1<p2npR(p,n)2n<p23np<(2n)2n1<p23np-   (2) \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 x3x \geq 3, 1<pnp<22n3\prod_{1<p\leq n}p < 2^{2n-3}

Proof

1<p2n1p1<pnp(2n1n)=12((2nn)(2nn1))<12(1+1)2n<22n2\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, 1<p2n1p<22n21<pnp\prod_{1<p\leq 2n-1}p < 2^{2n-2}\prod_{1<p\leq n}p

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

QED

apply above lemma,

(2n)2n1<p23np<(2n)2n243n3<(2n)2n243n(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,

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


and (2nn)\begin{pmatrix} 2n \\ n \end{pmatrix} is less than

4n=(1+1)2n=k=02n(2nk)=2+k=12n1(2nk)2n(2nn)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}


22n2n(2nn)\frac{2^{2n}}{2n} \leq \begin{pmatrix} 2n \\ n \end{pmatrix}

so,

22n2n(2nn)<(2n)2n243n\frac{2^{2n}}{2n} \leq\begin{pmatrix} 2n \\ n \end{pmatrix} < (2n)^{\sqrt{2n}} 2^{\frac{4}{3}n}

22n(2n)2n+1243n2^{2n} \leq (2n)^{\sqrt{2n}+1} 2^{\frac{4}{3}n}

take log2log_2 yield to

2n(2n+1)log2(2n)+43n2n \leq (\sqrt{2n}+1)\log_2(2n) + \frac{4}{3}n

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

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