# Show that $\binom{2n}{ n}$ is divisible by 2? [duplicate]

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

-

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

The answers here might help: math.stackexchange.com/questions/78533/… –  yunone Feb 28 '12 at 6:24
$\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

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

-
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

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.

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

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

-

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

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