Generating Functions

A generating function is a clothesline on which we hang up a sequence of numbers for display.

Generatingfunctionology,
H. S. Wilf
Academic Press, 1994, p. 1

In probability theory, statistics and the theory of Markov chains, the clothesline at hand is woven of the analytic yarn, the Maclauren series strain. It's almost tangible and can be checked point by point wherever the series converges. In combinatorics, the rather delicate threads come from the abstract variety of formal series.

By definition, the (ordinary) generating function of the sequence {a_n}, where, by convention, the index n ranges from 0 to , is a formal series

(*)

f(x) = a₀ + a₁x + a₂x² + a₃x³ + ...

Two such series are equal iff they have exactly same sequence of coefficients. [xⁿ]f(x) is the usual notation for the coefficient a_n in f. Thus, two series f and g are equal iff [xⁿ]f = [xⁿ]g, for all n = 0, 1, 2, ...

The series is formal in that it is defined as an algebraic, not an analytic concept. Formally speaking, we append to the set of numbers (mostly real numbers on these pages) a new term x, whose nature is quite irrelevant for the construction. The new term and the numbers can be added and multiplied, and both operations are postulated to be commutative: a + x = x + a, ax = xa, for all numbers a. Addition is also required to be distributive with respect to the multiplication. Thus expanded set of real numbers becomes a ring, a mathematical construct with two commutative operations -- addition and multiplication, in which the objects do not always have a multiplicative inverse. They do iff a₀ is not 0. For example,

(1 - x)(1 + x + x² + x³ + ...) = 1,

so that we can state that

(1)

1/(1 - x) = 1 + x + x² + x³ + ...

Mulitplicative Inverse Property

The series (*) has a multiplicative inverse iff a₀0.

Proof

Let's simply show how to constructively find the inverse f ^-1 in the form

f ^-1 = b₀ + b₁x + b₂x² + b₃x³ + ...

Such an inverse should satisfy f·f ^-1 = 1 + 0x + 0x² + .... Term by term this gives

a₀b₀ = 1
a₀b₁ + a₁b₀ = 0
a₀b₂ + a₁b₁ + a₂b₀ = 0
...

From the first equation, b₀ = 1/a₀. From the second equation, b₁ = -a₁b₀/a₀. From the second equation, b₂ = -(a₁b₁ + a₂b₀)/a₀, and so on. In this manner indeed, since a₀0, all coefficients b can be found successively.

In analytic terms, x is a variable with the range over the numbers, real or complex, and the identity holds whenever the series on the right is convergent, i.e., whenever |x| < 1. However, in the formal theory we are not concerned with the question of convergence. In this sense, the term generating function is not quite consistent in that the operation of substituting a number for x in order to establish the value of the series at that point, is not legal.

As another example, the binomial theorem

(1 + x)ⁿ = 1 + C(n,1)x + C(n,2)x² + C(n,3)x³ + ... + C(n,n-1)x^n-1 + xⁿ

says that the expression (1 + x)ⁿ is the generating function of the sequence of the binomial coefficients C(n,0), C(n,1), ..., C(n,n). Just from this expression we can derive a famous property of the binomial coefficients:

(2)

C(n,k) = C(n-1,k) + C(n-1,k-1).

What it takes is to equate [x^k](1 + x)ⁿ with [x^k](1 + x)^n-1·(1 + x), or more explicitly, the coefficients of x^k on both sides of the identity

