| Version 7 |
Version 6 |
| \PMlinkescapeword{term} |
\PMlinkescapeword{term} |
| \PMlinkescapeword{terms} |
|
| \PMlinkescapeword{conjecture} |
|
| \PMlinkescapeword{minimal} |
|
| \PMlinkescapeword{formula} |
|
| \PMlinkescapeword{information} |
|
|
|
|
\begin{proof} |
| This is a version of Erd\H{o}s's proof as it appears in Hardy and Wright. |
This is a version of Erd\H{o}s's proof as it appears in Hardy and Wright. |
|
|
| We begin with the following lemma. |
Let $\vartheta(n)$ be the Chebyshev function |
|
\[ |
|
\begin{lemma*}
|
\vartheta(n)=\sum_{\substack{p\le n\\p{\:\mathrm{prime}}}} \log p.
|
| Let $n$ be a positive integer and $p$ be a prime. The highest power of $p$ dividing $n!$ is $\sum_j\lfloor\frac{n}{p^j}\rfloor$, where $\lfloor x\rfloor$ is the floor of $x$. |
\] |
| \end{lemma*} |
We will apply the \PMlinkname{upper bound}{UpperBoundOnVarthetan} $\vartheta(n)\le n\log 4$. |
|
|
| \begin{proof} |
Suppose $n>2$ and there is no prime $p$ with $n<p<2n$. |
| Let $p^k$ divide $n$ with $k$ as large as possible. Every $p$th term of the sequence $1,\dots,n$ is divisible by $p$, so contributes a factor to $p^k$. There are $\lfloor\frac{n}{p}\rfloor$ such factors. Every $p^2$th term contributes an extra factor above that, providing $\lfloor\frac{n}{p^2}\rfloor$ new factors. In general, the $p^j$th terms contribute $\lfloor\frac{n}{p^j}\rfloor$ extra factors to $p^k$. So the highest power of $p$ dividing $n!$ is $\sum_j\lfloor\frac{n}{p^j}\rfloor$. |
|
| \end{proof} |
|
|
|
|
We now prove the theorem.
|
The \PMlinkname{binomial expansion}{BinomialTheorem} of $(1+1)^{2n}$ has $2n+1$ terms and has largest term $\binom{2n}{n}$. Hence $\binom{2n}{n}\ge\frac{4^n}{2n+1}$.
|
|
|
| \begin{proof}[Bertrand's conjecture] |
For a prime $p$ define $r(p,n)$ to be the highest power of $p$ dividing $\binom{2n}{n}$. We first look at the highest power of $p$ dividing $n!$. Every $p$-th term contributes a factor, so we have already $[\frac{n}{p}]$ factors, where $[x]$ is the integer part (or equivalently, since every number we are dealing with is nonnegative, the floor) of $x$. However, every $p^2$-th term contributes an extra factor above that, and every $p^3$-th term one more and so on. So the highest power of $p$ dividing $n!$ is $\sum_j[\frac{n}{p^j}]$. Now for $r(p,n)$ we need to take the factors contributed by $(2n)!$ and subtract twice the factors taken away by $n!$. This leads us to $r(p,n)=\sum_j([\frac{2n}{p^j}]-2[\frac{n}{p^j}])$. Now each of these terms is either $0$ or $1$ (as is every value of $[2x]-2[x]$), and the terms vanish for $j>[\frac{\log(2n)}{\log p}]$, so $r(p,n)\le[\frac{\log(2n)}{\log p}]$ or $p^{r(p,n)}\le 2n$. |
| Let $n>2$ be a minimal counterexample to the claim. Thus there is no prime $p$ such that $n<p<2n$. |
|
|
|
| In the sequence of primes |
Now $\binom{2n}{n}=\prod_p p^{r(p,n)}$. By the previous inequality, primes larger than $2n$ do not contribute to this product and by assumption there are no primes between $n$ and $2n$. So |
| \[ |
\[ |
| 2, 3, 5, 7, 13, 23, 43, 83, 163, 317, 631, 1259, 2503, |
\binom{2n}{n}=\prod_{\substack{1\le p \leq n\\ p{\:\mathrm{prime}}}}p^{r(p,n)}. |
| \] |
\] |
| each succeeding term is smaller than the double of its predecessor. This shows |
|
| that $n\ge 2503$. |
|
|
|
|
The \PMlinkname{binomial expansion}{BinomialTheorem} of $(1+1)^{2n}$ has $2n+1$ terms and has largest term $\binom{2n}{n}$. Hence $\binom{2n}{n}\ge\frac{4^n}{2n+1}\ge\frac{4^n}{(2n)^2}$.
|
If $p>\sqrt{2n}$, all the terms for higher powers of $p$ vanish and $r(p,n)=[\frac{2n}{p}]-2[{{n}\over{p}}]$.
|
|
|
| For a prime $p$ define $r(p,n)$ to be the highest power of $p$ dividing $\binom{2n}{n}$. To compute $r(p,n)$, we apply the lemma to $(2n)!$ and $n!$. We get that |
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. |
| \[ |
|
| r(p,n)=\sum_{j\ge 1}\left\lfloor\frac{2n}{p^j}\right\rfloor |
|
| -2\sum_{j\ge 1}\left\lfloor\frac{n}{p^j}\right\rfloor |
|
| =\sum_{j\ge 1}\left(\left\lfloor\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 |
|
| $r(p,n)\le\left\lfloor\frac{\log(2n)}{\log p}\right\rfloor$, that is, |
|
| $p^{r(p,n)}\le 2n$. |
|
|
|
| Now $\binom{2n}{n}=\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 |
Now for $p>\sqrt{2n}$, $r(p,n)$ is at most $1$, so 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}$ which equals $e^{\vartheta(\frac{2n}{3})}$. There are at most $\sqrt{2n}$ primes smaller than $\sqrt{2n}$ and by the inequality $p^{r(p,n)}\leq 2n$ their product is less than |
| \[ |
$(2n)^{\sqrt{2n}}$. |
| \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 $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. |
Now for $p>\sqrt{2n}$, $r(p,n)$ is at most $1$, so 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}$ which equals $e^{\vartheta(\frac{2n}{3})}$. There are at most $\sqrt{2n}$ primes smaller than $\sqrt{2n}$ and by the inequality $p^{r(p,n)}\leq 2n$ their product is less than |
|
$(2n)^{\sqrt{2n}}$. |
|
|
| If $p>\sqrt{2n}$, all the terms for higher powers of $p$ vanish and $r(p,n)=\lfloor\frac{2n}{p}\rfloor-2\lfloor\frac{n}{p}\rfloor$. |
Combining these we get $$\frac{4^n}{2n+1}\leq{{2n}\choose{n}}\leq (2n)^{\sqrt{2n}}e^{\vartheta(\frac{2n}{3})}.$$ |
| 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 |
|
| $e^{\vartheta(\frac{2n}{3})}$, where $\vartheta(n)$ is the Chebyshev function |
|
| \[ |
|
| \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 |
|
| \[ |
|
| \frac{4^n}{(2n)^2}\le\binom{2n}{n}\le(2n)^{\sqrt{2n}}e^{\vartheta(\frac{2n}{3})}. |
|
| \] |
|
| Taking logarithms and applying the \PMlinkname{upper bound of $n\log 4$ for $\vartheta(n)$}{UpperBoundOnVarthetan}, we obtain the inequality $\frac{n}{3}\log 4\le(\sqrt{2n}+2)\log(2n)$, which is false for sufficiently large $n$, 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. |
Using $2n+1<(2n)^2$ and taking logarithms, we find $n\frac{\log4}{3}\leq (\sqrt{2n}+2)\log(2n)$ which is clearly false for large enough $n$, say $n=2^{11}$, leading to a contradiction. For smaller $n$, we prove the theorem by exhibiting a sequence of primes in which each is smaller than the double of its predecessor, e.g., $3, 5, 7, 13, |
|
23, 43, 83, 163, 317, 631, 1259, 2503$. |
| \end{proof} |
\end{proof} |
|
|
| \begin{thebibliography}{9} |
\begin{thebibliography}{9} |
| \bibitem{HW} |
\bibitem{HW} |
| G.H. Hardy, E.M. Wright, \emph{An Introduction to the Theory of Numbers}, Oxford University Press, 1938. |
G.H. Hardy, E.M. Wright, \emph{An Introduction to the Theory of Numbers}, Oxford University Press, 1938. |
| \end{thebibliography} |
\end{thebibliography} |
