A proof from my book. This theorem was needed to estimate (from below) the growth function of Okninski’s semigroup. For every natural number let denote the number of primes . Say, , , , etc. The next theorem was proved by Chebyshev in 1850. We present a proof based on some ideas of Erdos (he used these ideas to prove another Chebyshev theorem that for every natural there is a prime between and ).
THEOREM There exists a constant such that for every natural number we have
PROOF. The inequality is obvious, so we should only prove the inequality For every natural number consider the middle binomial coefficient in the Newton expansion of .
EXERCISE 1. Prove that . HINT: Use the Pascal triangle formula to prove that the middle binomial coefficient is the biggest one. Then use the fact that the sum of the binomial coefficients is , and the number of them is .
For a prime and a number we define as the largest exponent of that divides . Note that and if divides , then .
EXERCISE 2. For every natural number and prime we have where is such that . HINT: There are numbers that are divisible by , numbers that are divisible by , etc.
LEMMA. If , i.e., divides , then .
PROOF. Let be the natural number such that . Then by Exercise 2.
because for every positive real number we have . Therefore Now let us deduce the theorem from this lemma. Since for every , we can assume that is even. Let . Every prime that divides does not exceed . Therefore , where all primes are different and , so . Hence By Lemma, each does not exceed . Hence by Exercise 1
for some Thus .