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.

Possible Duplicate:
prove that $(2n)!/(n!)^2$ is even if $n$ is a positive integer

Show that $\binom{2n}{ n}$ is divisible by 2?

Any help would be appreciated..

share|improve this question

marked as duplicate by Gerry Myerson, Aryabhata, Quixotic, Asaf Karagila, Chris Eagle Feb 28 '12 at 14:27

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

    
The answers here might help: math.stackexchange.com/questions/78533/… –  yunone Feb 28 '12 at 6:24
2  
$\binom{m+1}{k+1}=\frac{m+1}{k+1}\binom{m}{k}$. –  Andres Caicedo Feb 28 '12 at 6:28
    
See the following quesiton: math.stackexchange.com/questions/78533/… –  Chris Dugale Feb 28 '12 at 6:35

4 Answers 4

The number $\binom{2n}{n}$ counts the number of ways to choose a set of $n$ people from a set of $2n$ people.

For every set $S$ of $n$ people, there is a corresponding other set of $n$ people, the complement $S'$ of $S$. Note that the complement of the complement of $S$ is $S$, So the subsets of size $n$ can be divided into complementary pairs, and therefore the number of sets of size $n$ is even.

If this is too abstract, let our initial set be $\{1,2,3,4,5,6\}$. Thus $n=3$. The set $\{1,2,3\}$ is paired with its complement, which is the set $\{4,5,6\}$. The set $\{2,3,5\}$ is paired with its complementary set $\{1,4,6\}$, and so on. This pairing divides the sets of size $3$ into "couples." Thus the number of subsets is twice the number of couples, and in particular is even.

Remark: This sort of pairing argument can be used to prove, for example, that if the positive integer $n$ is not a perfect square, then the number of (positive) divisors of $n$ is even. We illustrate the idea with $n=24$. Pair two divisors $a$ and $b$ of $n$ if $ab=n$. So $1$ is paired with $24$, $2$ is paired with $12$, $3$ is paired with $8$, $4$ is paired with $6$. Now the divisors of $24$ have been divided into couples, so $24$ has an even number of divisors. The same idea works for any non-square $n$.

The method breaks down when $n$ is a perfect square, like $36$. For then there is nobody to pair poor $6$ with. The other divisors are happily (?) off in couples, so the total number of divisors of $36$ is odd. The same idea can be used to show that the total number of divisors of any perfect square is odd.

share|improve this answer
    
@Henry: Thanks! It is when I am typing too fast. –  André Nicolas Feb 28 '12 at 14:25

An algebraic approach:

$$ { 2n \choose n } = \frac{(2n)!}{n! \cdot n!} $$

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

$$ = \frac{ [1 \cdot 3 \cdot 5 \cdots (2n-1)] \cdot [2 \cdot 4 \cdot 6 \cdots (2n)]}{n! \cdot n!} $$

$$ = \frac{ [1 \cdot 3 \cdot 5 \cdots (2n-1)] \cdot [(2.1) \cdot (2.2) \cdot (2.3) \cdots (2.n)]}{n! \cdot n!} $$

$$= \frac{ [1 \cdot 3 \cdot 5 \cdots (2n-1)] \cdot [ 2^n \cdot (n)! ]}{n! \cdot n!} $$

$$ = 2^n \frac{ 1 \cdot 3 \cdot 5 \cdots (2n-1)}{n!} $$

share|improve this answer
    
It does follow from this, but you need a bit extra care to see that not all of those twos will get cancelled by the factorial in the denominator. –  Jyrki Lahtonen Feb 28 '12 at 7:12
1  
This is not a proof, and in fact it is difficult to understand how you think these algebraic manipulations solve the question... Is this because the last ratio would be an integer? But it is not. Or because $2^n$ would divide the LHS? It does not... –  Did Feb 28 '12 at 7:59

There are several ways to show this. I gave this as a homework exercise once (after having given the theory for computing a binomial coefficient modulo two in terms of the binary expansions), and a student surprised me with $$ {2n\choose n}={2n-1\choose n-1}+{2n-1\choose n}=2{2n-1\choose n-1}. $$ IOW he used Pascal's triangle rule once and then the symmetry ${n\choose k}={n\choose n-k}$.

share|improve this answer
2  
Nice! A more pedestrian variant is that the sum of the binomial coefficients is a power of $2$. But all but the middle one pair. –  André Nicolas Feb 28 '12 at 14:30

This answer has been moved to this question, of which this question has been judged to be a duplicate.

share|improve this answer

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