Jason (jcreed) wrote,

simont's hint about factoring the multinomial got me to a proof of the little identity from yesterday! Take the RHS of

(a choose c)(b choose c) = Σ_n [n choose n-a,n-b,c,a+b-n-c] (-1)^(a+b-n-c)

(I am being careful and writing multinomial coefficients with [brackets] and the traditional binomial abbreviation (P choose Q)=[P choose Q, P-Q] with parens) and turn it into

Σ_n (n choose n-a)[a choose n-b,c,a+b-n-c] (-1)^(a+b-n-c)

and thence into

Σ_n (n choose n-a)(a choose c)[a-c choose n-b,a+b-n-c] (-1)^(a+b-n-c)

which is the same thing as

Σ_n (n choose n-a)(a choose c)(a-c choose a+b-n-c) (-1)^(a+b-n-c)

so all we really need to show, dividing both sides by (a choose c), is

(b choose c) = Σ_n (n choose n-a)(a-c choose a+b-n-c) (-1)^(a+b-n-c)

I'm going to choose some better variable names to clean up the mess. Set m=a+b-n-c and d=a-c. Then this is equivalent to proving

(b choose c) = Σ_m (d+b-m choose d+c)(d choose m) (-1)^m

Now we can work out some examples when d is small and see what the pattern is.

When d=0, it's trivial: it asserts that (b choose c) = (b choose c).
When d=1, it's simple: it asserts that (b choose c) = (b+1 choose c+1) - (b choose c+1). This is, like, the most basic identity in the history of binomial coefficients.
When d=2, it's pretty easy: it asserts that (b choose c) = (b+2 choose c+2) - 2(b+1 choose c+1) + (b choose c+1). But we get this by applying the above identity three times, first to (b choose c), and then to *both* terms in (b+1 choose c+1) and (b choose c+1). Inductively, the fully general version follows quite naturally.
Tags: math

  • (no subject)

    Cat vs. Fence. WHO WILL WIN? Cat is very agile, but... In other news, Lulu copy of thesis just arrived today, and it looks great! Score one more…

  • (no subject)

    Ok, kids, if you want to blow $40+shipping on a color* copy of my thesis I'm not stopping you. *The cover is color no matter what, but this version…

  • (no subject)

    Recently constructed things: First attempt at Lulu-ing thesis. I have ordered a copy for myself to make sure it looks ok. Made a song with tom7…

  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded