## Bertrand's Conjecture

Theorem (Bertrand's Conjecture)
Fir
$n \ge 1$
there is at least one prime number between
$n$
and
$2n$
inclusive.
Proof
Proof. Suppose to the contrary that there is some
$n$
with no prime between
$n$
and
$2n$
. Consider the prime factors of
$C_n = \begin{pmatrix}2n\\n\end{pmatrix}= \frac{(2n)!}{n!n!}$
. If
$p$
is such a factor with
$\frac{2n}{3} \lt p \lt n$
then
$\left[ \frac{2n}{p} \right] =2 \left[ \frac{n}{p} \right] =2$
, so
$p$
is not a factor of
$2n$
, so
$p \le \frac{2n}{3}$
/
We need the following lemma.
Lemma
For any integer

, none of the prime powers in the prime factorisation of
$2n$
.
For example, if
$n=4$
,
$C_n=70=2^1 \times 5^1 \times 7^1$
. None of
$2^1, \; 5^1, \; 7^1$
exceeds
$2n=8$
/
Proof
Let
$v_p(n)$
be the number of times a prime
$p$
occurs in the prime factorisation of
$n!$
is
$\left[ \frac{n}{p} \right] + \left[ \frac{n}{p^2} \right] + \left[ \frac{n}{p^3} \right] +...$
.
$v_p(C_n)=v_p((2n)!)-2 v_p(n!)= \left( \left[ \frac{2n}{p} -2 \frac{n}{p} \right] \right) + \left( \left[ \frac{2n}{p^2} -2 \frac{n}{p^2} \right] \right) + \left( \left[ \frac{2n}{p^3} -2 \frac{n}{p^3} \right] \right) +...$

$p^k \gt 2n \rightarrow \left( \left[ \frac{2n}{p^k} -2 \frac{n}{p^k} \right] \right)=0$
else this term is at most 1. Hence
$v_p(C_n)$
is at less than or equal to the largest
$k$
satisfying
$p^k \le 2n \rightarrow p^{v_p(C_n)} \le 2n$
.
Let
$n \gt 4$
(
$n=1, \; 2, \; 3, \; 4$
are not counterexamples), then
$\sqrt{2n} \lt \frac{2n}{3}$
. We can divide factors of
$C_n$
into those less than
$\sqrt{2n}$
and those between
$\sqrt{2n}$
and
$\frac{2n}{3}$
.
$C_n=\underbrace{p_1^{a_1}p_2^{a_2}...p_r^{a_r}}_{p_i \le \sqrt{2n}} \underbrace{p_{r+1}^{a_{r+1}}...p_k^{a_k}}_{\sqrt{2n} \lt p_i \lt \frac{2n}{3}}$
.
By the above lemma none of the primes in the first factor on the right hand side exceeds
$2n$
so
$\underbrace{p_1^{a_1}p_2^{a_2}...p_r^{a_r}}_{p_i \le \sqrt{2n}} \le (2n)^{\sqrt{2n}}$
.
The primes in the second factor all have power equal to 1, since
$p \gt \sqrt{2n} \rightarrow p^2 \gt 2n$
and the power could not be 2 or greater again by the above lemma. It then follows that
$\underbrace{p_{r+1}^{a_{r+1}}...p_k^{a_k}}_{ \sqrt{2n} \lt p_i \lt \frac{2n}{3}} \le (\frac{2n}{3})! \le 4^{2n/3}$
.
We need another lemma.
Lemma 2
$\frac{4^n}{2n} \le C_n$

Proof
$4^n \le (1+1)^{2n} = \sum_{k=0}^{2n} \begin{pmatrix}2n\\k\end{pmatrix}=2+ \sum_{k=1}^{2n-1} \begin{pmatrix}2n\\k\end{pmatrix} \le 2+(2n-1) \begin{pmatrix}2n\\n\end{pmatrix} \le 2n \begin{pmatrix}2n\\n\end{pmatrix}$

Hence
$\frac{4^n}{2n} \le C_n$

With this lemma we have
$\frac{4^n}{2n} \le C_n= \underbrace{p_1^{a_1}p_2^{a_2}...p_r^{a_r}}_{p_i \le \sqrt{2n}} \underbrace{p_{r+1}^{a_{r+1}}...p_K^{r_k}}_{ \sqrt{2n} \lt p_i \lt \frac{2n}{3}} \le (2n)^{\sqrt{2n}} 4^{2n/3}$
.
This can be shown to be true for
$n=1, \; 2,...,467$
but false for
$n \ge 468$
.To show that there are no coun terexamples for
$n le 467$
, we find a sequence of primes beginning
$2 \le p \le 467$
such that each prime is no more than twice the previous one. Here is such a sequence:
2, 3, 5, 7, 13, 23, 43, 83, 163, 317, 631