Generating Functions & Series Tricks Cheat Sheet

Key Facts

• The ordinary generating function for a sequence $a_0, a_1, a_2, \ldots$ is $A(x) = \sum_{n=0}^{\infty} a_n x^n$.
• Coefficient extraction is written as $[x^n]A(x)$, meaning the coefficient of $x^n$ in the power series $A(x)$.
• The basic geometric series identity is $\frac{1}{1-x} = \sum_{n=0}^{\infty} x^n$ for $|x| < 1$.
• Shifting a generating function by multiplying by $x^k$ gives $x^k A(x) = \sum_{n=0}^{\infty} a_n x^{n+k}$.
• Differentiating gives $A'(x) = \sum_{n=1}^{\infty} n a_n x^{n-1}$, which helps create factors of $n$.
• The series for counting nonnegative solutions to $a+b+c=n$ is $\frac{1}{(1-x)^3}$, and $[x^n]\frac{1}{(1-x)^3} = \binom{n+2}{2}$.
• If a recurrence is linear, multiply both sides by $x^n$, sum over valid $n$, and solve algebraically for the generating function.
• The product $A(x)B(x)$ has coefficients $[x^n]A(x)B(x) = \sum_{k=0}^{n} a_k b_{n-k}$, called convolution.

Vocabulary

Generating function

A power series such as $A(x) = \sum_{n=0}^{\infty} a_n x^n$ that stores the terms of a sequence as coefficients.

Coefficient extraction

The notation $[x^n]A(x)$ means the coefficient of $x^n$ in the expanded form of $A(x)$.

Ordinary generating function

A generating function where the sequence term $a_n$ is paired directly with $x^n$.

Geometric series

A series of the form $1+x+x^2+x^3+\cdots$ whose sum is $\frac{1}{1-x}$ when $|x| < 1$.

Convolution

A rule for multiplying generating functions where the coefficient of $x^n$ is $\sum_{k=0}^{n} a_k b_{n-k}$.

Recurrence relation

An equation that defines each term of a sequence using earlier terms, such as $a_n = a_{n-1}+a_{n-2}$.