Interpretation for identity with binomial coefficients

[techmologist]

I am looking for a counting interpretation to make the following identity evident:

\sum_{k=0}^{n-j}(-1)^k\binom{j-1+k}{j-1}\binom{n}{j+k} = 1

The form of it looks like inclusion-exclusion. The sum is 1, more or less independent of j. So that makes me think it would be something like "how many ways can you toss a coin n times, getting heads on the first j tosses and tails on the rest?", which obviously happens in one way. The problem is, I don't see how the left side of the equation can be interpreted that way.

Thanks in advance.

 

[eigenperson]

The easiest way to deal with identities having alternating signs is to use the "involution principle", which is not much more than a fancy name for moving the negative terms to the other side. (See Stanley, Enumerative Combinatorics, vol. 1, section 2.6.)

The quantity \binom{n}{j+k}\binom{j-1+k}{j-1} counts the number of ways to take a row of $n$ balls and choose $j+k$ of them to paint. Of these, you paint the rightmost one red. Then, of the others, you paint $j-1$ blue and $k$ green.

You can then construct an (almost) "sign-reversing involution" on this set -- basically, this means a bijection between the paintings where k is odd and the paintings where k is even. One way to do this is by starting at the red ball and going to the left one ball at a time until you find a ball that is either green or unpainted. If it's green, you remove the paint; if it's unpainted, you paint it green.

As I said, this is not quite a sign-reversing involution because there is one case where it isn't defined. If, from the left, the row starts with $j-1$ blue balls and then a red ball, there is no way to follow the above instruction.

But this is actually a good thing. After all, there was that "1" floating around. So the bijection handles all the cases except for one; to compensate for this, you have to add 1 to the other side. And that gives you the identity you were looking for.

Another way of looking at this is that the sign-reversing involution tells you how to cancel out paintings in pairs, where 1 element of each pair has k even and the other has k odd. Everything is canceled out except for the one exceptional painting, and so after the cancellation you have just 1 left, which is the right side.

 

[techmologist]

Thank you, eigenperson! That was a first rate solution and explanation. I encountered that sum while trying to find an expected value in the broken-stick model here, and couldn't come up with an approach for it.

Thanks again :)