2
$\begingroup$

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.

$\endgroup$
  • 6
    $\begingroup$ 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}$. $\endgroup$ – Andrew D Sep 11 '13 at 17:11
  • $\begingroup$ Its called the Chu-Vandermonde Identity, and there's already a post about it here: math.stackexchange.com/questions/219928/… $\endgroup$ – Salieri Nov 23 '13 at 13:48
  • 1
    $\begingroup$ @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. $\endgroup$ – Marc van Leeuwen Nov 23 '13 at 14:57
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

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