4
$\begingroup$

I believe the following is an identity (I've tested with a few random $m$ and $n$ values, could be wrong though):

$$\sum_{k= 0}^{\infty}{m \choose k}{n \choose k}k=n\binom{m+n-1}{m-1}$$ but I'm not sure how to prove it.

Initially I thought of considering the right side combinatorially: pick $m-1$ things from a bucket of $m+n-1$ things and repeat this $n$ times. But how do I think of the left side combinatorially, since there is an infinite sum? Or maybe this is the incorrect approach?

$\endgroup$
  • 1
    $\begingroup$ Start by noting that $\binom{n}{k}k=n\binom{n-1}{k-1}$. $\endgroup$ – Thomas Andrews Feb 22 '16 at 0:22
  • $\begingroup$ According to Wolfram Alpha, you're right. (Note that $\Gamma(x)=(x-1)!$ for $x \in \Bbb{N}$.) $\endgroup$ – Noble Mushtak Feb 22 '16 at 0:24
  • $\begingroup$ @NobleMushtak Perhaps this question is out of place: but according to your network profile you are $13$ years old. Is this true? $\endgroup$ – S.C.B. Feb 22 '16 at 0:50
  • $\begingroup$ @MXYMXY ...Yes. Why? $\endgroup$ – Noble Mushtak Feb 22 '16 at 21:53
5
$\begingroup$

Hint

Note that $k\binom{n}{k}=n\binom{n-1}{k-1}$, and erase $n$ from both sides.

There is one box with $m$ balls, and the other with $n-1$ balls.

You are trying to pick $n$ balls in total.

Note that this is equal to $(RHS)$.

Note that $\binom{n-1}{k-1}=\binom{n-1}{n-k}$
Since you are trying to pick $n$ balls in total if you pick $k$ balls from the first box, you are going to have to pick $n-k$ from the second. This operation is equal to $(LHS)$.

$\endgroup$
  • $\begingroup$ Okay so we can show $\sum_{k=0}^{\infty}\binom{m}{k} \binom{n-1}{m-1}=\binom{m+n-1}{m-1}$. But I'm not sure where to go from here. How to handle infinite sum? $\endgroup$ – User Feb 22 '16 at 0:28
  • $\begingroup$ @User I am using that $\binom{m+n-1}{m-1}=\binom{m+n-1}{n}$. Also, note that if $\binom{n}{k}$ would become $0$ if $k > n$, so the infinite sum does not matter as much. $\endgroup$ – S.C.B. Feb 22 '16 at 0:32
  • $\begingroup$ I see it now. That trick to remove the infinite sum is what I was stuck on. $\endgroup$ – User Feb 22 '16 at 0:42
3
$\begingroup$

$$\begin{align} \sum_{k= 0}^{\infty}\color{green}{{m \choose k}}\color{blue}{{n \choose k}k} &=\color{blue}n\sum_{k=0}^\infty\color{green}{\binom m{m-k}}\color{blue}{\binom {n-1}{k-1}}\\ &=n\binom{m+n-1}{m-1}\qquad\blacksquare\end{align}$$ using the Vandermonde identity. Applicable limits for $k$ are $1\le k\le \min(m,n)$ as $\binom ab=0$ for $a<b$.

$\endgroup$
  • $\begingroup$ I was unaware of this identity. It looks very useful. Thank you. $\endgroup$ – User Feb 22 '16 at 0:52
  • $\begingroup$ It is indeed! You're welcome. $\endgroup$ – hypergeometric Feb 22 '16 at 0:53
1
$\begingroup$

Since you were originally aiming for a combinatorial proof, I thought I'd offer one: a committee consists of $m$ members from the minority party and $n$ members from the majority party. A subcommittee is to be formed having an equal, but unspecified, number of members from each party, and one of the subcommittee members from the majority party is to be designated chair of the subcommittee. Call the result a marked subcommittee.

The left side clearly enumerates the number of marked subcommittees. To see that the right side does too, observe that the majority-party and minority-party members of a marked subcommittee may be paired up as follows: line up the subcommittee members from the majority party with the chair first and everybody else in alphabetical order. Line up the subcommittee members from the minority party in alphabetical order. Now pair up the first people in each of the lineups, the second people in each of the lineups, and so on.

We can now interpret the right side of the identity: select a person from the majority party to be subcommittee chair. Now line up the $n$ majority-party members with the chair first and everybody else in alphabetical order. There $n$ possible lineups. Place $m-1$ separator marks in this lineup to partition the lineup into $m$ parts (some possibly empty). By stars-and-bars, there are $n\binom{n+m-1}{m-1}$ partitioned lineups. Line up the minority-party members in alphabetical order and pair up the first minority-party member with the first part of the majority-party lineup, the second minority-party member with the second part of the majority-party lineup, and so on. Then the subcommittee is formed by taking those minority-party members that have been paired with a non-empty part of the majority-party lineup, and by taking as majority-party members the lead member of each such non-empty part. Note that since the chair will be the lead member of her/his part, the chair will always be taken.

Example: To show how the correspondence works, let the majority party consist of $A$, $B$, $C$, $D$, $E$ and the minority party of $1$, $2$, $3$, $4$. Suppose the subcommittee consists of $B$, $D$, $2$, $3$, with $D$ as chair. Then the pairing between minority-party and majority-party subcommittee members is $(2,D)$, $(3,B)$. The corresponding partition of the majority-party lineup is $\lvert DA\lvert BCE\lvert$, the associated pairing is $(1,())$, $(2,(D,A))$, $(3,(B,C,E))$, $(4,())$.

Going the other way, suppose $B$ is chosen as chair and the partition of the majority-party lineup is $B\lvert\lvert ACD\lvert E$. The associated pairing is $(1,(B))$, $(2,())$, $(3,(A,C,D))$, $(4,(E))$, which produces the subcommittee consisting of $B$, $A$, $E$, $1$, $3$, $4$, with $B$ as chair.

$\endgroup$
  • $\begingroup$ An alternative explanation of how the right side counts marked subcommittees: from the $n$ majority party members choose a chair. Then choose $m-1$ of the remaining people (of both parties). Of the chosen people, any from the majority party are placed on the subcommittee; any from the minority party are LEFT OFF of the subcommittee. If $k-1$ of the chosen people are of the majority party, then, with chair included, the majority party will have $k$ members on the subcommittee. The minority party will have $m-1-(k-1)=m-k$ members NOT on the subcommittee, and hence $k$ members ON it. $\endgroup$ – Will Orrick Mar 3 '16 at 19:11

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.