3
$\begingroup$

I am trying to find a closed form for the following summation:

$$\sum_{i=0}^k \binom{n}{i}\binom{m}{k-i}$$

, expecting a binomial coefficient without any summation notation as the answer.

I have broken down this summation as follows:

$$\sum_{i=0}^k \binom{n}{i}\binom{m}{k-1} = \binom{n}{0}\binom{m}{k}+\binom{n}{1}\binom{m}{k-1}+\binom{n}{2}\binom{m}{k-2}+...+\binom{n}{k}\binom{m}{0}$$

However, I am stuck on how to solve this after breaking it up like that. Someone had suggested to me that I should define the following terms and then take the product of the two expressions: $$(x+1)^n=\binom{n}{0}+\binom{n}{1}x+...+\binom{n}{n}x^n$$ $$(x+1)^m=\binom{m}{0}x^m+\binom{m}{1}x^{m-1}+...+\binom{m}{m}x^0$$

I am confused on how the above two terms have been derived and I am also confused on how these two terms can be used to find the closed form.

Can someone provide assistance?

$\endgroup$
1
  • $\begingroup$ It’s $\binom{n+m}k$, by Vandermonde’s identity. There are quite a few proofs of the identity on this site, and there are three in the Wikipedia article. $\endgroup$ – Brian M. Scott Aug 30 '16 at 19:00
2
$\begingroup$

This identity is known as Vandermonde's identity.

In order to show the relationship with binomials $(1+x)^n$ it is convenient to introduce the coefficient of operator $[x^i]$ to denote the coefficient of $x^i$ in a series. This way we can write e.g. \begin{align*} [x^i](1+x)^n=\binom{n}{i} \end{align*}

We obtain \begin{align*} \sum_{i=0}^k\binom{n}{i}\binom{m}{k-i} &=\sum_{i=0}^\infty [x^i](1+x)^n[y^{k-i}](1+y)^m\tag{1}\\ &= [y^k](1+y)^m\sum_{i=0}^\infty y^i [x^i](1+x)^n\tag{2}\\ &=[y^k](1+y)^m(1+y)^n\tag{3}\\ &=[y^k](1+y)^{m+n}\tag{4}\\ &=\binom{m+n}{k} \end{align*} and the claim follows.

Comment:

  • In (1) we apply the coefficient of operator twice. We also extend the upper limit of the series to $\infty$ without changing anything since we are adding zeros only.

  • In (2) we use the linearity of the coefficient of operator and apply the rule $[x^{p-q}]A(x)=[x^p]x^qA(x)$.

  • In (3) we use the substitution rule of the coefficient of operator: \begin{align*} A(y)=\sum_{i=0}^\infty a_i y^i=\sum_{i=0}^\infty y^i [x^i]A(x) \end{align*}

  • In (4) we select the coefficient of $x^{m+n}$.

$\endgroup$
3
  • $\begingroup$ Can you provide a reference for this "coefficient of" operator you are speaking of? I've never heard of it, and I can't find a lot of good information about these rules you've used. $\endgroup$ – jshapy8 Aug 30 '16 at 23:39
  • $\begingroup$ @revolution9540: A landmark is Egorychev's classic. Easier accessible is this paper. It's funny to detect the efficiency of this method. A short time ago I saw a nice answer by MarkoRiedel regarding this question. I've thought about his nice representation of Iverson brackets and was astonished how efficient we can handle this situation with the coefficient of technique ... :-) $\endgroup$ – Markus Scheuer Aug 31 '16 at 8:42
  • $\begingroup$ @revolution9540: Here's another application which might be useful. $\endgroup$ – Markus Scheuer Aug 31 '16 at 8:46
1
$\begingroup$

The result is $\binom{n+m}{k}$.

This is known as Vandermonde's identity.

$\endgroup$
1
$\begingroup$

If you want a generating function approach, your sum is equivalent to finding the $x^k$ coefficient of $(1+x)^n(1+x)^m=(1+x)^{m+n}.$ This is easily seen to be $\binom{n+m}{k}$.

$\endgroup$
1
$\begingroup$

The answer is ${n+m \choose k}$ and the best possible intuition is that both this and the big summation are counting all possible ways of choosing $k$ things from two sets of things, one of size $m$ and one of size $n$.

I find it easier to do combinatorial identities by thinking about what the formulas might be counting rather than just doing algebra. This heuristic is really helpful for similar problems.

ALSO: If you wanted to follow the hint that person gave you, you can use the binomial theorem to determine what the coefficient of $x^k$ in $(x+1)^n(x+1)^m = (x+1)^{n+m}$ is, and you can also calculate it by multiplying your expansions of $(x+1)^n$ and $(x+1)^m$. That's actually a really cool way to do it!

$\endgroup$

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.