5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – hardmath Apr 30 at 16:29
  • $\begingroup$ This specific Question was among those listed in a recent Meta Math.SE post. $\endgroup$ – hardmath Apr 30 at 16:41
18
$\begingroup$

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

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.