Bertrand's Postulate

 I have always been fascinated by Bertrand's Postulate, the claim that there is always a prime number between $n$ and $2n$. When I first heard about it as an undergraduate, I tried proving it for myself but was not able to. I'd like to present here what appears to be a now standard proof of the fact due to Erdös. I am basing my exposition on two articles, one by Aigner and Ziegler from the book "Proofs from the book" as well as a PDF found on Franz Lemmermeyer's webpage.  Lemmermeyer has a short section on Bertrand's Postulate which appears to be largely based on the the Aigner-Ziegler article, but he also has a nice exposition on getting some Prime Number Theorem type estimates, which I want to talk about in my next post.

Let $\Theta(x)$ be the product of all primes less than or equal to $x$. More generally, let $\Theta(x,y)$ be the product of all primes in the interval $[x,y]$.

Here's a neat fact:

Proposition: $\Theta(x)\leq 4^{x-1}$ if $x\geq 2$.

Proof: 

Suppose we know the proposition inductively for all values less than $k$. If $k$ is even, then $\Theta(k)=\Theta(k-1)$, so $\Theta(k)<4^{k-1}<4^k$. If $k=2m+1$ is odd, consider the integer $\binom{2m+1}{m}$. By the Binomial theorem, $\binom{2m+1}{m}<2^{2m+1},$ but in fact, because there are two equal terms $\binom{2m+1}{m}=\binom{2m}{m}$, we get the better inequality  

$$\binom{2m+1}{m}<2^{2m}=4^m.$$

Moreover, we claim that $\Theta(m+2,2m+1)$ divides  $\binom{2m+1}{m}$. To see this, notice that $\binom{2m+1}{m}$ can be written as $\frac{(2m+1)(2m)\cdots(m+2)}{m!}.$ Therefore, all of the primes in the range $[m+2,2m+1]$ are factors of the numerator, and they are all larger primes than can be contained in the denominator.

Now $$\Theta(2m+1)=\Theta(m+1)\Theta(m+2,2m+1)$$

$$\leq\Theta(m+1)\binom{2m+1}{m}$$

$$<4^m\cdot 4^m=4^{2m}.$$

This completes the inductive step. $\Box$

In that argument, we used the upper bound $\binom{2m+1}{m}<4^m$. To proceed, we'll want a lower bound on $\binom{2n}{n}$. Consider the set of binomial coefficients $\{\binom{2n}{0},\binom{2n}{1},\ldots\binom{2n}{2n}\}.$ The average value is the sum $2^{2n}$ divided by $2n+1$. Since the middle term is the largest, we get the inequality $\binom{2n}{n}>\frac{2^{2n}}{2n+1}$. In fact, we can improve this to $$\binom{2n}{n}>\frac{2^{2n}}{2n},$$ by considering the set $\{\binom{2n}{0}+\binom{2n}{2n},\binom{2n}{1},\binom{2n}{2},\cdots,\binom{2n}{2n-1}\}$ instead.

Next, we'll look at what we can say about primes appearing in $N=\binom{2n}{n}.$ It is quite easy to check that no prime in the range $(2/3n,n]$ is a divisor of $N$. Think of $n=\frac{(2n)(2n-1)\cdots(n+1)}{n!}$, and notice that $p$ appears once in the denominator, $2p$ appears once in the numerator, while $3p$ is already out of range. A less obvious pair of facts is the following:

Proposition:  

(a) If a prime $p$ satisfies $p>\sqrt{2n}$, then it appears at most once in $\binom{2n}{n}$.

(b) The exponent of $p$ in $\binom{2n}{n}$ is less than or equal to $2n$.

Proof:

The proof  of both these facts uses the Legendre formula that $n!$ contains the prime factor $p$ exactly $\sum_{k\geq 1}\lfloor \frac{n}{p^k}\rfloor$ times. (Incidentally, the Beast Academy 5th Grade Series from AoPS proves this quite nicely, though not using all of the fancy language.)

