- #1
techmologist
- 306
- 12
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.