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

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$$

marked as duplicate by Batominovski, Rebecca J. Stones, vociferous_rutabaga, Yagna Patel, ml0105Aug 19 '15 at 3:07

• Where's your problem exactly? $$\frac{(2n + 2)!}{(n+1)! 2^{n+1}} = \frac{2(n+1) \times (2n + 1) \times (2n)!}{(n+1)\times n! \times 2 \times 2^n} = (2n+1) \times \frac{(2n)!}{n! \times 2^n}$$ – user230734 Aug 18 '15 at 19:38

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$.

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.

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.

• The purpose of \displaystyle is to have mathematical notation set in the style used in "displayed" as opposed to "inline" notation. If it's already in a displayed setting rather than an inline setting, then its use has no effect and I fear it will confuse people who see it there and think it's there for a reason. So in the course of editing for proper use of \cdots I deleted all instances of \displaystyle. ${}\qquad{}$ – Michael Hardy Aug 18 '15 at 20:08

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$.