Erdős’s proof of Bertrand’s postulate

In 1845 Bertrand postulated that there is always a prime between n and 2n, and he verified this for n < 3, 000, 000. Tchebychev gave an analytic proof of the postulate in 1850. In 1932, in his first paper, Erdős gave a beautiful elementary proof using nothing more than a few easily verified facts about the middle binomial coefficient. We describe Erdős’s proof and make a few additional comments, including a discussion of how the two main lemmas used in the proof very quickly give an approximate prime number theorem. We also describe a result of Greenfield and Greenfield that links Bertrand’s postulate to the statement that {1,..., 2n} can always be decomposed into n pairs such that the sum of each pair is a prime.