Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Prove that $(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: $$ (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.

share|improve this question
    
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. –  Chris Taylor Nov 3 '11 at 9:40
    
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. –  hdtv1104 Nov 3 '11 at 9:50
    
Did you try using induction? It seems like that shouldn't be too difficult... –  Braindead Nov 3 '11 at 13:59

6 Answers 6

We have $$\displaystyle \frac{(2n)!}{(n!)^2} = \binom{2n}{n} $$ and of course for every way to choose a combination of $n$ objects from a total of $2n$ objects, there exists a complementary choice (the left over $n$ objects). Since the ways to pick $n$ objects from $2n$ comes in pairs, it follows that the total number is even.

Another proof: $$ \frac{(2n)!}{(n!)^2} = \frac{ 2n \cdot (2n-1)! }{(n!)^2 } = 2 \cdot \frac{ n \cdot (2n-1)! }{ n\cdot (n-1)! \cdot n!} = 2 \cdot \frac{(2n-1)!}{n! (n-1)!} = 2 \binom{2n-1}{n} $$

This one can be written in another flavor (using $ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ and the symmetric property): $$ \frac{(2n)!}{(n!)^2} = \binom{2n}{n} = \binom{2n-1}{n-1} + \binom{2n-1}{n} = 2\binom{2n-1}{n}.$$ Yet another: The sum of the $2n$-th row of Pascal's triangle is $2^{2n}$ which is even, and the sum of all the entries excluding the central coefficient is also even, because of the symmetric property $ \displaystyle \binom{n}{k} = \binom{n}{n-k} $. Thus, the central coefficient must also be even.


We can squeeze this problem a bit further and learn something interesting with this fourth proof. This one does not require any knowledge of binomial coefficients. To investigate the prime factors of factorials we use the following identity: $$ l = \sum_{k=1}^{\infty} \bigg\lfloor \frac{n}{p^k} \bigg\rfloor $$

where $p$ is a prime number and $l$ is the unique natural number such that $p^l \mid n!$ but $p^{l+1} \nmid n!.$ Basically this counts the multiplicity of the prime factor $p$ in $n!$.

The idea of the proof is this: Write $n! = 1\cdot 2 \cdot 3 \cdots (n-1) \cdot n$, and ask yourself where the factors of $p$ come from. Clearly you get one factor of $p$ from $p, 2p, 3p, \cdots $ so there are $ \lfloor n/p \rfloor $ factors of $p$ from these. But that's not the whole story - when we checked over the multiples $p,2p,3p\cdots $ we didn't count the second factor of $p$ every time there was $p^2, 2p^2, 3p^2 \cdots $ so there comes another $ \lfloor n/p^2 \rfloor $ to add. Wait, we didn't count another factor every time we missed cubes in $p^3, 2p^3,\cdots$, so we add another $ \lfloor n/p^3 \rfloor $ and so on. Also, note that this may look like an infinite series, but eventually $ p^k > n$ so all the terms eventually become $0. $

Anyway, back to the main goal. Using our identity, we see that there are $$ \sum_{k=1}^{\infty} \bigg \lfloor \frac{2n}{2^k} \bigg \rfloor - 2 \bigg \lfloor \frac{n}{2^k} \bigg \rfloor$$ factors of $2$ in $ \displaystyle \frac{(2n)!}{ (n!)^2} $, and we wish to show that this number is at least $1.$

With some easy casework we can see that $$ \lfloor 2x \rfloor - 2 \lfloor x \rfloor = \left\{ \begin{array}{lr} 1 & : \{ x\} \geq \frac{1}{2} \\ 0 & : \{ x\} < \frac{1}{2} \end{array} \right. $$ where $\{ x \} $ denotes the fractional part of $x.$ Thus our problem is reduced to showing that there exists some $ k\in \mathbb{N} $ such that $ \displaystyle \frac{n}{2^k} $ has fractional part greater than or equal to $1/2.$ This is of course true, since if $m$ is the largest positive integer such that $\displaystyle \frac{n}{2^m} \geq 1 $ then $ \displaystyle \frac{1}{2} \leq \frac{n}{2^{m+1} } < 1.$ Hence, $ \displaystyle \frac{(2n)!}{(n!)^2} $ is even.

share|improve this answer
    
Thanks for the combinatorics response to this proof. I see that it is easier to invoke the combinatorial interpretation but I myself could not see this interpretation as readily. What inspired the use of binomial? –  hdtv1104 Nov 3 '11 at 9:53
2  
Just a bit of practice I guess. Every time I see a ratio of factorials, I check whether it fits the form $ \frac{n!}{k! (n-k)!} = \binom{n}{k}.$ Also, it was particularly easy for me here because this particular coefficient, $\binom{2n}{n} $, is quite special and comes up relatively often. –  Ragib Zaman Nov 3 '11 at 9:55
    
Thanks a lot Ragib. –  hdtv1104 Nov 3 '11 at 9:58
    
You're welcome! –  Ragib Zaman Nov 3 '11 at 10:00
3  
In fact, the number of factors of $2$ in $\binom{2n}{n}$ is equal to the number of $1$ bits in the binary representation of $n$. –  robjohn Nov 14 '11 at 21:24

It is often fun to try to solve such problems using Lagrange's Theorem from finite group theory. That is, to prove that $a$ divides $b$ you try to find a group of cardinality $b$ with a subgroup of cardinality $a$.

In this case, the symmetric group on $2n$ letters, $S_{2n}$, is an obvious choice for a group of cardinality $(2n)!$. Let $G\subset S_{2n}$ be the set of all permutations which map the set $\{1,\ldots, n\}$ onto $\{1,\ldots, n\}$ or $\{n+1,\ldots, 2n\}$. You can check that $G$ is a subgroup of $S_{2n}$.

To compute the cardinality $\lvert G \rvert$, one option is to observe that $G\cong S_n\wr \mathbb{Z}_2$, so $\lvert G\rvert = \lvert S_n\rvert^{\lvert \mathbb{Z}_2\rvert} \lvert \mathbb{Z}_2\rvert = 2(n!)^2$. Alternatively, choosing an element of $G$ corresponds to choosing two permutations of a set of size $n$ and a choice of whether to swap $\{1,\ldots,n\}$ with $\{n+1,\ldots, 2n\}$ or not, so $\lvert G\rvert = 2(n!)^2$.

Thus by Lagrange's Theorem $2(n!)^2$ divides $(2n)!$, or in other words, $\frac{(2n)!}{(n!)^2}$ is even.

share|improve this answer

By the binomial theorem, $$ 4^n=(1+1)^{2n}=\sum\limits_{k=0}^{2n}{2n\choose k}={2n\choose n}+\sum\limits_{k=0}^{n-1}{2n\choose k}+\sum\limits_{k=n+1}^{2n}{2n\choose k}. $$ Since Pascal's triangle is symmetrical, each term in the sum from $k=0$ to $n-1$ coincides with one term in the sum from $k=n+1$ to $2n$, hence these two sums are equal and $$ \frac{(2n)!}{(n!)^2}={2n\choose n}=4^n-2\cdot\sum\limits_{k=0}^{n-1}{2n\choose k} $$ is even for every $n\geqslant1$.

share|improve this answer
    
I had this one in my answer =) But not as fleshed out. –  Ragib Zaman Nov 14 '11 at 21:02
    
Oh yes, I missed it but I see it now. Sorry about that. –  Did Nov 14 '11 at 21:08

Let's observe an example:

$(2\cdot 5)!=10\cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5!$ , we may conclude that:

$(2n)!=2n\cdot(2n-1)\cdot(2n-2)....(n+1)n!$ so we get following expression :

$$\frac{2n\cdot(2n-1)\cdot(2n-2)....(n+1)}{n!}=\frac{2n\cdot(2n-1)\cdot2\cdot(n-1)\cdot(2n-3)\cdot 2 \cdot (n-2)....(n+1)}{n!}$$

$$=\frac{2\cdot2\cdot2...\cdot2\cdot n\cdot(n-1)\cdot(n-2)\cdot......\cdot 1\cdot(2n-1)\cdot(2n-3)\cdot......(n+1)}{n!}$$

$$=\frac{2\cdot2\cdot2...\cdot2 \cdot n!\cdot(2n-1)\cdot(2n-3)\cdot......\cdot (n+1)}{n!}=$$

$$=2\cdot2\cdot2...\cdot2 \cdot(2n-1)\cdot(2n-3)\cdot......\cdot (n+1)$$ so number is even.

share|improve this answer
1  
But I'm sorry, this proof is false (still got 11 upvotes). –  user144248 May 15 at 21:32
1  
The error here is at the third equality: The terms that have been divided by $2$ don't go all the way down to $1$, since there are only (about) $n/2$ such terms. In fact, for $n$ even, the last term that is of this form is $n + 2$, so the correct expression would be $$= \frac{2 \cdots 2 \cdot n \cdot (n - 1) \cdot ... \cdot \frac{n + 2}{2} \cdot (2n - 1) \cdots (n + 1)}{n!}$$ –  user61527 May 16 at 4:49

This answer has been moved from this question, which was closed because it was judged to be a duplicate of this question.

The number of factors of a prime $p$ in $n!$ is $$ \nu_p(n)=\left\lfloor\frac{n}{p}\right\rfloor+\left\lfloor\frac{n}{p^2}\right\rfloor+\left\lfloor\frac{n}{p^3}\right\rfloor+\dots\tag{1} $$ $\left\lfloor\frac{n}{p}\right\rfloor$ counts the number of positive multiples of $p$ no greater than $n$, but only once. $\left\lfloor\frac{n}{p^2}\right\rfloor$ counts the multiples of $p^2$ a second time, and $\left\lfloor\frac{n}{p^3}\right\rfloor$ the positive multiples of $p^3$ a third time, etc. Applying $(1)$ to the base-$p$ representation of $n$ $$ n=\sum_{i=0}^kn_ip^i\tag{2} $$ where $0\le n_i<p$, yields $$ \begin{align} \nu_p(n) &=\sum_{i=0}^kn_i\left(1+p+p^2+\dots+p^{i-1}\right)\\ &=\sum_{i=0}^kn_i\left(\frac{p^i-1}{p-1}\right)\\ &=\frac{1}{p-1}\left(n-\sum_{i=0}^kn_i\right)\\ &=\frac{n-\sigma_p(n)}{p-1}\tag{3} \end{align} $$ where $\sigma_p(n)$ is the sum of the base-$p$ digits of $n$.

Therefore, the number of factors $p$ in $\displaystyle\binom{n}{k}=\frac{n!}{k!(n-k)!}$ is $$ \begin{align} &\nu_p(n)-\nu_p(k)-\nu_p(n-k)\\ &=\frac{1}{p-1}\left(n-\sigma_p(n)-k+\sigma_p(k)-(n-k)+\sigma(n-k)\right)\\ &=\frac{\sigma_p(k)+\sigma_p(n-k)-\sigma_p(n)}{p-1}\tag{4} \end{align} $$ Using $(4)$ with $p=2$ says that the number of factors of $2$ in $\displaystyle\binom{2n}{n}$ is $\sigma_2(n)+\sigma_2(n)-\sigma_2(2n)$ which is simply $\sigma_2(n)$ since $\sigma_2(n)=\sigma_2(2n)$. Therefore, the number of factors of $2$ in $\displaystyle\binom{2n}{n}$ is the number of $1$-bits in the binary representation of $n$.

Thus, if $n>0$, then there is at least one $1$-bit in $n$ in binary, and so $2$ divides $\displaystyle\binom{2n}{n}$.

share|improve this answer

The exact power of $2$ dividing $\binom{2n}{n}$ is $2$^(sum of digits in base $2$ representation of $n$).

The exact power of $3$ dividing the trinomial coefficient $\binom{3n}{n,n,n} = (3n)!/(n!)^3$ is $3$^(sum of digits in base $3$ representation of $n$).

The exact power of $p$ dividing the $p$-nomial coefficient $\binom{pn}{n,n,\dots , n} = (pn)!/(n!)^p$ is $p$^(sum of digits in base $p$ representation of $n$) for any prime $p$.

This is from the formula for the power of $p$ dividing $n!$, which is ($n$ - sum of digits of $n$ when written in base $p$)/($p-1$). There also are combinatorial and generating function proofs but they are more complicated.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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