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