Prove that $\frac{(2n)!}{2^n} $ is an integer for all $n \geq 0$

Question

I don't really know where to begin with this problem. Should I use induction to solve it or is there an easier way?

Answer 1

$$(2n)! = (2n) * (2n - 1) * (2n - 2) * ... * 1$$

There are $n$ factors in this product that are even. $2$ divides each even number at least once, so $2$ is a factor in the product at least $n$ times. Thus, $2^n$ divides the product and $\frac{(2n)!}{2^n}$ is an integer.

Answer 2

Is it for $n=0$? Yes, because $0!=1$ and $2^0=1$.

Suppose it is for $n\ge0$; then $$ \frac{(2(n+1))!}{2^{n+1}}=\frac{(2n)!}{2^n}\frac{(2n+2)(2n+1)}{2} $$ and…

Answer 3

$$\frac{2n!}{2^n}=\frac{2n\cdot(2n-1)\cdot(2n-2)\cdot(2n-3)\cdot(2n-4)\cdots 2\cdot1}{2^n}\\ =n\cdot(2n-1)\cdot(n-1)\cdot(2n-3)\cdot(n-2)\cdots 1\cdot1$$

Answer 4

Consider the number of ways to arrange the numbers $1,1,2,2,\ldots,n,n$ in a line. Standard combinatorics tells you that it is $\frac{(2n)!}{2^n}$, hence that expression is an integer.

More details for why the number of ways is the desired expression: There are $(2n)!$ ways of arranging the list. Since for every $k$ we can switch the two copies of $k$ and be left with the same list, we have overcounted, so we should divide by $2$ for every $k$ to get the correct count. This gives the $2^n$ in the denominator.