Help with an inequality used in Chebyshev's proof of $\vartheta(x) = O(x)$

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}.$$

But

$${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.

1 Answer

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.

• 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