Finding a closed form for binomial coefficient summation 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?
 A: 
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}$.
A: The result is $\binom{n+m}{k}$.
This is known as Vandermonde's identity.
A: 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!
A: 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}$. 
