In the alternate view, the k^2 isn't there any more. Not because we are computing a different number, but because we're organizing the computation differently.

In the alternate view, the k^2 isn't there any more. Not because we are computing a different number, but because we're organizing the computation differently. (It's turned into a d^2 factor, except that we then need to treat the red=blue case differently from the red!=blue case, so it's really a d factor plus a d^2-d factor.) And yes, the last bit of the proof is exactly the same thing as one way to prove that the sum of "even" and "odd" binomial coefficients are equal -- provided n>0. (For the (0 choose whatever) case, the "even" sum is 1 and the "odd" sum is 0.)