Prove $\frac{(2n)!}{2^nn!}$ is always an integer by induction.

Question

Hey guys so I have this math question. I have to prove that $\frac{(2n)!}{2^nn!}$ is always an integer by induction where $n$ is a positive integer. This is my approach. First I check the initial case when $n=1$. It satisfies. I then assume $\frac{(2k)!}{2^kk!}$ is true (it is an integer) for some positive integer k. Now I try to prove that $\frac{(2(k+1))!}{2^{k+1}(k+1)!}$ is also true. I simplify it down to $\frac{(2k)!(k+1)(k+2)}{2\cdot2^kk!\cdot(k+1)}$. This simplifies to $\frac{(2k)!(k+2)}{2\cdot2^kk!}$. I can now replace it with the assumption. Therefore all I have left is $\frac{(k+2)}{2}\cdot $ (integer). Is this the correct approach? I'm not sure how I can conclude from here. Thanks.

Answer 1

$$\frac{(2(k+1))!}{2^{k+1}(k+1)!} =\frac{(2k)!(2k+1)(2k+2)}{2^k(k)!(2(k+1))}$$

So we need to show that $\frac{(2k+1)(2k+2)}{2(k+1)}$ is an integer

Answer 2

The approach by induction is correct but there seems to be an error in the simplification at the $(k+1)$ th stage -

You will have $\frac{(2k+2)!}{2^{k+1}(k+1)!} = \frac{2(k+1)(2k+1)(2k)!}{2^{k+1}(k+1)!} = \frac{(2k+1)(2k)!}{2^kk!}$ which is an integer after applying the assumption at $k$ th stage.

Answer 3

Hmmmn...

$\frac{(k+2)}{2}$ is not necessarily an integer. (e.g., $k=1$)

As you said, you want to show that if $\frac{(2k)!}{2^kk!}$ is an integer, then so is $\frac{(2(k+1))!}{2^{k+1}(k+1)!}$

Try:

$$\frac{(2k)!}{2^kk!}\times\frac{2(k+1)}{2(k+1)}= \frac{[2(k+1)]!}{2^{k+1}(k+1)!}$$

If $\frac{(2k)!}{2^kk!}$ is an integer, then the result of multiplying it by unity, $\frac{2(k+1)}{2(k+1)}$, is also an integer.

This cinches your inductive step:

$$\frac{(2k)!}{2^kk!}\in\mathbb Z \implies \frac{[2(k+1)]!}{2^{k+1}(k+1)!}\in\mathbb Z$$