### (no subject)

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

(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

and thence into

which is the same thing as

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

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

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.