Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 5 down vote accepted

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.

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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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