<s>[INST] Show that $ (n+1)(n+2)\cdots(2n)$ is divisible by $ 2^n$, but not by $ 2^{n+1}$ darij grinberg's note: 
I. Niven, H. S. Zuckerman, H. L. Montgomery, An introduction to the theory of numbers, 5th edition 1991, §1.4, problem 4 (b)


Let $n$ be a nonnegative integer. Show that $ (n+1)(n+2)\cdots(2n)$ is divisible by $ 2^n$, but not by $ 2^{n+1}$.

I have no idea how to prove this. Can anyone help me through the proof. Thanks. 
 [/INST] Let's count directly:
The number of multiples $m_2$ of $2$ between $n+1$ and $2n$ is $\left\lfloor \frac {2n}2 \right\rfloor-\left\lfloor \frac {n}2 \right\rfloor$ (we take the multiples of $2$ up to $2n$ and subtract the number up to $n$).
The number of multiples $m_4$ of $4$ between $n+1$ and $2n$ is $\left\lfloor \frac {2n}4 \right\rfloor-\left\lfloor \frac {n}4 \right\rfloor$
The number of multiples $m_8$ of $8$ between $n+1$ and $2n$ is $\left\lfloor \frac {2n}8 \right\rfloor-\left\lfloor \frac {n}8 \right\rfloor$
Now consider $$\sum_{r=1}^\infty m_{2^r}$$
This counts each multiple of $2$. Every multiple of $4$ is counted twice - as a multiple of $2$ and a multiple of $4$, and every multiple of $2^r$ is counted $r$ times. Also, when $2^r\gt 2n$ we have $m_{2^r}=0$ so the sum is finite (we could calculate a finite upper limit).
Adding the $m_{2^r}$ we see that every term apart from the first cancels, because $\left\lfloor \frac {2n}{2^{r+1}} \right\rfloor=\left\lfloor \frac {n}{2^{r}} \right\rfloor$  leaving the exact power of $2$ which divides the product as $\left\lfloor \frac {2n}{2} \right\rfloor=n$.
</s>