# 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

$\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

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

### (Lemma) For all real numbers $x \geq 3$, $\prod_{1

#### Proof

$\frac{\prod_{1

therefore, $\prod_{1

using mathmatical induction, assume that $\prod_{1

• odd case
• If $n = 3$, $\prod_{1
• If $n = 2m-1$, $\prod_{1
• even case
• If n = 4, $\prod_{1
• If $n = 2m$, $\prod_{1

QED

apply above lemma,

$(2n)^{\sqrt{2n}}\prod_{1

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.