So the exponent of $p$ in $N$ is given by $$\sum_{k\geq 1}(\lfloor \frac{2n}{p^k}\rfloor-2\lfloor\frac{n}{p^k}\rfloor).$$

It is a simple exercise to check that $\lfloor 2x\rfloor- 2\lfloor x\rfloor\in\{0,1\}$, so each summand is at most $1$. Moreover the summands vanish as soon as $p^k>2n$, so we can say that the exponent of $p$ in $N$ is at most $\operatorname{max}\{k:p^k\leq 2n\}$. This immediately implies statement (b) of the proposition.

To prove (a), notice that if $p>\sqrt{2n}$, the largest power of $p$ less than $2n$ is $1$, so its exponent in $N$ will be at most $1$. $\Box$

Let $\nu_p$ be the exponent of $p$ in $N$. Write

$$N=\prod_{p\leq \sqrt{2n}}p^{\nu_p} \cdot\prod_{\sqrt{2n}<p<\frac{2}{3}n}p^{\nu_p}\cdot\prod_{n<p\leq 2n}p.$$

Notice that we removed the range $[\frac{2}{3}n,n]$ since there are no prime factors of $N$ here. In a similar way to how we argued previously for $\binom{2m+1}{m}$, every prime from $n$ to $2n$ definitely appears with exponent $1$. We can also note that the exponents on the middle term must be either $0$ or $1$. Now we know that $p^{\nu_p}<2n$ from the (b) statement in the above proposition. So we have $$N\leq (2n)^{\sqrt{2n}}\cdot (4^{\frac{2}{3}n})\cdot (2n)^{P(n)},$$

where $P(n)$ denotes the number of primes between $n$ and $2n$. Recall that we are trying to show $P(n)>0$ in order to establish Bertrand's Postulate. On the other hand $N>\frac{4^n}{2n}$, so we get the following inequality:

$$4^{\frac{n}{3}}<(2n)^{\sqrt{2n}+1+P(n)},$$

and taking logarithms, we have

$$P(n)>\frac{2n}{3\log_2(2n)}-(\sqrt{2n}+1).$$

Now we are basically done. The term $\frac{2n}{3\log_2(2n)}$ is going to dominate $\sqrt{2n}+1$ in the long run, and in fact one can check that the right hand side is positive after $n=468$. One can then just verify by hand or computer that $P(n)>0$ for $n<468$. In fact one just needs to find a sequence of primes where each is smaller than twice the previous until you exceed 468. 

It is interesting to notice that this argument establishes a lot more than Bertrand's Postulate. Not only does it show $P(n)>0$, but it give a pretty substantial lower bound of $\frac{2n}{3\log_2(2n)}-(\sqrt{2n}+1)$.

If we let $\pi(n)$ denote the number of primes $\leq n$, clearly $P(n)<\pi(2n)$, so we also get a lower bound on the number of primes.

$$\pi(2n)\geq \frac{2n}{3\log_2(2n)}-(\sqrt{2n}+1).$$

In fact, using the inequality $\sqrt{2n}-1\geq \frac{21}{4}\log_2(2n)$ for $n\geq 2^{11}$, we get

$$\pi(2n)>P(n)>\frac{1}{7}\frac{2n}{\log_2(2n)}.$$

The Prime Number Theorem says that $\pi(n)$ is asymptotically the same as $\frac{n}{\log n}$, so this estimate is in the same ballpark. 

As a step toward the prime number theorem Chebyshev proved that $c_1 \frac{n}{\log n}\leq \pi(n)\leq c_2 \frac{n}{\log n}$ for some positive constants $c_1$ and $c_2$. Our estimate for $P(n)$ gives $c_1=\frac{\ln 2}{7}$. In our next post we will improve $c_1$ and find a $c_2$ that works, following Lemmermeyer's exposition.