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:

- 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 .
- 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 .
- Solve the resulting equation, getting a closed form for .
- 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