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. 
 A: Hint
Prove by induction that
$$(n+1)\cdots(2n)=\frac{(2n)!}{n!}=a_n 2^n$$
where $a_n$ is an odd number satisfying the relation
$$a_{n+1}=(2n+1)a_n$$ and recall that the product of two odd numbers is also odd.
A: 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$.
A: Consider the product to be $P$.
Then $P$ is $\frac{(2n)!}{n!}$.
Now evaluate $(2n)!$ as 
$$(2n)!={(2n)\cdot (2n-2)\cdot \ldots (4)\cdot (2)}{(2n-1)\cdot(2n-3)\ldots 3\cdot 1} .$$
The $(2n) \cdot (2n-2) \cdot ... (4) \cdot (2)$ part of the right hand side can be rewritten as $2^n (n!)$, so we get
$$(2n)!=2^n(n!){(2n-1)\cdot (2n-3)\ldots 3\cdot 1} .$$
Therefore 
$$P = 2^n(\text{product of odd numbers from } 1 \text{ to }(2n-1)) .$$
Hence proved
A: You can do it by induction. The base case is easy. For the induction step, suppose the result is true for $n=k$. So we assume that we know that
$$(k+1)(k+2)\cdots(2k)\tag{1}$$
is divisible by $2^k$ but not by $2^{k+1}$. 
Now the product when $n=k+1$ is
$$(k+2)(k+3)\cdots(2k)(2k+1)(2k+2).\tag{2}$$
To get from the product  (1) to the product (2), we multiply (1) by $\frac{(2k+1)(2k+2)}{k+1}=2(2k+1)$. Thus the product (2) has "one more $2$" than the product (1). 
