# generating functions

The basic generating function has the form:

, or for short, is the generating function for the sequence , also called . The coefficient of in is denoted .

There are two kinds of “closed form” in generatingfunctionology.

• a closed form for , expressed in terms of , and
• a closed form for , expressed in terms of .

e.g. the generating function for Fibonacci numbers has the closed form ; the Fibonacci numbers themselves have the closed form .

Solving recurrences – THE METHOD

Given a sequence that satisfies a given recurrence, we seek a closed form for in terms of . A solution to this problem via generating functions proceeds in four steps:

1. Write down a single equation that expresses in terms of other elements of the sequence. This equation should be valid for all integers , assuming that .
2. Multiply both sides of the equation by and sum over all . This gives, on the left, the sum , which is the generating function . The right-hand side should be manipulated so that it becomes some other expression involving .
3. Solve the resulting equation, getting a closed form for .
4. To find an exact formula, a closed form for the sequence:
• Expand into a power series and read off the coefficient of .
• If G is a rational function (quotient of two polynomials)
• expand in partial fractions and handle the terms separately.
• OR: If the roots of the denominator polynomial are all different, use the rational expansion theorem below.

The “routine stunt”

Expanding partial fractions
e.g. Expand
This will be expandable in the form .
To find , multiply both sides by and let .
To find , multiply both sides by and let .
To find , substitute in and use the values of and to find .
So

Rational expansion theorem for distinct roots

If , where and the roots are distinct, and if is a polynomial of degree less than , then

i.e.

When is quadratic, i.e. , the equation becomes

Basic generating function manipulations

The calculus of ordinary power series generating functions

Definition. The symbol means that the series is the ordinary power series (‘ops’) generating function for the sequence , i.e. .

Shifting the subscript by 1. the series changes by difference quotient

Therefore
Shift subscript by 2 Iterate the difference quotient operation.

e.g. the Fibonacci recurrence relation translates directly into .

Rule 1. Shifting subscript. If , then, for integer ,

Multiplying terms by and its powers. To multiply the th member of a sequence by causes its ops generating function to be multiplied by , which we will write as . i.e.

What generates ? . In general,

What generates ?
Do the same thing to that is done to : .

Rule 2. If , and P is a polynomial,

Examples.
Find (The terms are )
The answer is the value at of the power series (ignoring convergence issues).

Find a closed formula for the sum of the squares of the first N positive integers.
Begin with the fact that . To obtain the desired series, apply to both sides, then set .

Rule 3. Multiplication of two gfs. If and , then

If are three series that generate sequences and ,

Rule 4. Powers of a series. If , then for a positive integer ,

Example. Find , the number of ways a nonnegative integer can be written as an ordered sum of nonnegative integers.
e.g. , because .
Consider the power series . Since , by Rule 4 we have

Since , .

If , what sequence does generate?

Rule 5. Dividing by . If then

i.e. dividing by replaces the generated sequence by the sequence of its partial sums.

bibliography

Concrete Mathematics – Knuth, Graham, Patashnik, 2nd Ed., Ch. 7
generatingfunctionology – Herbert Wilf – read online