Use induction to prove that $2^n$ divides $(2n)!$ for any $n\in\mathbb{Z}_{\geq0}.$ Use induction to prove that $2^n$ divides $(2n)!$ for any $n\in\mathbb{Z}_{\geq0}.$
How would you do the inductive step for this proof? I have the base case done. 
 A: The inductive step can be done as follows:
$$(2(n+1))!=(2n+2)!=(2n)!(2n+1)(2n+2)$$
and $\;(2n)!\;$ is divisible by $\;2^n\;$ by the inductive hypothesis, and $\;(2n+1)(2n+2)\;$ is clearly even.
A: Assume it is true for $n = k$. I.e., assume $\color{blue}{\bf 2^k\mid (2k)!}$.
Then, show that, using the assumption above, then it follows that $$2^{k+1} = \color{red}{\bf 2}\cdot \color{blue}{\bf 2^k}\mid (2(k + 1))! = (2k + 2)(2k+1)\cdot \color{blue}{\bf (2k)!} = \color{red}{\bf 2}(k+1)(2k+1)\cdot\color{blue}{\bf (2k)!}$$
A: *

*Inductive hypothesis: ${(2n)! \over 2^n} = a$ where $a$ is some natural number. We suppose this is true for each $n \in \Bbb Z^{\ge0}$. From this expression we get ${(2n)! = a}\cdot 2^n$

*Inductive step: we need to make sure, that assuming our hypothesis is true for $n$ it is true for $n+1$. Thus we get: $${(2(n+1))! \over 2^{n+1}} = {(2n+2)! \over 2 \cdot 2^n}={2n! \cdot (2n+1)(2n+2) \over 2 \cdot 2^n} = {a \cdot 2^n\cdot (2n+1)(2n+2) \over 2 \cdot 2^n} = {a \cdot (2n+1)(2n+2) \over 2} $$


We see that $2n+2$ is obviously divisible by 2 and the result of the division will be $$a \cdot (2n+1)(n+1)$$
which is a natural number.
