# Prove using combinatorial argument $\binom{n}{0}.\binom{n}{2}+ \binom{n}{1}.\binom{n}{3}+\cdots+ \binom{n}{n-2}.\binom{n}{n}$

How can I prove it using combinatorial argument

$$\binom n0\binom n2 + \binom n1\binom n3 + \cdots + \binom{n}{n-2}\binom nn = \binom {2n}{n-2}$$

Sorry friends I have edited it

-

Recall that $\binom{n}k=\binom{n}{n-k}$, so your identity can be written

$$\binom{n}0\binom{n}{n-2}+\binom{n}1\binom{n}{n-3}+\ldots+\binom{n}{n-2}\binom{n}0=\binom{2n}{n-2}\;.\tag{1}$$

Imagine that you have $n$ couples, each consisting of a man and wife, and you want to choose $n-2$ of these $2n$ people. Let $k$ be the number of women you choose; $k$ can be anywhere from $0$ through $n-2$, and you must then choose $n-2-k$ men. There are $\binom{n}k$ ways to choose these $k$ women, and there are $\binom{n}{n-2-k}$ ways to choose the $n-2-k$ men, so there are $$\binom{n}k\binom{n}{n-2-k}$$ ways to choose a group of $n-2$ people containing exactly $k$ women.

The lefthand side of $(1)$ simply sums these numbers over all possible values of $k$; the righthand side counts the number of groups of $n-2$ people directly.

Evaluate $$\sum_{k=0}^{20}(-1)^k\binom{30}k\binom{30}{k+10}\;.\tag{2}$$

However, I can do it with generating functions. First note that $(2)$ is equal to $$\sum_{k=0}^{20}(-1)^k\binom{30}k\binom{30}{20-k}\;,$$ so the problem is an instance of evaluating $$\sum_{k=0}^m(-1)^k\binom{n}k\binom{n}{m-k}\;.$$ From the binomial theorem we have $$(1-x)^n=\sum_{k=0}^n(-1)^k\binom{n}kx^k\quad\text{and}\quad(1+x)^n=\sum_{k=0}^n\binom{n}kx^k\;,$$ so $$\left(1-x^2\right)^n=(1-x)^n(1+x)^n=\left(\sum_{k=0}^n(-1)^k\binom{n}kx^k\right)\left(\sum_{k=0}^n\binom{n}kx^k\right)\;,\tag{3}$$ a polynomial of degree $2n$. Let $c_m$ be the coefficient of $x^m$ in $(3)$. Since $$\left(1-x^2\right)^n=\sum_{k=0}^n(-1)^k\binom{n}kx^{2k}\;,$$ it’s clear that

$$c_m=\begin{cases}0,&\text{if }m\text{ is odd}\\\\\binom{n}{m/2},&\text{if }m\text{ is even}\;.\end{cases}$$

On the other hand, multiplying out the product of polynomials on the righthand side of $(3)$ shows that $$c_m=\sum_{k=0}^m(-1)^k\binom{n}k\binom{n}{m-k}\;,$$ so

$$\sum_{k=0}^m(-1)^k\binom{n}k\binom{n}{m-k}=\begin{cases}0,&\text{if }m\text{ is odd}\\\\\binom{n}{m/2},&\text{if }m\text{ is even}\;.\end{cases}$$

In your problem $n=30$ and $m=20$, so $(2)$ reduces to $\dbinom{30}{10}$.

-
Thanks Brain M. Scoot for Nice explanation. I have one Question based on same concept. The sum of $\displaystyle \bf{\binom{30}{0}.\binom{30}{10}-\binom{30}{1}.\binom{30}{11}+..................‌​......+\binom{30}{20}.\binom{30}{30}=}$ would to like to explain it to me here i have confused because of alternate positive and negative sigm. thanks – juantheron Feb 7 '13 at 5:28
@juantheron: Have you been given a righthand side, or are you supposed to figure one out? – Brian M. Scott Feb 7 '13 at 5:36
actually it is a objective Type Question whose $4$ options is Given below (a) $\displaystyle \binom{30}{11}$ (b) $\displaystyle \binom{30}{10}$ (c) $\displaystyle \binom{60}{10}$ (d) $\displaystyle \binom{65}{55}$ – juantheron Feb 7 '13 at 5:43
@juantheron: It took me a while to find the solution, but I’ve added it to my answer. – Brian M. Scott Feb 7 '13 at 7:20
Thanks Brian M. Scott – juantheron Feb 9 '13 at 7:07

I assume your sum is $$\dbinom{n}0\dbinom{n}2 + \dbinom{n}1 \dbinom{n}3 + \cdots + \dbinom{n}{n-2}\dbinom{n}n$$ Consider a bag with $n$ red balls and $n$ blue balls. Now count the number of ways to reject $n-2$ balls from these two bags. The total number of ways to do is $$\dbinom{2n}{n-2}$$

Another way to count this, is to first note that rejecting $n-2$ balls is same as selecting $n+2$ balls. To do this, we can select $k+2$ red balls from $n$ red balls, then we need to select $n-k$ blue balls from $n$ blue balls (equivalently we need to reject $k$ blue balls from $n$ blue balls). Hence, number of ways to do this is $\dbinom{n}{k+2} \dbinom{n}k$. To take all possible cases into account, we need to run $k$ from $0$ to $n-2$. Hence, we get the total number of ways is $$\sum_{k=0}^{n-2} \dbinom{n}k \dbinom{n}{k+2}$$

You can find a similar/same argument, I wrote earlier today here.

-
Is "reject" some kind of combinatoric term? I'd rather say "to choose", but I really am not sure. – DonAntonio Feb 7 '13 at 5:06
@DonAntonio I use the word "reject" to denote the opposite of "select", since I want to say that number of ways of selecting $k$ objects is same as number of ways of rejecting $n-k$ objects to conclude $\dbinom{n}k = \dbinom{n}{n-k}$. – user17762 Feb 7 '13 at 5:08
Thanks Marvis for Nice explanation. – juantheron Feb 7 '13 at 5:27