Newsgroups: sci.math
From: Robin Chapman <rjc@maths.ex.ac.uk>
Subject: Bertrand's Postulate
Date: Wed, 22 Oct 1997 10:35:49 GMT

The result that for each positive integer n>=2 there is a prime
p with n < p < 2n is known as Bertrand's postulate (even though it
is a theorem). Regulary requests for proofs occur on sci.math,
so I have decided to post a complete proof here, so that
interested parties can be directed to it.

Bertrand's postulate.

This proof is due to Erd"os. However this account is based on my reading
of Hardy/Wright, Introduction to the theory of Numbers and Rose,
A Course in Number Theory (both Oxford UP). Any deficencies/errors
are mine alone.

We need to prove a bound due to Chebyshev on the theta function.
This is defined by theta(n) = sum_{p <= n} log p, where p
runs over primes. Chebyshev's bound is theta n <= n log 4 for all
integers n. We use induction. The cases of n = 1 and 2 are trivial.
If n > 2 is even then the case of n is immediate from the case of n-1.
So let n = 2m+1 be odd with m > 0. The binomial coefficient
(2m+1 choose m) =(2m+1)!/(m!(m+1)!) occurs twice in the binomial
theorem expansion of (1+1)^{2m+1}, and so (2m+1 choose m) <= 4^m.
But each prime p with m+1 < p <= 2m+1 divides (2m+1 choose m)
and so theta(2m+1) - theta(m+1) <= log(4^m) = m log 4. Inductively
theta(m+1) <= (m+1) log 4, and so theta(2m+1) <= (2m+1)log 4,
establishing Chebyshev's bound.

Now to the main proof. Suppose that n>=2 and there is no prime p with
n < p < 2n. Suppose first that n >= 2^11 = 2048. As
(2n choose n) is the largest term in the binomial expansion of
(1+1)^{2n} then (2n choose n) >= 4^n/(2n+1). For a prime p we shall
denote the power of p dividing (2n choose n) by r(p,n). This number
is the sum of [2n/p^j] - 2[n/p^j] over all j, where [x] denotes the
integer part of x. Each of these terms is 0 or 1, and they vanish for
j > [log 2n/log p]. So r(p,n) <= [log 2n/log p]. Consequently
p^{r(p,n)} <= 2n. For p > sqrt{2n} we have [log 2n/log p] <= 1.
Hence for p > sqrt(2n) we have r(p,n) = [2n/p] - 2[n/p]. By assumption
there are no primes p with n < p < 2n. If 2n/3 < p <= n, then
p > sqrt(2n) and r(p,n) =  2-2 = 0. Thus each prime factor of
(2n choose n) is <= 2n/3. Hence an upper bound for
(2n choose n), which is the product of all p^{r(p,n)} over all
primes p, is (2n)^sqrt(2n) exp(theta(2n/3)). The former factor takes
into consideration all primes with p <= sqrt{2n}, the latter all
other primes. Using the lower bound for (2n choose n) and Chebyshev
we get
	4^n/(2n+1) <= (2n)^sqrt(2n) 4^{2n/3}.
For our values of n, (2n+1) < (2n)^2 and so
	4^{n/3} <= (2n)^{2+sqrt(2n)}.
Also 2 <= sqrt{2n}/3 and
	4^{n/3} <= (2n)^{4 sqrt(2n)/3}.
Taking logarithms gives
	sqrt(2n) log 2 <= 4 log 2n.
Now write 2n = 2^{2t} so that t >= 6. This becomes
	2^t/t <= 8.
The function x |--> 2^x/x is increasing for x > 1/log 2.
So 2^t/t >= 2^6/6 > 10, a contradiction.

Now assume 2 <= n < 2^11. Then one of the prime numbers 3, 5, 7, 13,
23, 43, 83, 163, 317, 631, 1259, 2503 satisfies n < p < 2n as each
is less than twice its predecessor. This completes the proof.

-- 
Robin Chapman			 	"256 256 256.
Department of Mathematics		 O hel, ol rite; 256; whot's
University of Exeter, EX4 4QE, UK	 12 tyms 256? Bugird if I no.
rjc@maths.exeter.ac.uk             	 2 dificult 2 work out."
http://www.maths.ex.ac.uk/~rjc/rjc.html	 Iain M. Banks - Feersum Endjinn