1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Interpretation for identity with binomial coefficients

  1. Sep 16, 2013 #1
    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.
  2. jcsd
  3. Sep 16, 2013 #2
    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 [tex]\binom{n}{j+k}\binom{j-1+k}{j-1}[/tex] 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.
  4. Sep 17, 2013 #3
    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 :)
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook