PlanetMath: Bertrand's conjecture, proof of

Proof. [Bertrand's conjecture] Let

be a minimal counterexample to the claim. Thus there is no prime

such that

In the sequence of primes

$\displaystyle 2, 3, 5, 7, 13, 23, 43, 83, 163, 317, 631, 1259, 2503,$

each succeeding term is smaller than the double of its predecessor. This shows that $n\ge 2503$ .

The binomial expansion of $(1+1)^{2n}$ has terms and has largest term $\binom{2n}{n}$ . Hence

$\displaystyle \binom{2n}{n}\ge\frac{4^n}{2n+1}\ge\frac{4^n}{(2n)^2}.$

For a prime define to be the highest power of dividing $\binom{2n}{n}$ . To compute , we apply the lemma to and . We get that

$\displaystyle r(p,n)=\sum_{j\ge 1}\left\lfloor\frac{2n}{p^j}\right\rfloor -2\su... ...or\frac{2n}{p^j}\right\rfloor -2\left\lfloor\frac{n}{p^j}\right\rfloor\right).$

The terms of the sum are all 0 or 1 and vanish when $\displaystyle j>\left\lfloor\frac{\log(2n)}{\log p}\right\rfloor$ , so $\displaystyle r(p,n)\le\left\lfloor\frac{\log(2n)}{\log p}\right\rfloor$ , that is, $p^{r(p,n)}\le 2n$ .

Now $\displaystyle\binom{2n}{n}=\prod_p p^{r(p,n)}$ . By the inequality just proved, primes larger than do not contribute to this product, and by assumption there are no primes between and . So

$\displaystyle \binom{2n}{n}=\prod_{\substack{1\le p \le n\\ p\text{\ prime}}}p^{r(p,n)}.$

For $n>p>\frac{2n}{3}$ , $\frac{3}{2}>\frac{n}{p}>1$ and so for $p>\frac{2n}{3}>\sqrt{2n}$ we can apply the previous formula for and find that it is zero. So for all , the contribution of the primes larger than $\frac{2n}{3}$ is zero.

If $p>\sqrt{2n}$ , all the terms for higher powers of vanish and $\displaystyle r(p,n)=\left\lfloor\frac{2n}{p}\right\rfloor-2\left\lfloor\frac{n}{p}\right\rfloor$ . Since is at most 1, an upper bound for the contribution for the primes between $\sqrt{2n}$ and $\frac{2n}{3}$ is the product of all primes smaller than $\frac{2n}{3}$ . This product is $\exp\left(\vartheta(\frac{2n}{3})\right)$ , where $\vartheta(n)$ is the Chebyshev function

$\displaystyle \vartheta(n)=\sum_{\substack{p\le n\\ p\text{\ prime}}}\log p.$

There are at most $\sqrt{2n}$ primes smaller than $\sqrt{2n}$ and by the inequality $p^{r(p,n)}\le 2n$ their product is less than $(2n)^{\sqrt{2n}}$ . Combining this information, we get the inequality

$\displaystyle \frac{4^n}{(2n)^2}\le\binom{2n}{n}\le(2n)^{\sqrt{2n}}\exp\left({\textstyle\vartheta(\frac{2n}{3})}\right).$

Taking logarithms and applying the upper bound of $n\log 4$ for $\vartheta(n)$ , we obtain the inequality $\frac{n}{3}\log 4\le(\sqrt{2n}+2)\log(2n)$ , which is false for sufficiently large

, say $n=2^{11}$ . This shows that $n<2^{11}$ .

Since the conditions $n\ge 2503$ and $n<2^{11}$ are incompatible, there are no counterexamples to the claim. $\qedsymbol$

Bibliography