# Unusual Combinatorial Identity (Alternating Sum of Binomial Products)

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.