Bertrand's postulate, also called the Bertrand-Chebyshev theorem or Chebyshev's theorem, states that if 
, there is always at least one prime 
between 
and 
. Equivalently, if 
, then there is always at least one prime 
such that 
. The conjecture was first made by Bertrand in 1845
(Bertrand 1845; Nagell 1951, p. 67; Havil 2003, p. 25). It was proved in
1850 by Chebyshev (Chebyshev 1854; Havil 2003, p. 25; Derbyshire 2004, p. 124)
using non-elementary methods, and is therefore sometimes known as Chebyshev's
theorem. The first elementary proof was by Ramanujan, and later improved by a
19-year-old Erdős in 1932.
A short verse about Bertrand's postulate states, "Chebyshev said it, but I'll say it again; There's always a prime between 
and 
." While commonly attributed to Erdős or to some
other Hungarian mathematician upon Erdős's youthful re-proof the theorem (Hoffman
1998), the quote is actually due to N. J. Fine (Schechter 1998).
An extension of this result is that if 
, then there is a number containing a prime
divisor 
in the sequence 
,
,
..., 
.
(The case 
then corresponds to Bertrand's postulate.) This was first proved by Sylvester, independently
by Schur, and a simple proof was given by Erdős (1934; Hoffman 1998, p. 37)
The numbers of primes between 
and 
for 
, 2, ... are 0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 3, 3, 3, 3, 3,
4, ... (OEIS A077463), while the numbers of
primes between 
and 
are 0, 1, 1, 2, 1, 2, 2, 2, 3, 4, 3, 4, 3, 3, ... (OEIS A060715).
For 
,
2, ..., the values of 
, where 
is the next prime function
are 2, 3, 5, 5, 7, 7, 11, 11, 11, 11, 13, 13, 17, 17, 17, 17, 19, ... (OEIS A007918).
After his proof of Bertrand's postulate, Ramanujan (1919) proved the generalization that 
,
2, 3, 4, 5, ... if 
,
11, 17, 29, 41, ... (OEIS A104272), respectively,
where 
is the prime counting function. The numbers
are sometimes known as Ramanujan primes. The case
for all 
is Bertrand's postulate.
A related problem is to find the least value of 
so that there exists at least one prime
between 
and 
for sufficiently large 
(Berndt 1994). The smallest known value is 
(Lou and Yao 1992).
