Finding a closed form for binomial coefficient summation

Question

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?

Answer 1

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

Answer 2

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

This is known as Vandermonde's identity.

Answer 3

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

Answer 4

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!