Show that $ (n+1)(n+2)\cdots(2n)$ is divisible by $ 2^n$, but not by $ 2^{n+1}$

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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

Answer 4

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