In mathematics, Bertrand's postulate (now a theorem) states that, for each
First conjectured in 1845 by Joseph Bertrand,[1] it was first proven by Chebyshev, and a shorter but also advanced proof was given by Ramanujan.
[2] The following elementary proof was published by Paul Erdős in 1932, as one of his earliest mathematical publications.
[3] The basic idea is to show that the central binomial coefficients must have a prime factor within the interval
This is achieved through analysis of their factorizations.
The main steps of the proof are as follows.
First, one shows that the contribution of every prime power factor
in the prime decomposition of the central binomial coefficient
As a consequence of these bounds, the contribution to the size of
Since the asymptotic growth of the central binomial coefficient is at least
, the conclusion is that, by contradiction and for large enough
, the binomial coefficient must have another prime factor, which can only lie between
are verified by direct inspection, which completes the proof.
The proof uses the following four lemmas to establish facts about the primes present in the central binomial coefficients.
, we have Proof: Applying the binomial theorem, since
terms (including the initial
, that is, the largest natural number
is given by Legendre's formula so But each term of the last summation must be either zero (if
in the denominator from one copy of the term
in the preconditions of the lemma ensures that
is too large to be a term of the numerator, and the assumption that
is odd is needed to ensure that
An upper bound is supplied for the primorial function, where the product is taken over all prime numbers
Proof: We use complete induction.
Let us assume that the inequality holds for all
is composite, we have Now let us assume that the inequality holds for all
appear only in the numerator, we have Therefore, Assume that there is a counterexample: an integer n ≥ 2 such that there is no prime p with n < p < 2n.
has at most one factor of p. By Lemma 2, for any prime p we have pR(p,n) ≤ 2n, and
Then, starting with Lemma 1 and decomposing the right-hand side into its prime factorization, and finally using Lemma 4, these bounds give: Therefore Taking logarithms yields By concavity of the right-hand side as a function of n, the last inequality is necessarily verified on an interval.
, we obtain But these cases have already been settled, and we conclude that no counterexample to the postulate is possible.