An interesting equality came up in a probability problem I have been looking at. It seems that the following equality is true for all $m,j\in\mathbb{N}$ such that $j<m$. I briefly tested the first few cases using python.

$$\sum_{i=j}^{m-1}(-1)^{m-i+1}\binom mi\binom ij=\binom mj$$

I have looked at a few sources for combinatorial identities, but I have not been able to find this one, a clearly analogous case, or indeed any involving alternating series of binomial coefficients. I was wondering if this was is a case of a known identity, and how one would go about proving it. Double induction, or potentially a double counting proof using the inclusion-exclusion principle come to mind.

If it is of any interest, this comes about when counting the number of sequences of length $n$ containing only members 0f $\{1,2,...,N\}$ such that each member appears at least once.


Notice that: $${m\choose i}{i\choose j}={m\choose j}{m-j\choose i-j}.$$ Afterward use binomial theorem.

  • $\begingroup$ (+1) I was just about to note this identity. $\endgroup$ – robjohn Aug 12 '16 at 20:27
  • $\begingroup$ Thanks. I saw that identity, but didn't realize the resulting sum could be reindexed into a binomial theorem sum. $\endgroup$ – Kajelad Aug 12 '16 at 20:32

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.