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

• Someone has voted to close this (five year old Question with upvotes and Accepted Answer), possibly for "lack of context". It seems likely that the OP is referencing a note by frequent contributor @darij grinberg at about that time. Such a Comment or other post is difficult (perhaps impossible) to link to now, but it provides sufficient context for my purpose. Apr 30, 2019 at 16:29
• This specific Question was among those listed in a recent Meta Math.SE post. Apr 30, 2019 at 16:41

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

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.

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

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