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!

Log in or register to write something here or to contact authors.