I am working my way through a paper proving the prime number theorem and I have come across the following (to use ${2n \choose n}$ was apparently due to Chebyshev, hence the title):

Lemma: Define $\vartheta(x) = \displaystyle\sum_{p \leq x} \log(p)$ (where $p$ is a prime number). Then, $\vartheta(x)=O(x)$.

Proof: Let $n \in \mathbb{N}$. Then by the binomial theorem,

$$2^{2n} = (1+1)^{2n} = {2n \choose 0} + {2n \choose 1} + \ldots + {2n \choose 2n} \geq {2n \choose n}.$$


$${2n \choose n} = \frac{(2n)!}{(n!)^2} \geq \displaystyle\prod_{n < p \leq 2n} p,$$

since ${2n \choose n}$ is an integer and no prime greater than $n$ can divide $n!$.

(I have no trouble following the rest of the proof, so I omit it.)

My question is how does that last inequality follow from the fact that no such $p$ divides $(n!)$? I don't see how it follows directly, so I have tried to approach it using induction which led me to something like this:

Assuming the inductive hypothesis $\frac{(2k)!}{(k!)^2} \geq \displaystyle\prod_{k < p \leq 2k} p$, I can get

$$\frac{(2(k+1))!}{((k+1)!)^2} \geq \frac{(2k+2)(2k+1)}{(k+1)^2} \displaystyle\prod_{k < p \leq 2k} p.$$

To complete the induction, I'd want to get the statement

$$\frac{(2(k+1))!}{((k+1)!)^2} \geq \displaystyle\prod_{k+1 < p \leq 2(k+1)} p.$$

This makes me think either that induction is not the way to proceed or the step in question is a direct "obvious" step that I am simply not seeing.


Any prime $p$ in the range $\{n+1, n+2, \ldots, 2n\}$ divides $(2n)!$ but not $n!$ (and hence not $n!^2$). Thus the number $$ \binom{2n}{n} = \frac{(2n)!}{n!^2} $$ is divisible each $p \in I$. Since distinct primes are relatively prime, $\binom{2n}{n}$ is divisible by the product $\prod \limits_{n \lt p \leqslant 2n} p$ as well. Finally, since $\binom{2n}{n}$ is nonzero, it follows that it is at least as big as the product.

  • $\begingroup$ Thank you. I wasn't connecting that since each $p$ divides $(2n)!$ that $\displaystyle\prod_{n < p \leq 2n} p$ also divides $(2n)!$. $\endgroup$
    – tomcuchta
    Nov 27 '11 at 22:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.