2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ What if $k=5$, say? $\endgroup$ – Pedro Tamaroff Sep 23 '15 at 4:16
  • 1
    $\begingroup$ @PedroTamaroff Then $\frac{(k+2)}{2}$ will not be an integer. $\endgroup$ – KFC Sep 23 '15 at 4:22
  • $\begingroup$ This is known as $(2n-1)!!$ See Double Factorial. $\endgroup$ – robjohn Sep 23 '15 at 5:39
  • $\begingroup$ I love inductive proofs. It's like watching dominoes toppling over. $\endgroup$ – Adam Hrankowski Sep 23 '15 at 20:06
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.