July 16th, 2011

beartato phd

(no subject)

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.