4
$\begingroup$

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 Answers 1

6

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.

  • 0
    Thank you. I wasn't connecting that since each $p$ divides $(2n)!$ that \displaystyle\prod_{n < p \leq 2n} p also divides $(2n)!$.2011-11-27