(2')

(1 + x)ⁿ = (1 + C(n-1,1)x + C(n-1,2)x² + C(n,3)x³ + ... + C(n-1,n-1)x^n-1)·(1 + x).

The representation of the function (1 + x)ⁿ as a product of monomials (1 + x)

(1 + x)ⁿ = (1 + x)·(1 + x)· ... ·(1 + x),

with n factors, gives an immediate interpretation of the coefficients C(n, k) in the binomial theorem. The product on the right requires to select either 1 or x from each of the n factors (1 + x). Thus C(n, k) is the number of ways to select k x's.

The binomial theorem makes frequent appearances not only in combinatorics but also in other branches of mathematics, see, for example, a proof of Lucas' Theorem.

What is the generating function of the series 1, -1, 1, -1, ... ? Obviously, it's

1/(1 + x) = 1 - x + x² - x³ + ...

Then

1/(1 - x) + 1/(1 + x) = 2·(1 + x² + x⁴ + ...)

such that the generating function of the series 1, 0, 1, 0, ... is given by

(3)

1/(1 - x²) = 1 + x² + x⁴ + ...

Note that (3) might have been obtained from (1) with the substitution of x² for x. Perversely, it can be shown that the substitution, although deemed illegal at the outset, leads to correct identities as long as the result includes either finite or formal quantities. With a substitution, we for example get without much ado

(4)

1/(1 - cx) = 1 + cx + c²x² + c³x³ + ...,

so that 1/(1 - cx) is the generating function of the series 1, c, c², c³ ...

It's possible to go a step further and ask, What is the generating function of the sequence 1, (1 + x), (1 + x)², (1 + x)³, ... ? An answer must by necessity contain an additional object, other than x, say y, which brings us to the generating functions of more than one argument. For example, from (4) we obtain by substitution

(5)

1 + (1 + x)y + (1 + x)²y² + (1 + x)³y³ + ... = 1/(1 - (1 + x)y).

And further,

[x^k]1/(1 - (1 + x)y)	= 1/(1 - y)·[x^k]1/(1 - x·y/(1-y))
	= 1/(1 - y)·(y/(1-y))^k
	= y^k/(1-y)^k+1.

On the other hand, in (5), we may expand the terms (1 + x)ⁱ according to the binomial theorem

1/(1 - (1 + x)y) = ∑_n∑_kC(n,k)x^kyⁿ,

from where [x^k]1/(1 - (1 + x)y) can also be found to be

[x^k]1/(1 - (1 + x)y) = ∑_nC(n,k)yⁿ

We thus obtain another useful formula:

∑_nC(n,k)yⁿ = y^k/(1-y)^k+1.

which of course could be rewritten in terms of x:

(6)

∑_nC(n,k)xⁿ = x^k/(1-x)^k+1.

Consider now the recurrence relation:

(7)

s_n = s_n-1 + n, s₀ = 0.

It's obvious that s_n is the sum of the first n natural numbers:

s_n = 1 + 2 + 3 + ... + n.

As is well known, the sum is a triangular number, s_n = n(n + 1)/2. There is a very simple proof that was discovered by young Gauss to the astonishment of his teacher. Presently, I'll establish the formula with the help of generating functions.

First let's find the generating function of {s_n},

f(x) = s₀ + s₁x + s₂x² + s₃x³ + ...

Multiply (7) by x^n-1 and sum up:

∑_ns_nx^n-1 = ∑_ns_n-1x^n-1 + ∑_nnx^n-1,

(8)

f(x)/x = f(x) + ∑_nnx^n-1.

If we introduce g(x) = ∑_nnx^n-1 and assume that taking derivative is a legitimate operation (which it is) in the ring of formal series, we may proceed as follows

g(x) = ∑_nnx^n-1 = (∑_nxⁿ)' = [1/(1 - x)]' = 1/(1 - x)².

In combination with (8), this gives f(x)·(1 - x)/x = 1/(1 - x)², from where

(9)

f(x) = x/(1 - x)³.

Now, letting k = 2 in (6)

x/(1-x)³ = ∑_nC(n,2)x^n-1,

which in part means that [xⁿ]x/(1-x)³ = C(n+1,2) = (n+1)n/2. Exactly the same result as above.

References

H. S. Wilf, Generatingfunctionology, Academic Press, 2^nd edition, 1994 (Also available free online.)

Generating Functions

72199745