I would like a combinatorial proof using committee and subcommittee selection for the following identity.

$$\sum_{j=i}^n { n \choose j} { j \choose i} (-1)^{n-j}=0$$

with $i<n$.

This is from Ross's A First Course in Probability, problem number 14c.

I see it this way:

$$ { n \choose j} { j \choose i} = { n \choose i} { n- i \choose j-i} $$

So the sum becomes

$$ \sum_{j=i}^n { n \choose i} { n- i \choose j-i} (-1)^{n-j} = { n \choose i} \sum_{j=i}^n { n- i \choose j-i} (-1)^{n-j} $$

The right hand side becomes ${ n \choose i} \sum_{k=0}^{n-i} { n- i \choose k} (-1)^{n-i-k}$. Since $\sum_{k=0}^{n-i} { n- i \choose k} (-1)^{n-i-k} =0$. The identity hold.

  • 2
    $\begingroup$ Your question is phrased as an isolated problem, without any further information or context. This does not match many users' quality standards, so it may attract downvotes, or be put on hold. To prevent that, please edit the question. This will help you recognise and resolve the issues. Concretely: please provide context, and include your work and thoughts on the problem. These changes can help in formulating more appropriate answers. $\endgroup$ – Aloizio Macedo Oct 5 '15 at 18:49




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.