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

Question

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

Answer 1

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.

Added: I don’t see a nice combinatorial way to answer the question in the comments:

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

Answer 2

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.