$2^n\mid(n+1)(n+2)\cdots(2n)$ for all $n\in\Bbb N$ 
How to prove that $(n+1)(n+2)\cdots(2n)$ is divisible by $2^n$, for each $n\in\Bbb N$?

I am quite confused how to start and end the proof using mathematical induction. I tried answering it but I'm not confident if it is right. Can anyone help me please?
This is my proof:
Base case When $n=1$, $(1+1)=2\implies1=1$. Since $2\in\Bbb N$ is divisible by $2^1$, then statement holds when $n=1$.
Induction Suppose the statement is true for some $n=k$.
$$2^k\mid(k+1)(k+2)\cdots(2k)$$
We are to show that it also holds for $n=k+1$. We have
$$2^{k+1} \mid [(k+1) + 1] [(k+1) + 2]\cdots[2(k+1)]\tag{target!}$$
$$2^{k+1}\mid (k+2)(k+3)\cdots(2k+2)$$
Now
$$(k+1) (k+2) \cdots (2k+2) = 2^k(2k+2) 
                                 = 2^k(2k) + 2^k(2)
                                 = 2^k(2k) + 2^k+1$$
and I don't know how to continue from here.
 A: Let $P_n=(n+1)\times(n+2)\times \dots \times(2n)$
base case: $2$ is divisible by $2^1$
Inductive step: $P_{n+1}=P_n\frac{(2n+1)\times(2n+2)}{n+1}$. Since $2^n\mid P_n$ we just have to show $\frac{(2n+1)\times(2n+2)}{n+1}$ is always even, which is clearly true, since $\frac{(2n+1)\times(2n+2)}{n+1}=(2n+1)\times 2$
A: We have a theorem:
Let $x$ be a prime. The power of $x$ that divides $n!$ is 
$$\left[\frac{n}{x}\right]+\left[\frac{n}{x^2}\right]+\cdots+\left[\frac{n}{x^k}\right]+\cdots$$
so the power of $2$ that divides $(n+1)\cdots(2n)$ is 
$$\left(\left[\frac{2n}{2}\right]+\left[\frac{2n}{4}\right]+\cdots\right) - \left(\left[\frac{n}{2}\right]+\left[\frac{n}{4}\right]+\cdots\right) = n$$
A: Just for fun, I want to give a combinatorial argument using group actions and orbit-stabilizer.
The group $L=(\mathbb{Z}/2\mathbb{Z})^n$ acts on $Y=\{1,\ldots,n\}\cup\{1',\ldots,n'\}$ where the $k$th coordinate vector acts as the transposition $(kk')$. Denote $X=\{1,\ldots,n\}$ and let $F$ be the set of all injective functions $X\to Y$. Then $L$'s action on $Y$  induces an action of $L$ on $F$ which is free, therefore every orbit has the same size, so $|L|$ divides $|F|$.

Here's my attempt to phrase the arguments without group actions.
Let $F$ be the set of all sequences $(a_1,\ldots,a_n)$ of $n$ distinct elements from $\{1,\ldots,n,1',\ldots,n'\}$ (which has a two copies of every number $1$ through $n$, just the extra copies have primes on them). We can set an equivalence relation on $F$, with $x\sim y$ whenever $x$ and $y$ are the same tuple after removing all primes. One may check that each equivalence class has $2^n$ elements, and there are $(2n)(2n-1)\cdots(n+1)$-many elements in $F$, from which the result follows.
A: Just to be different.  (Seriously induction as per Carry on Smiling's solution is the easiest way.)
$(n+1)......(2n)$ will have roughly $n/2$ even numbers.  So if we  factor $2$ out of each of the even terms then $2^{n/2}$ factors.  The expression will have roughly $n/4$ numbers divisible by $4$.  If we factor $2$ out of those terms we with get that $2^{n/2}*2^{n/4}$ factors.
We repeat to get $2^{n/2}*2^{n/4}*2^{n/8}*.... = 2^{n(1/2 + 1/4 + 1/8 + ....)} = 2^{n*1}$.
Roughly.
Okay... so the devil is in the details, right.
Let $n = \sum_{i = 0}^k b_i 2^i;b_i = \{0|1\}$ be the binary representation of $n$.
Then $2n = \sum_{i = 0}^k b_i 2^{i+1}$.
Between $1$ and $2n$ there are $ \sum_{i = 0}^k b_i 2^{i}$ even numbers.  Between $1$ and $n$ there are $\sum_{i=1}^k b_i 2^{i-1}$ even numbers.  So between $n + 1$ and $n$ there are $b_0 + \sum_{i=1}^k bi*(2^{i} - 2{i-1}) = b_0 + \sum_{i=1}^k bi*2^{i-1}$ even number.
Likewise between $n+1$ and $2n$ there will be $b_1 + \sum_{i=2}^k bi*2^{i-2}$ numbers divisible by $4$.
And between $n+1$ and $2n$ there will be $b_{m-1} + \sum_{i=m}^k bi*2^{i-m}$ numbers divisible by $2^m$.
So $2^{\sum_{m=1}^k (b_{m-1} + \sum_{i=m}^k bi*2^{i-m})}$ divides $(n+1)....2n$.
Remains to show $\sum_{m=1}^k (b_{m-1} + \sum_{i=m}^k bi*2^{i-m})= n$.
Well..... $\sum_{m=1}^k (b_{m-1} + \sum_{i=m}^k bi*2^{i-m})=$
$\sum_{m=1}^k (b_{m-1} + \lfloor n/2^m \rfloor)=$
$b_0 + (b_1 + \lfloor n/2 \rfloor) + (b_2 +  \lfloor n/4 \rfloor) + ....=$
$b_0 + (b_1 + b_1 + 2\lfloor n/4 \rfloor)+ (b_2 +  b_2 + 2\lfloor n/8 \rfloor) + ....=$
$b_0 + b_1*2+  2\lfloor n/4 \rfloor)+ (b_2*2 + 2\lfloor n/8 \rfloor) + ....=$
$b_0 + b_1*2+  2*b_2 + 4\lfloor n/8 \rfloor)+ (b_2*2 + 2*b_3 + 4\lfloor n/16 \rfloor) + ....=$
$b_0 + b_1*2+  b_2*2^2 + 2*b_3 + 4\lfloor n/8 \rfloor)+ ( 2*b_3 + 4\lfloor n/16 \rfloor) + ....=$
.....
$b_0 + b_1*2 + b_2*2^2 + b_3*2^3 + .... = n$.
Okay... I told you induction was easier.
But what I hope I have shown is an idea of why this works.  i.e. that by dividing $2$ out $n/2$ even numbers and then another $2$ out of $n/4$ numbers divisible by $4$ and so on we divide $2$ out roughly $n/2 + n/4 + .... = n$ times so $2^n$ is a factor.
A: $\newcommand{\angles}[1]{\left\langle\,{#1}\,\right\rangle}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\half}{{1 \over 2}}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\iff}{\Longleftrightarrow}
 \newcommand{\imp}{\Longrightarrow}
 \newcommand{\Li}[1]{\,\mathrm{Li}_{#1}}
 \newcommand{\mc}[1]{\mathcal{#1}}
 \newcommand{\mrm}[1]{\mathrm{#1}}
 \newcommand{\ol}[1]{\overline{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\ul}[1]{\underline{#1}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$
\begin{align}
&\color{#f00}{\pars{n + 1}\pars{n + 2}\ldots\pars{2n}} =
{\pars{2n}! \over n!} =
{\Gamma\pars{2n + 1} \over \Gamma\pars{n + 1}} =
2\,{\Gamma\pars{2n} \over \Gamma\pars{n}}\qquad\qquad\pars{~Recurrence~}
\\[5mm] = &\
2\,{1 \over \root{\pi}}\,2^{2n - 1}\,\,\Gamma\pars{n + \half}
\qquad\qquad\pars{~Duplication\ Formula~}
\end{align}

\begin{align}
&\color{#f00}{\pars{n + 1}\pars{n + 2}\ldots\pars{2n} \over 2^{n}} =
{1 \over \root{\pi}}\,2^{n}\,\Gamma\pars{n + \half}
\\[5mm] = &\
{2^{n} \over \root{\pi}}\,\pars{n - \half}\Gamma\pars{n - \half} =
{2^{n} \over \root{\pi}}\,\pars{n - \half}\pars{n - {3 \over 2}}
\Gamma\pars{n - {3 \over 2}}
\\[5mm] = &\ \cdots =
{2^{n} \over \Gamma\pars{1/2}}\,\pars{n - \half}\pars{n - {3 \over 2}}\ldots
\half\,\Gamma\pars{\half}\qquad\quad
\pars{~\mbox{Note that}\ \Gamma\pars{\half} = \root{\pi}~}
\\[5mm] = &\
{2^{n} \over \Gamma\pars{1/2}}\,\pars{n - \half}\pars{n - {3 \over 2}}\ldots
\half\,\Gamma\pars{\half}\\[5mm] = &\
2^{n}\
\overbrace{{2n - 1 \over 2}\,{2n - 3 \over 2}\ldots{2n - \pars{2n - 1} \over 2}}
^{\ds{n\ \mbox{terms}}}
\end{align}

$$
\color{#f00}{\pars{n + 1}\pars{n + 2}\ldots\pars{2n} \over 2^{n}} =
\color{#f00}{\pars{2n - 1}!!}\ \in\ \mathbb{N}
$$
