Prove by induction: for $n \ge 0$, $\frac{(2n)!}{n!2^n}$ is an integer

Question

Another prove by induction question: for $n \ge 0$, $$\frac{(2n)!}{n!2^n}$$ is an integer

Base step: $$n = 0$$ $$\frac{(2 \times 0)!}{0! \times 2^0} = \frac{0!}{1 \times 1} = 1$$

Induction step: please help

Answer 1

Assume for $k$, the result $\dfrac{(2k)!}{k!2^k}$ is equal to integer $c$.

For step $k+1$, we have $$\frac{(2(k+1))!}{(k+1)!2^{k+1}}=\frac{(2k)!}{k!2^k}\times\frac{(2k+1)(2k+2)}{2(k+1)}=c\times(2k+1)$$ Now, $c$ was assumed to be an integer, and $k$ is an integer as well, so $c\times(2k+1)$ will be an integer too.

Answer 2

Proof:: (Without Using induction::) Let $$Z=\frac{(2n)!}{n!\cdot 2^n} = \frac{(2n)\cdot (2n-1)\cdot (2n-2)\cdots4\cdot 3 \cdot 2 \cdot 1}{n!\cdot 2^n}$$

so $$Z = \frac{\underbrace{(2n)\cdot (2n-2)\cdot (2n-4)\cdots4\cdot 2}\times \underbrace{(2n-1)\cdot (2n-3)\cdot (2n-5)\cdots3\cdot 1}}{n!\cdot 2^n}$$

So $$Z = \frac{2^n\cdot \left[n\cdot (n-1)\cdot (n-2)\cdots 4\cdot 2\right]\times \underbrace{(2n-1)\cdot (2n-3)\cdot (2n-5)\cdots3\cdot 1}}{n!\cdot 2^n}$$

So $$Z = \frac{2^n\cdot n!\times \underbrace{(2n-1)\cdot (2n-3)\cdot (2n-5)\cdots3\cdot 1}}{2^n\cdot n!}$$

So $$Z = \underbrace{(2n-1)\cdot (2n-3)\cdot (2n-5)\cdots3\cdot 1}$$ is an Integer.

Answer 3

Assume it is true for $n=k$, so $$\frac{(2k)!}{2^{k}k!}$$ is an integer.

For $n=k+1$, the expression is $$\frac{(2k+2)!}{2^{k+1}(k+1)!}$$

This is the same as $$\frac{(2k)!(2k+1)(2k+2)}{2^{k+1}k!(k+1)}$$

But $2k+2=2(k+1)$, so we can cancel terms, yielding $$\frac{(2k)!(2k+1)}{2^{k}k!}$$

And since $$\frac{(2k)!}{2^{k}k!}$$ and $2k+1$ are integers, so is their product.

Therefore if it is true for $n=k$ it is also true for $n=k+1$.

Answer 4

Assume $\frac{(2n)!}{n!2^n}$ is an integer. $\frac{2(n+1)!}{(n+1)!2^{n+1}}=\frac{(2n+2)\cdot(2n+1)\cdot(2n)!}{(n+1)\cdot n!\cdot 2^n\cdot 2}=\frac{(2n)!}{n!2^n}\cdot \frac{(2n+2)(2n+1)}{2(n+1)}$. Notice that $\frac{(2n)!}{n!2^n}$ is an integer by the inductive assumption, and that $\frac{(2n+2)(2n+1)}{2(n+1)}=\frac{2(n+1)(2n+1)}{2(n+1)}=2n+1$.