At the end of this message there are two steps that I do not understand. The proof wants to show in the end that :

  • $$\theta(n) \le \theta(2^{k+1}) < 4\cdot \log[2n]$$

by definition we have

  • $$\theta(x) = \sum_{p \le x} \log[p]$$

I got the first steps so far and came to:

$$\pi (n) \cdot \frac{\log[n]}{n} < \frac{3}{2} \cdot \frac{\theta(n)}{n} + \frac{\log(n)}{n^{1/3}}$$

Now the second step for me was to show:

  • $$\theta(2n) - \theta(n) = \log \cdot \prod_{n < p \leq 2n} p$$

I did this by using the definition of $\theta(x)$ (see above) and using the third logarithm law.

Now I got a hint which I did not understand:

For $n < p \leq 2n$ then $p$ is a prime divisor of binomial $\binom{2n}n$. The prime factorization of $\binom{2n}n$ thus contains all of those prime divisors.

  • Why???

Now you can conclude:

$$\prod_{n < p \leq 2n} p \leq \binom{2n}n < \sum_{k=0}^{2n} \binom{2n}k = 2^{2n}$$

  • The $\leq$ I don't understand.
  • The $<$ should work since the right sum contains the left binom AND other binoms as well, at least $\binom{2n}2n$ which is 1. So its sum is greater.
  • The right side is obvious.

The binomial coefficient $\binom{2n}{n}$ is an integer for all $n\geq 1$. It also has the form

$$ \binom{2n}{n} = \frac{(2n)!}{(n!)^2}.$$

Each prime prime between $n<p\leq 2n$ certainly appears at least once (actually exactly once) in the prime factorisation of $(2n)!$, because that's the product of all numbers less than $2n$.

Also, if $p>n$ then it doesn't appear in the prime factorisation of $n!$, since that's the product of numbers $\leq n$. Hence it doesn't appear in $(n!)^2$ either.

So each prime $n<p\leq 2n$ appears once in the numerator of the fraction above, and never in the denominator, so must divide $\binom{2n}{n}$.

Since each prime $n<p\leq 2n$ divides $\binom{2n}{n}$ it follows that

$$ \prod_{n<p\leq 2n}p \mid \binom{2n}{n},$$

and hence certainly the left hand side is at most the right hand side.

This trick of looking at the primes which divide binomial coefficient can be very useful - with some more effort, for example, Erdos used it to show that the equation $\binom{n}{k}=m^\ell$ has no integer solutions with $\ell\geq 2$ and $4\leq k\leq n-4$.


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.