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

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