# show that $(n+1)(n+2)…(2n)$ is divisible by $2^n$ but not by $2^{n+1}$

Is this proof correct?

Suppose $2^k$ is the largest power of $2$ in the sequence $n+1, n+2, ... 2n$

Then we can compute the power of 2 in the product as $n/2 + n/2^2 + ... n/2^k = n(1 + 2 + .... 2^{k-1})/2^k = n$.

• I think your proof is correct, but you need to round up on the whole expression. For example, when $n=5$, $k=3$, and the expression becomes $\frac{5}{2} + \frac{5}{2^2} + \frac{5}{5^3}$, which rounds up to $5$. Since $151200/(2^5) = 4725$, your answer is correct for this case. – Toby Mak Apr 29 '17 at 23:20
• I didn't get why the sum you wrote down is equal to the power of 2 in the product? – Ramil Apr 29 '17 at 23:32
• $\frac{2^{k-1}}{2^k} = 1/2, \frac{2^{k-2}}{2^k} = 1/4, \frac{2^{k-3}}{2^k} = 1/8$ and so on. Multiplying the expression by $n$ will give the previous step. – Toby Mak Apr 29 '17 at 23:35
• @TobyMak Could you please elaborate more on why do you multiply it by $n$? What do these $1/2, 1/4, 1/8, \dots$ mean? – Ramil Apr 29 '17 at 23:44
• We can factor out an $n$ from the previous expression to get $n(1/2 + 1/4 + 1/8 + 1/16 \cdots)$. If we multiply by $2^k$, we have $n(2^k/2 + 2^{k-1}/2 + 2^{k-2}/2 + 2^{k-3}/2 \cdots)$ Using the division law of indices, we have $n(2^{k-1} + 2^{k-2} + 2^{k-3} + 2^{k-4} \cdots)$. Dividing the whole expression by $2^k$ will give us the second step. – Toby Mak Apr 29 '17 at 23:52

You can also proceed by induction.

Let $a_n = (n+1)(n+2)\ldots(2n)$.

Then $a_{n+1}/a_n = (2n+1)(2n+2)/(n+1) = 2(2n+1)$.
Since $2n+1$ is odd, only one $2$ factor is added at each step.

Since $a_1 = 2^1$, you get $a_n = 2^n \times o_n$ where $o_n$ is an odd number

Note that $$\dfrac{(n+1)(n+2)\dots (2n)}{1\cdot 3 \cdot 5 \dots (2n-1)} = \dfrac{(2n)!/n!}{(2n)!/(2\cdot 4 \cdot 6 \cdot \dots \cdot (2n))} = \dfrac{(2n)!/n!}{(2n)!/(2^n n!)} = 2^n$$

Hence, $$(n+1)(n+2)\dots (2n) = 1\cdot 3 \cdot 5 \dots (2n-1) \cdot 2^n$$

Since the first $n$ multipliers on the right side are all odd, the maximum power of two that divides the product in question is indeed $2^n$.

Here is some intuition behind this solution.

First of all, it is clear that every natural number $m$ can be represented in the form $$m = 2^k \operatorname{maxodd}(m)$$ where $2^k$ is the maximum power of two that divides $m$ and $\operatorname{maxodd}(m)$ is the maximum odd divisor of $m$.

Note that the numbers in the range $[n+1, 2n]$ have different maximum odd divisors. Indeed, if for two different numbers in this range their maximum odd divisors were the same, one of them should be at least two times greater than the other one, which is impossible. This means that each of the number $1, 3, 5, \dots, 2n-1$ (here are exactly $n$ numbers) should be the maximum odd divisor for exactly one number from $[n+1, 2n]$ range.

For example, if $n=5$ then $[n+1, 2n] = \{6, 7, 8, 9, 10\}$ and maximum odd divisors are $\{3, 7, 1, 9, 5\} = \{1, 3, 5, 7, 9\}$.

This means that the power of two in the product is equal to

$$\dfrac{(n+1)(n+2)\dots (2n)}{1\cdot 3 \cdot 5 \dots (2n-1)} = \dfrac{(2n)!/n!}{(2n)!/(2\cdot 4 \cdot 6 \cdot \dots \cdot (2n))} = \dfrac{(2n)!/n!}{(2n)!/(2^n n!)} = 2^n$$

• I think that the statement saying that the first $n$ multipliers are odd is false. If $n$ is even, then $n+2$ is also even. However, if $n$ is odd, then $n+1$ is even. – Toby Mak Apr 30 '17 at 0:12
• @TobyMak I meant the product on the right side. I edited the answer accordingly so that it is clear now. – Ramil Apr 30 '17 at 0:15

$\newcommand{\bbx}{\,\bbox[8px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}{\displaystyle{#1}} \newcommand{\expo}{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}{\mathcal{#1}} \newcommand{\mrm}{\mathrm{#1}} \newcommand{\pars}{\left(\,{#1}\,\right)} \newcommand{\partiald}[]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}{\left\vert\,{#1}\,\right\vert}$ \begin{align} \pars{n + 1}\cdots\pars{2n} & = {\pars{2n}! \over n!} = {\pars{2n}\pars{2n - 1}\pars{2n - 2}\pars{2n - 3}\cdots 3.2 \over n!} = 2^{n}\prod_{k = 1}^{n}\pars{2k - 1} \end{align}

We can write as $$(n+1)(n+2)...(2n)=\frac{2n!}{n!}\tag1$$ Now let us calculate the power of $2$ contained in $2n!$ $$\text{Power of }2 \text{ in } 2!=\frac{2n}{2}+\frac{2n}{2^2}+\frac{2n}{2^3}+\frac{2n}{2^4}\ldots\\=2n\left(\frac{1}{2}+\frac{1}{2^2}+\frac{1}{2^3}+\ldots\right)\\=2n\left(\frac{\frac{1}{2}}{1-\frac12}\right)\\=2n$$ which means $$2n!=2^{2n}\times a$$

Similarly power of $2$ contained in $n!$ $$\text{Power of }2 \text{ in } 2!=\frac{n}{2}+\frac{n}{2^2}+\frac{n}{2^3}+\frac{n}{2^4}\ldots\\=n\left(\frac{1}{2}+\frac{1}{2^2}+\frac{1}{2^3}+\ldots\right)\\=n\left(\frac{\frac{1}{2}}{1-\frac12}\right)\\=n$$ which means $n!=2^{n}\times b\tag{Note that$b|a$}$
$\therefore$ equation $(1)$ can be written as $$(n+1)(n+2)...(2n)=\frac{2^{2n}\times a}{2^{n}\times b}$$ $$(n+1)(n+2)...(2n)=\frac{2^{n}\times a}{b}$$