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


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

  • $\begingroup$ 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 $\endgroup$ – juantheron Feb 7 '13 at 5:28
  • $\begingroup$ @juantheron: Have you been given a righthand side, or are you supposed to figure one out? $\endgroup$ – Brian M. Scott Feb 7 '13 at 5:36
  • $\begingroup$ 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}$ $\endgroup$ – juantheron Feb 7 '13 at 5:43
  • $\begingroup$ @juantheron: It took me a while to find the solution, but I’ve added it to my answer. $\endgroup$ – Brian M. Scott Feb 7 '13 at 7:20
  • $\begingroup$ @juantheron: You’re welcome. $\endgroup$ – Brian M. Scott Feb 9 '13 at 12:48

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.

  • $\begingroup$ Is "reject" some kind of combinatoric term? I'd rather say "to choose", but I really am not sure. $\endgroup$ – DonAntonio Feb 7 '13 at 5:06
  • 2
    $\begingroup$ @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}$. $\endgroup$ – user17762 Feb 7 '13 at 5:08
  • $\begingroup$ Thanks Marvis for Nice explanation. $\endgroup$ – juantheron Feb 7 '13 at 5:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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