Calculus of generating functions

The main idea behind the calculus of generating functions is to figure out how to compute the generating function of a sequence that is the product (or sum, etc.) of two other sequences whose generating functions are known. There are different rules for dealing with different types of generating functions; for instance, the rules that hold for manipulating ordinary generating functions may have analogues with their exponential generating function counterparts, but the rules are often not the same. Hence, we must be careful when manipulating formal power series, and note which type of generating function we're working with.

Ordinary generating functions

Similar to differentiation in the subject of calculus, we have a lot of rules we can use to manipulate ordinary power series. We'll start with the shift rule.

Shift rule

To start, let's consider an easy example. Suppose we have that

$f(x)\longleftrightarrow \!\!\!\!\!\!\!\!\!\!^{\text{ops}}\ \left\{a_{n}\right\}$,

and we want to find the generating function for the sequence $\left\{a_{n+1}\right\}_{n\geq 0}$. Formally, we want the function g(x) that has power series representation

$g(x)=\sum _{n\geq 0}a_{n+1}x^{n}$.

Since we know that

$f(x)=\sum _{n\geq 0}a_{n}x^{n}$,

We have that

$f(x)-a_{0}=\sum _{n\geq 1}a_{n}x^{n}$,

and reindexing gives

$f(x)-a_{0}=\sum _{n\geq 0}a_{n+1}x^{n+1}$.

Finally, dividing both sides by x, we achieve

${\dfrac {f(x)-a_{0}}{x}}=\sum _{n\geq 0}a_{n+1}x^{n}$,

which was precisely the function we wanted. Setting $g(x)={\dfrac {f(x)-a_{0}}{x}}$, we now have

$g(x)\longleftrightarrow \!\!\!\!\!\!\!\!\!\!^{\text{ops}}\ \left\{a_{n+1}\right\}_{n\geq 0}$, as desired.

From this example, we can derive a rule.

Shift rule

If $f(x)\longleftrightarrow \!\!\!\!\!\!\!\!\!\!^{\text{ops}}\ \left\{a_{n}\right\}$, then the ordinary generating function for the sequence $\left\{a_{n+k}\right\}_{n\geq 0}$ is the function

$g(x)={\dfrac {f(x)-a_{0}-a_{1}x-a_{2}x^{2}-\cdots -a_{k-1}x^{k-1}}{x^{k}}}.$

Polynomial multiplier rule

Again, let

$f(x)\longleftrightarrow \!\!\!\!\!\!\!\!\!\!^{\text{ops}}\ \left\{a_{n}\right\}$.

Suppose we want the generating function for $\left\{na_{n}\right\}_{n\geq 0}$. How can we get this to come about?

Here, we have to be a bit more clever than we were with the shift rule above. Notice that if $f(x)=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots$ then

$f'(x)=0+a_{1}+2a_{2}x+3a_{3}x^{2}+\cdots ,$

which is almost what we want. If we multiply both sides by x, we get

$xf'(x)=0+a_{1}x+2a_{2}x^{2}+3a_{3}x^{3}+\cdots ,$

which is exactly what we want. So, if

$f(x)\longleftrightarrow \!\!\!\!\!\!\!\!\!\!^{\text{ops}}\ \left\{a_{n}\right\},$

then

$xf'(x)\longleftrightarrow \!\!\!\!\!\!\!\!\!\!^{\text{ops}}\ \left\{na_{n}\right\}.$

Immediately, we see the use for some operator notation; notation that will tell us to perform the operation "differentiate f once with respect to x, then multiply the result by x".

We elect to use notation similar to Euler's differential operator (for ease); that is, D. To express this more precisely, we'll stipulate that

$Df=f'(x)$

and that

$(xD)f=xf'(x).$

Applying a similar idea to the one above, if we want to find the OPS for $\left\{n^{2}a_{n}\right\}_{n\geq 0}$ given the generating function for $\left\{a_{n}\right\}_{n\geq 0}$, we would apply the "xD" operator twice. Notation for this would be

$(xD)^{2}f,$

and in words means "differentiate f, multiply by x, differentiate again, and then multiply by x". This leads to the intermediate rule that $(xD)^{k}f\longleftrightarrow \!\!\!\!\!\!\!\!\!\!^{\text{ops}}\ \left\{n^{k}a_{n}\right\}_{n\geq 0}$ whenever f is the generating function for the sequence $\left\{a_{n}\right\}_{n\geq 0}$. Now that we have a rule for multiplying a sequence by n^k, by default we have a rule for multiplying a sequence by any polynomial in n.

Polynomial multiplier rule

If

$f(x)\longleftrightarrow \!\!\!\!\!\!\!\!\!\!^{\text{ops}}\ \left\{a_{n}\right\}_{n\geq 0}$

and p is any polynomial, then

$p(xD)f(x)\longleftrightarrow \!\!\!\!\!\!\!\!\!\!^{\text{ops}}\ \left\{p(n)a_{n}\right\}_{n\geq 0}.$