proof of bertrand's postulate

In mathematics, Bertrand's postulate states that for each n ≥ 2 there is a prime p such that n < p < 2n. It was first proven by Pafnuty Chebyshev; the gist of the following elementary but involved proof by contradiction is due to Paul Erdős. We denote the set of prime numbers with

\Bbb{P}

and define:

\theta(x) = \sum_{p\in\Bbb{P};\, p\leq x} \ln (p)

Lemma

\theta(n) < n \cdot \ln(4)

for all integers

n\ge 1

Proof

n = 1:

\theta(1)= 0 < 1 \cdot \ln(4)

n = 2:

\theta(2)=\ln(2) < 2 \cdot \ln(4)

n > 2 and n is even:

\theta(n) = \theta(n-1) < (n-1) \cdot \ln(4) < n \cdot \ln(4)

(by induction)

(because every even no. is not prime, so the sum is aligned with the previous prime)

$n>2$ and n is odd. Let n = 2m+1 with m > 0:

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}

Each prime p with

m+1 < p \le 2m+1

divides

{2m+1 \choose m}

giving us:

\theta(2m+1) - \theta(m+1) \le \ln(4^m) = m \cdot \ln(4)

By induction

\theta(m+1) < (m+1) \cdot \ln  4

, so:

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

Q.E.D. Now for the proof of Bertrand's postulate. Assume there is a counterexample: an integer n ≥ 2 such that there is no prime p with n < p < 2n. If 2 ≤ n < 2048, 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 n < p < 2n. Therefore n ≥ 2048.

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

Since

{2n \choose n}

is the largest term in the sum we have:

\frac {4^n} {2n+1} \le {2n \choose n}

Define

R(p,n)

to be highest number x, such that

p^x

divides

{2n \choose n}

. Since n! has

\sum_{j=1}^\infty \left \lfloor \frac {n} {p^j} \right \rfloor

factors of p we get:

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

But each term

\left \lfloor \frac {2n} {p^j} \right \rfloor - 2\left \lfloor \frac {n} {p^j} \right \rfloor

can either be 0

(\frac {n} {p^j} \mod 1 < 1/2)

or 1

(\frac {n} {p^j} \mod 1 \ge 1/2)

and all terms with

j> \left \lfloor \frac {\ln(2n)} {\ln(p)} \right \rfloor

are 0. Therefore

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

, and we get:

p^{R(p,n)} = \exp \left ( R(p,n) \ln p \right ) \le \exp \left ( \left \lfloor \frac {\ln(2n)} {\ln(p)} \right \rfloor \ln p \right ) \le 2n

For

p > \sqrt{2n}

we have

\left \lfloor \frac {\ln (2n)} {\ln(p)} \right \rfloor \le 1

R(p,n) = \left \lfloor \frac {2n} {p} \right \rfloor - 2\left \lfloor \frac {n} {p} \right \rfloor

{2n \choose n}

has no prime factors p such that:

2n < p, because 2n is the largest factor.
$n, because we assumed there is no such prime number.$
$\frac {2n} {3} , because p > \sqrt{2n} (since n \ge 5) which gives us R(p,n) = \left \lfloor \frac {2n} {p} \right \rfloor - 2\left \lfloor \frac {n} {p} \right \rfloor = 2-2 = 0 .$

Each prime factor of

{2n \choose n}

is therefore not larger than

\frac {2n} {3}

{2n \choose n}

has at most one factor of every prime

p > \sqrt{2n}

. As

p^{R(p,n)} \le 2n

, the product of

p^{R(p,n)}

over all other primes is at most

(2n)^\sqrt{2n}

. Since

{2n \choose n}

is the product of

p^{R(p,n)}

over all primes p, we get:

\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})}

Using our lemma

\theta(n) < n \cdot \ln(4)

\frac {4^n} {2n+1} \le (2n)^\sqrt{2n} 4^{\frac {2n} {3}}

Since we have

(2n+1) < (2n)^2

4^{\frac {n}{3}} \le (2n)^{2+\sqrt{2n}}

Also

2 \le \frac {\sqrt{2n}}{3}

(since

n \ge 18

4^{\frac {n}{3}} \le (2n)^{\frac {4} {3}\sqrt{2n}}

Taking logarithms:

\sqrt{2n} \ln(2) \le 4 \cdot \ln(2n)

Substituting 2^2t for 2n:

\frac {2^t} {t} \le 8

This gives us t < 6 and the contradiction:

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

Thus no counterexample to the postulate is possible. Q.E.D.

<< Previous

Word Browser

Next >>

johann simon hermstedt
akitaro daichi
project mac
project a ko
j.c.r. licklider
concise oxford dictionary
windaria
argument from free will
weasel war dance
durham regional municipality, ontario
toronto argonauts

list of christian scientists
saskatchewan roughriders
calgary stampeders
winnipeg blue bombers
bioalcohol
ambulatory patient group
apg
labial click
honor system
batch 11
chimney sweep

futurepop
rdos
province of china
broadcast
1845 in music
list of sociologists
kruder & dorfmeister
list of species in folklore and mythology
bossanova
chahar (province)
mute swan

bill & ted's bogus journey
joint product pricing
stan marsh
mikhail kasyanov
the ninth configuration
california's gold
seir (demon)
vine (demon)
bifrons (demon)
vanadinite
cord automobile