# 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.

• For an algebraic proof (I don't know why you want one, to be honest), but consider the coefficient of $x^k$ in $(1+x)^n(1+x)^m = (1+x)^{n+m}$. – Andrew D Sep 11 '13 at 17:11
• Its called the Chu-Vandermonde Identity, and there's already a post about it here: math.stackexchange.com/questions/219928/… – Salieri Nov 23 '13 at 13:48
• @AndrewD: The algebraic proof does not depend on $n,m$ being natural numbers (but the binomial powers are now formal powers series); this is one reason why one might want an algebraic proof. – Marc van Leeuwen Nov 23 '13 at 14:57

## 3 Answers

For identities involving binomial coefficients sometimes "combinatorial proofs" and "algebraic proofs" are offered. Here we have two proofs for the Vandermonde Convolution:

1. 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.

2. 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.

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}(\sum_{i=0}^k{n\choose i}{m\choose k-i})x^r.$$ Thus $$\sum_{i=0}^k{n\choose i}{m\choose k-i}={m+n\choose k}.$$

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.