Algebraic proof of $\sum_{i=0}^k{{n \choose i}{m \choose {k-i}}}= {{m+n}\choose k}$ I can't figure out an algebraic proof for the following identity:
$$\sum_{i=0}^k{{n \choose i}{m \choose {k-i}}}= {{m+n}\choose k}$$
Combinatorical solution:
We can see that as choosing some from $n$ and the rest of $k$ from $m$, thus $k$ in total.
Or we could just choose $k$ from the union.
 A: For identities involving binomial coefficients sometimes "combinatorial proofs" and "algebraic proofs" are offered. Here we have two proofs for the Vandermonde Convolution: 


*

*Algebraic proof: The sum of the LHS of the convolution formula equals the coefficient of $x^k$ on the LHS of the polynomial
$$
(1+x)^n(1+x)^m=(1+x)^{m+n}.
$$
The binomial coefficient on the RHS of the convolutions formula equals the coefficient of $x^k$ on the RHS of the polynomial equation.

*Combinatorial proof: Suppose that there are $n+m$ objects in a set, $n$ of them white and $m$ of them black. There are $\binom{n+m}{k}$ ways to choose $k$ elements in all. This is the RHS. The number of ways to choose $j$ white and $k-j$ black objects is the product $\binom{n}{j}\binom{m}{k-j}$, so the sum of all these objects, the LHS, must be the same total as on the RHS.
A: Using the binomial theorem consider $$\sum_{k=0}^{m+n}{m+n\choose k}x^k=(1+x)^{m+n}.$$ The right-hand side becomes $$(1+x)^m(1+x)^n=(\sum_{r=0}^m{m\choose r}x^r)(\sum_{s=0}^n{n\choose s}x^s).$$ The product of the two polynomials on the right-hand side can be rewritten as  $$\sum_{k=0}^{m+n}\bigg{\{}\sum_{i=0}^k{n\choose i}{m\choose k-i}\bigg{\}}x^k.$$ Thus $$\sum_{i=0}^k{n\choose i}{m\choose k-i}={m+n\choose k}.$$
A: For another proof, see the First Proof of Theorem 3.29 in my Notes on the combinatorial fundamentals of algebra. (NB: It is Theorem 3.29 in the version of 10 January 2019. Theorem labels are subject to change, so search for "Chu-Vandermonde identity" if Theorem 3.29 is something different in your version.) This is not a particularly enlightening proof, but it has the advantage of requiring the least about $n$ and $m$: it works when $n$ and $m$ are elements of a commutative $\mathbb{Q}$-algebra. (Compare to the combinatorial proof, which requires $n$ and $m$ to be nonnegative integers. Compare also to the proof using the binomial formula, which works generally only if one has an algebraic way of proving $\left(1+x\right)^n\left(1+x\right)^m = \left(1+x\right)^{n+m}$ for non-integer $n$ and $m$.)
This has been linked from How do i prove that $\sum\limits_{r=0}^k \binom{m}{r}\binom{n}{k-r} = \binom{m+n}{k}$ , which has other proofs.
