Generating functions for polynomial sequences

The previous post looked at a generating function for a specific polynomial sequence. This post will look at generating functions for polynomial sequences in general. (There’s an alternating term in the previous post that isn’t polynomial, but we’ll address that too.)

The starting point for this post is a simple observation:

x\left(\frac{d}{dx} x^n \right) = n x^n

If we let xD be the operator that differentiates a function then multiplies the result by x, we have

(xD) x^n = n x^n

We can apply xD m times, each time multiplying xn by a factor of n.

(xD)^m x^n = n^m x^n

And more generally, for any polynomial p(x) we have

p(xD) x^n = p(n) x^n

Now let S be a set of integers and form a generating function F(x) by summing xn over n in S.

p(xD) x^n = p(n) x^n

Then we have

\begin{align*} p(xD)F(x) &= p(xD)\sum_S x^n \\ &= \sum_S p(xD)x^n \\ &= \sum_S p(n)x^n \end{align*}

In words, multiplying the nth term of a generating function by p(n) is the same as operating on the generating function by p(xD).

Example

The previous post computed the generating function of

Z_n = \frac{(-1)^n(3n+6) + 2n^3 + 12n^2 + 25n - 6}{12}

using Mathematica. Here we will compute the generating function again using the result derived below.

Before we computed

g(x) = \sum_{n=1}^\infty Z_nx^n

by summing over the positive integers. But Zn is not quite a polynomial function of n. Aside from the alternating term it is a cubic polynomial in n. The alternating term is a polynomial in n if we restrict ourselves to even values of n, and it is another polynomial if we restrict ourselves to odd values of n.

Define

\begin{align*} F_1(x) &= \frac{2n^3 + 12n^2 + 25n - 6}{12} \\ F_2(x) &= \frac{(3n+6)}{12} \\ F_3(x) &= -\frac{(3n+6)}{12} \\ \end{align*}

Then we have

\sum_{n} Z_nx^n = \sum_{n} F_1(n)x^n + \sum_{n \text{ even}} F_2(n)x^n + \sum_{n \text{ odd}} F_3(n)x^n

for positive integer n, splitting our original generating function into three generating functions, each summed over a different set of integers.

Define

\begin{align*} g_1(x) &= \sum_{n > 1} x^n = \frac{x}{1-x}\\ g_2(x) &= \sum_{n > 1,\, n \text{ even}}^\infty x^n = \frac{x^2}{1 - x^2}\\ g_3(x) &= \sum_{n > 1,\, n \text{ odd}}^\infty x^n = \frac{x}{1 - x^2}\\ \end{align*}

Then

g(x) = F_1(xD)g_1(x) + F_3(xD)g_3(x) + F_3(xD)g_3(x)

If we expand the line above, we should get the same expression for g(x) as in the previous post.

Leave a Reply

Your email address will not be published.