Bertrand’s conjecture, proof of
This is a version of Erdős’s proof as it appears in Hardy and Wright.
We begin with the following lemma.
Lemma.
Let $n$ be a positive integer and $p$ be a prime. The highest power of $p$ dividing $n\mathrm{!}$ is $\mathrm{\sum}_{j}}\mathrm{\lfloor}{\displaystyle \frac{n}{{p}^{j}}}\mathrm{\rfloor$, where $\mathrm{\lfloor}x\mathrm{\rfloor}$ is the floor of $x$.
Proof.
Let ${p}^{k}$ divide $n!$ with $k$ as large as possible. Every $p$th term of the sequence^{} $1,\mathrm{\dots},n$ is divisible by $p$, so contributes a factor to ${p}^{k}$. There are $\lfloor {\displaystyle \frac{n}{p}}\rfloor $ such factors. Every ${p}^{2}$th term contributes an extra factor above that, providing $\lfloor {\displaystyle \frac{n}{{p}^{2}}}\rfloor $ new factors. In general, the ${p}^{j}$th terms contribute $\lfloor {\displaystyle \frac{n}{{p}^{j}}}\rfloor $ extra factors to ${p}^{k}$. So the highest power of $p$ dividing $n!$ is $\sum _{j}}\lfloor {\displaystyle \frac{n}{{p}^{j}}}\rfloor $. ∎
We now prove the theorem^{}.
Bertrand’s conjecture.
Let $n>2$ be a minimal counterexample to the claim. Thus there is no prime $p$ such that $$.
In the sequence of primes
$$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 (http://planetmath.org/BinomialTheorem) of ${(1+1)}^{2n}$ has $2n+1$ terms and has largest term $\left(\genfrac{}{}{0pt}{}{2n}{n}\right)$. Hence
$$\left(\genfrac{}{}{0pt}{}{2n}{n}\right)\ge \frac{{4}^{n}}{2n+1}\ge \frac{{4}^{n}}{{(2n)}^{2}}.$$ |
For a prime $p$ define $r(p,n)$ to be the highest power of $p$ dividing $\left(\genfrac{}{}{0pt}{}{2n}{n}\right)$. To compute $r(p,n)$, we apply the lemma to $(2n)!$ and $n!$. We get that
$$r(p,n)=\sum _{j\ge 1}\lfloor \frac{2n}{{p}^{j}}\rfloor -2\sum _{j\ge 1}\lfloor \frac{n}{{p}^{j}}\rfloor =\sum _{j\ge 1}\left(\lfloor \frac{2n}{{p}^{j}}\rfloor -2\lfloor \frac{n}{{p}^{j}}\rfloor \right).$$ |
The terms of the sum are all 0 or 1 and vanish when $j>\lfloor {\displaystyle \frac{\mathrm{log}(2n)}{\mathrm{log}p}}\rfloor $, so $r(p,n)\le \lfloor {\displaystyle \frac{\mathrm{log}(2n)}{\mathrm{log}p}}\rfloor $, that is, ${p}^{r(p,n)}\le 2n$.
Now $\left({\displaystyle \genfrac{}{}{0pt}{}{2n}{n}}\right)={\displaystyle \prod _{p}}{p}^{r(p,n)}$. By the inequality^{} just proved, primes larger than $2n$ do not contribute to this product^{}, and by assumption^{} there are no primes between $n$ and $2n$. So
$$\left(\genfrac{}{}{0pt}{}{2n}{n}\right)=\prod _{\begin{array}{c}1\le p\le n\\ p\text{prime}\end{array}}{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 $r(p,n)$ and find that it is zero. So for all $n>4$, the contribution of the primes larger than $\frac{2n}{3}$ is zero.
If $p>\sqrt{2n}$, all the terms for higher powers of $p$ vanish and $r(p,n)=\lfloor {\displaystyle \frac{2n}{p}}\rfloor -2\lfloor {\displaystyle \frac{n}{p}}\rfloor $. Since $r(p,n)$ 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 $\mathrm{exp}\left(\vartheta (\frac{2n}{3})\right)$, where $\vartheta (n)$ is the Chebyshev function^{}
$$\vartheta (n)=\sum _{\begin{array}{c}p\le n\\ p\text{prime}\end{array}}\mathrm{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
$$\frac{{4}^{n}}{{(2n)}^{2}}\le \left(\genfrac{}{}{0pt}{}{2n}{n}\right)\le {(2n)}^{\sqrt{2n}}\mathrm{exp}\left(\vartheta (\frac{2n}{3})\right).$$ |
Taking logarithms and applying the upper bound of $n\mathrm{log}4$ for $\vartheta (n)$ (http://planetmath.org/UpperBoundOnVarthetan), we obtain the inequality $\frac{n}{3}\mathrm{log}4\le (\sqrt{2n}+2)\mathrm{log}(2n)$, which is false for sufficiently large $n$, say $n={2}^{11}$. This shows that $$.
Since the conditions $n\ge 2503$ and $$ are incompatible, there are no counterexamples^{} to the claim. ∎
References
- 1 G.H. Hardy, E.M. Wright, An Introduction to the Theory of Numbers, Oxford University Press, 1938.
Title | Bertrand’s conjecture, proof of |
---|---|
Canonical name | BertrandsConjectureProofOf |
Date of creation | 2013-03-22 13:18:55 |
Last modified on | 2013-03-22 13:18:55 |
Owner | CWoo (3771) |
Last modified by | CWoo (3771) |
Numerical id | 15 |
Author | CWoo (3771) |
Entry type | Proof |
Classification | msc 11N05 |