198 BINOMIAL COEFFICIENTS
Generating functions give us powerful ways to discover and/or prove identities. For example, the binomial theorem tells us that (1 + z)~ is the generating function for the sequence ((i) , (;) , (;) , . . ): (1 +z)'
= x (;)2 k30
Similarly,
(1 +z)” = x (;)zk. k>O
If we multiply these togethe:r, (1 +z)T(l
+z)S
we get another generating function:
= (1 +z)'+s.
And now comes the punch line: Equating coefficients of z” on both sides of this equation gives us
g:)(A) = (T). We’ve discovered Vandermonde’s convolution, (5.27)! That was nice and easy; let’s try another. This time we use (1 -z)~, which is the generating function for the sequence ((-1 )"(G)) = ((h) , -(;), (i) , . . . ). Multiplying by (1 + z)~ gives another generating function whose coefficients we know: (1 -- z)'(l + z)' = (1 - z2)'. Equating coefficients of z” now gives the equation
~(~)(n~k)t-lik = (-1)n12(~,)Inevenl.
(5.55)
We should check this on a small case or two. When n = 3, for example, the result is
(a)(;)-(F)(;)+(I)(T)-(;)(6)
= O.
Each positive term is cancelled by a corresponding negative term. And the same thing happens whenever n is odd, in which case the sum isn’t very
[5.27)! = (5.27)[4.27) (3.27)[2.27) (1.27)(0.27)!.
