7
$\begingroup$

Consider the following identity

$${{n}\choose{0} }{m\choose n} + {n\choose 1}{{m+1} \choose n}+ \cdots +{n\choose n}{{m+n} \choose n} =\sum_{i=0}^{\min (m ,n)} {n\choose i}{m\choose i}2^i$$

The right hand side looks really neat to me but I can't find any combinatorial argument to this.I'm totally stuck on how to approach. I'd like hints and not full solutions.

EDIT I guess asking for a hint was a bit too much for this question. Apologies.

$\endgroup$
1
  • 1
    $\begingroup$ For the sake of future reference, I would like to mention that both sides are indeed equal to $$ [x^m y^n] \frac{1}{1-x-y-xy}, $$ where the bracket notation extracts the coefficient of $x^m y^n$ from the Taylor series. $\endgroup$ Apr 7, 2015 at 6:13

2 Answers 2

7
$\begingroup$

You have $n$ women in Room A and $m$ men in Room B. For some $k\in\{0,\ldots,n\}$ you pick $k$ of the women and move them into Room B; this can be done in $\binom{n}k$ ways. Then you pick $n$ of the people in Room B and move them to Room C; this can be done in $\binom{m+k}n$ ways, so there are altogether

$$\sum_k\binom{n}k\binom{m+k}n$$

ways to carry out this process. The result of the process is $n$ people in Room C, $n-k$ women in Room A for some $k$, and $m+k-n$ people in Room B. If there are $\ell$ men in Room C, then there are $m-\ell$ men in Room B.

We might instead begin by simply picking $\ell$ men from Room B and $n-\ell$ women from Room A and moving them to Room C; this leaves $\ell$ women in Room A, and we conclude by moving any subset of them into Room B$. This process can be carried out in

$$\sum_\ell\binom{n}{n-\ell}\binom{m}\ell2^\ell=\sum_\ell\binom{n}\ell\binom{m}\ell2^\ell$$

ways.

Clearly the two procedures have the same set of possible outcomes: $n$ of the people in Room C, all of the other men still in Room B, and possibly some of the other women in Room B instead of Room A. Thus,

$$\sum_k\binom{n}k\binom{m+k}n=\sum_k\binom{n}k\binom{m}k2^k\;.$$

$\endgroup$
1
$\begingroup$

Permit me to contribute a proof complex variables, for variety's sake, which is an instructive exercise.

Suppose we seek to verify that $$\sum_{q=0}^n {n\choose q} {m+q\choose n} = \sum_{q=0}^{\min(m,n)} {n\choose q}{m\choose q}2^q.$$ with $n,m$ a positive integers.

For the LHS introduce the integral representation $${m+q\choose n} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m+q}}{z^{n+1}} \; dz$$

which gives for the sum $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m}}{z^{n+1}} \sum_{q=0}^n {n\choose q} (1+z)^q\; dz$$

or alternatively $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m}}{z^{n+1}} (2+z)^n \; dz.$$

For the RHS start by observing that it is symmetric in $m$ and $n$ so we may assume that $m\ge n.$ Now introduce the integral representation

$${m\choose q} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m}}{z^{q+1}} \; dz$$

which gives for the sum $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m}}{z} \sum_{q=0}^n {n\choose q} 2^q \frac{1}{z^q} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m}}{z} \left(1+\frac{2}{z}\right)^n \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m}}{z} \frac{(z+2)^n}{z^n} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m}}{z^{n+1}} (2+z)^n \; dz.$$

We have equality of the LHS and the RHS which was to be shown.

Addendum. If we had not observed the symmetry here we would get for $n\ge m$ the integral $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n}}{z^{m+1}} (2+z)^m \; dz.$$

Put $z=2/w$ in this integral to get $$-\frac{1}{2\pi i} \int_{|w|=R} \frac{(1+2/w)^{n}}{(2/w)^{m+1}} (2+2/w)^m \times\left(-\frac{2}{w^2}\right) \; dw \\ = \frac{1}{2\pi i} \int_{|w|=R} \frac{(w+2)^n}{w^n} \frac{w^{m+1}}{2^{m+1}} \frac{(2w+2)^m}{w^m} \times\left(\frac{2}{w^2}\right) \; dw \\ = \frac{1}{2\pi i} \int_{|w|=R} \frac{(w+2)^n}{w^{n+1}} (w+1)^m \; dw $$

which is the form we sought.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .