34
$\begingroup$

Prove that $\frac{(2n)!}{(n!)^2}$ is even if $n$ is a positive integer.

For clarity: the denominator is the only part being squared.

My thought process:

The numerator is the product of the first $n$ even numbers and the product of the first $n$ odd numbers.

That is, $(2n!) = (2n)(2n-2)(2n-4)\cdots(2n-1)(2n-3)(2n-5).$ In effect, the product of even numbers can be cancelled out with $n!$ resulting in the following quotient: $$ \frac{(2^n)(2n-1)(2n-3)}{(n!)}\;.$$ To me this looks even thanks to the powers of $2$. But I am not convinced for some reason.

Was this approach to naive?

Sorry for the poor notation, I don't know any coding languages, my apologies.

  • 0
    Try counting the powers of 2 in the numerator and denominator. After a quick bit of experimentation, it looks like it's probably sufficient to consider $n=4m+k$ for $k=0,1,2,3$ (i.e. there are four cases) and you could demonstrate that there are always more powers of 2 in the numerator than in the denominator.2011-11-03
  • 0
    Could you give me more insight as to how you came up with the four cases for n? I don't see the derivation for n as you have shown.2011-11-03
  • 0
    Did you try using induction? It seems like that shouldn't be too difficult...2011-11-03

7 Answers 7