## You are here

HomeBertrand's conjecture, proof of

## Primary tabs

# 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!$ is $\displaystyle\sum_{j}\left\lfloor\frac{n}{p^{j}}\right\rfloor$, where $\lfloor x\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,\dots,n$ is divisible by $p$, so contributes a factor to $p^{k}$. There are $\displaystyle\left\lfloor\frac{n}{p}\right\rfloor$ such factors. Every $p^{2}$th term contributes an extra factor above that, providing $\displaystyle\left\lfloor\frac{n}{p^{2}}\right\rfloor$ new factors. In general, the $p^{j}$th terms contribute $\displaystyle\left\lfloor\frac{n}{p^{j}}\right\rfloor$ extra factors to $p^{k}$. So the highest power of $p$ dividing $n!$ is $\displaystyle\sum_{j}\left\lfloor\frac{n}{p^{j}}\right\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 $n<p<2n$.

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\geq 2503$.

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

$\binom{2n}{n}\geq\frac{4^{n}}{2n+1}\geq\frac{4^{n}}{(2n)^{2}}.$ |

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

$r(p,n)=\sum_{{j\geq 1}}\left\lfloor\frac{2n}{p^{j}}\right\rfloor-2\sum_{{j\geq 1% }}\left\lfloor\frac{n}{p^{j}}\right\rfloor=\sum_{{j\geq 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 $\displaystyle r(p,n)\leq\left\lfloor\frac{\log(2n)}{\log p}\right\rfloor$, that is, $p^{{r(p,n)}}\leq 2n$.

Now $\displaystyle\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

$\binom{2n}{n}=\prod_{{\substack{1\leq p\leq 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.

If $p>\sqrt{2n}$, all the terms for higher powers of $p$ vanish and $\displaystyle r(p,n)=\left\lfloor\frac{2n}{p}\right\rfloor-2\left\lfloor\frac{% n}{p}\right\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 $\exp\left(\vartheta(\frac{2n}{3})\right)$, where $\vartheta(n)$ is the Chebyshev function

$\vartheta(n)=\sum_{{\substack{p\leq 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)}}\leq 2n$ their product is less than $(2n)^{{\sqrt{2n}}}$. Combining this information, we get the inequality

$\frac{4^{n}}{(2n)^{2}}\leq\binom{2n}{n}\leq(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\leq(\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\geq 2503$ and $n<2^{{11}}$ 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.

## Mathematics Subject Classification

11N05*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections