- #1

- 299

- 12

## Main Question or Discussion Point

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

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

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.

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

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.