Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I need a combinatorial proof for these two identites:

(a) $\sum_{k=0}^{n} \binom{n}{k}^2 x^k = \sum_{k=0}^{n} \binom{n}{k} \binom{2n-k}{n} (x-1)^k$

(b) $\binom{n}{k} ^2 = \sum_{l=0}^{n-k} (-1)^l \binom{k+l}{k} \binom{n}{k+l}\binom{2n-k-l}{n}$

We have a theorem $\sum_{k=0}^{n} e_k x^k = \sum_{k=0}^{n} a_k(x-1)^k$ (where $e_k$ is the number of objects in our universe that have exactly $k$ properties and $a_k$ is an overcounting of the objects that have at least $k$ properties) that looks like it applies nicely to part (a) but I can't come up with a combinatorial interpretation for $e_k$ and $a_k$. Part (b) looks like Inclusion / Exclusion, but I'm stuck on that as well. Any help?

share|cite|improve this question
What have you tried? Where did you got stuck, and need a push to get over the bump? Have you tried to expand the power in the right hand side of (a)? – vonbrand Mar 1 '14 at 21:24
For (a) I figured it was safe to interpret $e_k$ as $\binom{n}{k}^2$ and $a_k$ as $\binom{n}{k} \binom{2n-k}{n} $ because of the theorem we were given. I've considered representing the LHS as choosing committees of $n$ men and $n$ women, but I can't think of a property set that would represent it or how the RHS would be interpreted. For part (b), we have an example involving binary sequences to produce a similar identity, but I can't extend it to what part (b) is saying. – Curtis Mar 1 '14 at 21:39

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.