A short proof of Chebyshev’s inequality

A proof from my book. This theorem was needed to estimate (from below) the growth function of Okninski’s semigroup. For every natural number $n$ let $\pi(n)$  denote the number of primes $\le n$. Say, $\pi(1)=0$, $\pi(2)=1$, $\pi(10)=4$, 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 $n$ there is a prime between $n$ and $2n$).

THEOREM  There exists a constant $c>0$ such that for every natural number $n$ we have $\frac{cn}{\ln n}\le \pi(n)\le n-1.$

PROOF. The inequality $\pi(n)\le n-1$ is obvious, so we should only prove the inequality $\frac{cn}{\ln n}\le \pi(n).$ For every natural number $m$ consider the middle binomial coefficient $\binom{2m}{m}$ in the Newton expansion of $(1+1)^{2m}=4^m$.

EXERCISE 1.  Prove that $\binom{2m}{m}\ge \frac{4^m}{2m+1}$. 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 $4^m$, and the number of them is $2m+1$.

For a prime $p$ and a number $m$ we define $o_p(m)$ as the largest exponent of $p$ that divides $m$. Note that $o_p(m_1m_2)=o_p(m_1)+o_p(m_2)$ and if $m_2$ divides                $m_1$, then $o_p(\frac{m_1}{m_2})=o_p(m_1)-o_p(m_2)$.

EXERCISE 2. For every natural number $m$ and prime $p$ we have $o_p(m!)=\sum_{i=1}^{r} \left\lfloor \frac{m}{p^i}\right\rfloor$ where $r$ is such that $p^r\le m\le p^{r+1}$. HINT: There are $\left\lfloor \frac mp\right\rfloor$ numbers $\le m$ that are divisible by $p$, $\left\lfloor \frac{m}{p^2}\right\rfloor$ numbers $\le m$ that are divisible by $p^2$, etc.

LEMMA. If $k=o_p(\binom{2m}{m})>0$, i.e., $p$ divides $\binom{2m}{m}$, then $p^k\le 2m$.

PROOF. Let $r$ be the natural number such that $p^r\le 2m . Then by Exercise 2.

$k=o_p\left(\binom{2m}{m}\right)=o_p((2m)!)-2o_p(m!)=\sum_{i=1}^r \left\lfloor \frac{2m}{p^i}\right\rfloor -2\sum_{i=1}^r \left\lfloor \frac m{p^i}\right\rfloor = \sum_{i=1}^r (\left\lfloor \frac{2m}{p^i}\right\rfloor -2\left\lfloor \frac m{p^I}\right\rfloor) \le r$

because for every positive real number $x$ we have $\left\lfloor 2x\right\rfloor - 2\left\lfloor x\right\rfloor \le 1$. Therefore $p^k\le p^r\le 2m.$ Now let us deduce the theorem from this lemma. Since $\pi(n+1)\le \pi(n)+1$ for every $n$, we can assume that $n=2m$ is even. Let $k=\pi(2m)$. Every prime that divides $\binom{2m}{m}$ does not exceed $2m$. Therefore $\binom{2m}{m}=\prod_{i=1}^\ell p_i^{a_i}$, where all primes $p_i$ are different and $p_i\le 2m$, so $\ell \le k$. Hence $\ln \binom{2m}{m}=\sum a_i\ln p_i.$ By Lemma, each $a_i\ln p_i$ does not exceed $\ln 2m$. Hence by Exercise 1

$\ell\ge \frac{\ln \binom{2m}{m}}{\ln(2m)}\ge \frac{\ln \frac{4^m}{2m+1}}{\ln(2m)} \ge c\frac{2m}{\ln(2m)}$

for some $c>0.$ Thus $\pi(2m)\ge c\frac{2m}{\ln(2m)}$.