The best reference for generating function tricks and techniques is, of course, Knuth's Fundamental Algorithms (vol. 1 of TaoCP). Add your favourite tricks as additional writeups to this node or by /msging me. A convenient convention which I try to maintain is that the first generating function is
A(z) = a0 + z a1 + z2 a2 + ...,
the second is
B(z) = b0 + z b1 + z2 b2 + ...,
etc. (evidently, no more than 26 generating functions can exist).
- Shifting
- Trivial, but
zk A(z) = zk a0 + zk+1 a1 + ...,
so the generating function for {an-k} is zk A(z); this is chiefly useful in shifting more interesting results to have the general form above.
- Derivation (& integration)
A'(z) = a1 + 2 z a2 + ... + n zn-1 an + ...
so the generating function of (n an) is z A'(z).
- Convolution
-
Multiplying power series is "easy" (if you don't worry about convergence -- and we won't, here):
A(z)B(z) = a0&sdotb0 +
z(a0b1+a1b0) +
z2(a0b2+a1b1+a2b0) + ...
So if we define the convolution sequence cn = a0bn + a1bn-1 + ... + anb0, then the generating function for {cn} is C(z)=A(z)⋅B(Z).
Note the exact parallel with Fourier transforms or Fourier series: convolution in the "time domain" is translated into the much simpler pointwise multiplication in the "frequency domain".
More to follow once (more) round tuits arrive!