Proof of Bertrand's postulate

(One statement of) Bertrand's postulate is that for each <math> n \ge 2 </math> there is a prime p such that <math> n < p < 2n </math>. It was first proven by Pafnuty Chebyshev, but the grist of the following elementary but involved proof by contradiction is due to Paul Erdös:

Define

<math> \theta(x) \equiv \sum_{p \in \mathbb{P} }^{x} \ln (p) </math>

Lemma

<math> \theta(n) < n \cdot \ln(4) \qquad (n\in\mathbb{N}^+) </math>

Proof

• n = 1:

<math> \theta(1)= 0 < 1 \cdot \ln(4) </math>

• n = 2:

<math> \theta(2)=\ln(2) < 2 \cdot \ln(4) </math>

• <math> n>2 </math> and n is even:

<math> \theta(n) = \theta(n-1) < (n-1) \cdot \ln(4) < n \cdot \ln(4) </math> (by induction)

• <math> n>2 </math> and n is odd. Let n = 2m+1 with m > 0:

<math> 4^m = \frac {(1+1)^{2m+1}}{2} = \frac {\sum_{k=0}^{2m+1}{2m+1 \choose k}} {2} = \frac {x+{2m+1 \choose m}+{2m+1 \choose m+1}}{2} \ge {2m+1 \choose m} </math>

Each prime p with <math> m+1 < p \le 2m+1 </math> divides <math> {2m+1 \choose m} </math> giving us:

<math> \theta(2m+1) - \theta(m+1) \le \ln(4^m) = m \cdot \ln(4) </math>

By induction <math> \theta(m+1) < (m+1) \cdot \ln 4 </math>, so:

<math> \theta(n) = \theta(2m+1) < (2m+1) \cdot \ln(4) = n \cdot \ln(4) </math>

Q.E.D.

Assume there is a counterexample n to there existing a prime p with <math> n<p<2n </math>.

If <math> 2 \le n < 2048 </math>, then one of the prime numbers 3, 5, 7, 13, 23, 43, 83, 163, 317, 631, 1259 and 2503 (each being less than twice its predecessor), call it p, will satisfy <math> n < p < 2n </math>. Therefore <math> n \ge 2048 </math>.

<math> 4^n=(1+1)^{2n}=\sum_{k=0}^{2n}{2n \choose k} </math>

Since <math> {2n \choose n} </math> is the largest term in the sum we have:

<math> \frac {4^n} {2n+1} \le {2n \choose n} </math>

Define <math> R(p,n) </math> to be highest number x, such that <math> p^x </math> divides <math> {2n \choose n} </math>. Since n! has <math> \sum_{j=1}^\infty \left \lfloor \frac {n} {p^j} \right \rfloor </math> factors of p we get:

<math> R(p,n)=\sum_{j=1}^\infty \left \lfloor \frac {2n} {p^j} \right \rfloor-2\sum_{j=1}^\infty \left \lfloor \frac {n} {p^j} \right \rfloor=\sum_{j=1}^\infty \left \lfloor \frac {2n} {p^j} \right \rfloor - 2\left \lfloor \frac {n} {p^j} \right \rfloor </math>

Since each term <math> \left \lfloor \frac {2n} {p^j} \right \rfloor - 2\left \lfloor \frac {n} {p^j} \right \rfloor </math> can either be 0 <math> (\frac {n} {p^j} < 1/2) </math> or 1 <math> (\frac {n} {p^j} \ge 1/2) </math> and all terms with <math> j> \left \lfloor \frac {\ln(2n)} {\ln(p)} \right \rfloor </math> are 0 we get:

<math> R(p,n) \le \left \lfloor \frac {\ln(2n)} {\ln(p)} \right \rfloor </math>

For <math> p > \sqrt{2n} </math> we have <math> \left \lfloor \frac {\ln (2n)} {\ln(p)} \right \rfloor \le 1 </math> or <math> R(p,n) = \left \lfloor \frac {2n} {p} \right \rfloor - 2\left \lfloor \frac {n} {p} \right \rfloor </math>.

<math> {2n \choose n} </math> has no prime factors p such that:

• 2n < p, because 2n is the largest factor.
• <math> n<p \le 2n </math>, because of a trivial expansion of the original assumption.
• <math> \frac {2n} {3} <p \le n </math>, because <math> p > \sqrt{2n} </math> (since <math> n \ge 5 </math>) which gives us <math> R(p,n) = \left \lfloor \frac {2n} {p} \right \rfloor - 2\left \lfloor \frac {n} {p} \right \rfloor = 2-2 = 0 </math>.

Each prime factor of <math> {2n \choose n} </math> is therefore not larger than <math> \frac {2n} {3} </math>.

<math> {2n \choose n} </math> has at most one factor of every prime <math> p > \sqrt{2n} </math>. As <math> p^{R(p,n)} \le 2n </math>, the product of <math> p^{R(p,n)} </math> over all other primes is at most <math> (2n)^\sqrt{2n} </math>. Since <math> {2n \choose n} </math> is the product of <math> p^{R(p,n)} </math> over all primes p, we get:

<math> \frac {4^n}{2n+1} \le {2n \choose n} \le (2n)^\sqrt{2n} \prod_{p \in \mathbb{P} }^{\frac {2n} {3}} p = (2n)^\sqrt{2n} e^{\theta(\frac {2n} {3})} </math>

Using our lemma <math> \theta(n) < n \cdot \ln(4) </math>:

<math> \frac {4^n} {2n+1} \le (2n)^\sqrt{2n} 4^{\frac {2n} {3}} </math>

Since we have <math> (2n+1) < (2n)^2 </math>:

<math> 4^{\frac {n}{3}} \le (2n)^{2+\sqrt{2n}} </math>

Also <math> 2 \le \frac {\sqrt{2n}}{3} </math> (since <math> n \ge 18 </math>):

<math> 4^{\frac {n}{3}} \le (2n)^{\frac {4} {3}\sqrt{2n}} </math>

Taking logarithms:

<math> \sqrt{2n} \ln(2) \le 4 \cdot \ln(2n) </math>

Substituting 2n for <math> 2^{2t} </math>:

<math> \frac {2^t} {t} \le 8 </math>

This gives us t<6 and the contradiction:

<math>n=\frac {2^{2t}} {2}<\frac {2^{2 \cdot 6}} {2}=2048</math>

Thus no counterexample to the postulate is possible.

Q.E.D.