Generating functions

2025 March 04

A generating function is a device somewhat similar to a bag. Instead of carrying many little objects detachedly, which could be embarrassing, we put them all in a bag, and then we have only one object to carry, the bag.

— George Pólya

Often when solving a problem, it is useful to consider some sequence of integers $(a_n)$, whether it is finite or infinite in length. Generating functions allow us to treat the entire sequence as one object, reducing a problem to algebra.
Definition 1.
The generating function of a sequence $(a_n)$ is given by \[f(x)=\sum_{i=0}^{\infty} a_ix^i=a_0+a_1x+a_2x^2+a_3x^3+\dots \] and if the sequence is finite the rest of the terms will be zero.
You may recognize the following generating functions: \[\frac{1}{1-x}=1+x+x^2+x^3+\dots\text{ and } (1+x)^n=\sum_{i=0}^{n}\binom{n}{i}x^i. \] In fact, differentiating the first one gives the identity \[\frac{1}{(1-x)^2}=1+2x+3x^2+\dots\implies \sum_{i=0}^{\infty}ix^i=\frac{x}{(1-x)^2}. \] Generating functions look like polynomials with infinite degree, and we see that the typical operations of addition, multiplication, and even differentiation are still defined in the same way. But does it mean that we can still treat it as a real function (i.e. plugging in values for $x$)? To see how this would go wrong, you may check that the generating function for the sequence $(a_n)=n!$, $f(x)=\sum_{n=1}^{\infty} (n!)x^n$ will never converge for any value of $x$, no matter how small. So generating functions are actually these objects called ‘formal series’\footnote{To assure you that they are a real mathematical object with meaning: they form a ring, which is denoted $R[[x]]$ over some ring $R$; on the reals this is ${\mathbb R}[[x]]$.} on which the operations are defined in the way you’d expect, \begin{align*} A(x)&=\sum a_ix^i,\ B(x)=\sum b_ix^i \\ A(x)+B(x)&=\sum_{n=1}^\infty (a_n+b_n)x^n, A(x)\cdot B(x)=\sum_{n=1}^\infty \left(\sum_{i=0}^n a_ib_{n-i}\right) x^n,\\ A’(x) &= \sum na_i x^{n-1}, \end{align*} and they are considered independently of convergence. But usually (and this is where the handwaving starts), if it makes sense it’s valid.
Example 2. (Mandelbrot)
Let $F_n$ be the $n$th Fibonacci number. Find the sum \[\sum_{n=1}^{\infty}\frac{F_n}{3^n}.\]
Solution, without generating functions. Let the requested sum be $S$. Then \[\frac{F_n}{3^n}=\frac{1}{3} \cdot \frac{F_{n-1}}{3^{n-1}}+\frac{1}{9}\cdot \frac{F_{n-2}}{3^{n-2}},\] so we write \[S\left(1-\frac{1}{3}-\frac{1}{9}\right)=\frac{F_1}{3}+\sum_{i=2}^{\infty} \frac{F_n-F_{n-1}-F_{n-2}}{3^n} \] and because the second term is zero, the answer is $S=(1/3)/(1-1/3-1/9)=3/5$. $\square$
Solution, with generating functions. Consider the generating function $F(x)=\sum_{n=0}^{\infty} F_n x^n.$ Then because \[F_nx^n=x\cdot F_{n-1}x^{n-1}+x^2\cdot F_{n-2}x^{n-2},\] we can explicitly find $F$. Convince yourself that this is true: \[F(x)(1-x-x^2)=x.\] So $F(x)=x/(1-x-x^2)$, and plugging in $1/3$ gives $S=F(1/3)=5/3$. $\square$
Hopefully, seeing how the two solutions are so similar convinces you that the last step of plugging in $x=1/3$ is valid whenever the series converges. Now here is an example which looks less like an algebra problem, yet still has a simple solution with generating functions:
Example 3.
How many ways are there to put $n$ fruits (only oranges, bananas, pineapples, and watermelons) into a basket such that:
Outline. Let $f_n$ be the number of ways to fill the basket. Consider the generating function $F(x)=\sum_{n\ge 0} f_nx^n$; we will try to find $F(x)$ instead (this is a common strategy).
  1. Let the generating function for choosing oranges be $O(x)$, similarly define $B(x)$ for bananas, $P(x)$ for pineapples, $W(x)$ for watermelons. Why do we have \[O(x)=1+x^2+x^4+\dots+=\frac{1}{1-x^2}?\]
  2. Why is it true that $F(x)=O(x)\cdot B(x)\cdot P(x)\cdot W(x)$?
  3. Find $F(x)$ and conclude that the answer is $n+1$.
$\square$
Exercise 4.
The expression \[(x+y+z)^{2006}+(x-y-z)^{2006}\] is simplified by expanding it and combining like terms. How many terms are in the simplified expression?
Example 5. (2003 AIME)
A bug starts at a vertex of an equilateral triangle. On each move, it randomly selects one of the two vertices where it is not currently located, and crawls along a side of the triangle to that vertex. Given that the probability that the bug moves to its starting vertex on its tenth move is $m/n,$ where $m$ and $n$ are relatively prime positive integers, find $m + n.$
There is a less overkill solution with states, but of course, it’s generating function time.
Solution. The generating function $(x+x^2)^{10}$ represents the number of ways the bug can move $n$ steps clockwise (for example) after ten moves, because it can move $120^\circ$ or $240^\circ$. Then, the total number of ways to traverse the triangle is $2^{10}$, but the number of ways to return to its starting vertex is the sum of the coefficients with $x^k$ such that $3$ divides $k$. Then \[x^{10}(x+1)^{10}\] has coefficient $\binom{10}{2}$ for the $x^{12}$ and $x^{18}$ term, and $\binom{10}{5}$ for the $x^{15}$ term. Hence the answer is \[\frac{2\cdot \binom{10}{2}+\binom{10}{5}}{2^{10}}=\frac{171}{512}\implies \boxed{683}.\] $\square$
Here is a problem with a multivariable generating function; certainly overkill, but there’s no longer any need for careful casework.
Example 6. (2007 AIME)
In a 6 x 4 grid (6 rows, 4 columns), 12 of the 24 squares are to be shaded so that there are two shaded squares in each row and three shaded squares in each column. Let $N$ be the number of shadings with this property. Find the remainder when $N$ is divided by 1000.
Solution. Given the generating function $P(a,b,c,d)$, let the degree of $a$, $b$, $c$, $d$ in a term represent the number of cells in a column which are shaded. Then, a row with two shaded squares is represented by $ab+ac+ad+bc+bd+cd$, and \[P(a,b,c,d)=(ab+ac+ad+bc+bd+cd)^6,\] and we are trying to find the coefficient of $(abcd)^3$. Anyone who has mucked around with these expressions enough should recognize the first line immediately (otherwise, it’s a bit unmotivated): \begin{align*} P(a,b,c,d) &= (ab+cd+(a+b)(c+d))^6 \\ &= \sum_{k=0}^{6} \binom{6}{k}(ab+cd)^k(a+b)^{6-k}(c+d)^{6-k} \end{align*} Then, we take only the term from the $(a+b)^{6-k}$ term which has equal exponents in $a$ and $b$, because only those contribute to the coefficient of $(abcd)^3$; the coefficient of it in $P(a,b,c,d)$ is the same as in \begin{align*} \sum_{k=0}^{3}\binom{6}{2k}(ab+cd)^{2k}(abcd)^{3-k}\binom{6-k}{3-2k}^2 ; \end{align*} again we only need the “middle” term of the $(ab+cd)^{2k}$ term, so the coefficient of $(abcd)^3$ is the same as in \[\sum_{k=0}^{3}\binom{6}{2k}\binom{2k}{k}\binom{6-2k}{3-k}^2\] which is $1860\implies \boxed{860}$ (after some computation). $\square$
Example 7. (All Soviet MO 1986)
Let $n\in {\mathbb N}$ and consider all polynomials with coefficients $\{0,1,2,3\}$. How many of these satisfy $P(2)=n$?
Solution. Let $a_n$ be the number of such polynomials; we will try to find the generating function $f(n)=\sum_{n\ge 0} a_nx^n$. If we only consider polynomials of degree at most $d$, then \[f_d(x)=\sum_Px^{P(2)},\] as each single term increments $a_{P(2)}$ by one, which is what counting is. Then, we can use the convenient additive properties of exponentiation to write \begin{align*} f_d(x)&=\sum_{c_0=0}^{3}\sum_{c_1=0}^{3}\sum_{c_2=0}^{3}\dots \sum_{c_d=0}^{3} x^{c_0+c_1\cdot 2+c_2\cdot 2^2+\dots c_d\cdot 2^d} \\ &= \prod^d_{k=0}\left(1+x^{2^k}+x^{2\cdot 2^k}+x^{3\cdot 2^k}\right)=\prod^d_{k=0}\frac{1-x^{2^{k+2}}}{1-x^{2^k}}\\ &= \frac{(1-x^{2^{d+1}})(1-x^{2^{d+2}})}{(1-x)(1-x^2)} \end{align*} Now we consider $f_d(x)$ for arbitrarily large $d$. Every term in $f_d(x)$ which has exponent smaller than $x^{2^{d+1}}$ matches exactly the corresponding term in $f(x)$. So as $d$ becomes arbitrarily large, $f_d(x)$ matches the terms of $f(x)$, and they approach equality. But then, if $x$ is small enough (i.e. $|x|<1$) then the numerator of $f_d(x)$ will approach $1$ (remember $d$ arbitrarily large), and \[f(x)=\frac{1}{(1-x)(1-x^2)}.\] To recover the coefficients of $f$, we use partial fraction decomposition: \begin{align*} \frac{1}{(1-x)^2(1+x)}&=\frac{a}{1-x}+\frac{b}{(1-x)^2}+\frac{c}{1+x}\\ f(x)&=\sum_{n\ge 0}\left( \frac{1}{4} +\frac{(-1)^n}{4}+\frac{n+1}{2} \right)x^n, \end{align*} and $a_n=\left\lfloor \frac n2 \right\rfloor+1$. $\square$

$\S$0.0. Identities

Example 8.
Show that \[\sum_{i=0}^{1000}n\binom{1000}{n} = 1000\cdot 2^{999}. \]
Outline. Take the derivative of $(1+x)^{1000}$. $\square$
Theorem 9. (Vandermonde Identity)
Show that \[\sum_{i=0}^{k}\binom{m}{i}\binom{n}{k-i} = \binom{n+m}{k} \]
Outline. What generating function would contain a term $\binom{n+m}{k}$? (You may not be used to thinking of this expression as a “generating function”.) Then, how does this proof correspond to the combinatorial proof of Vandermonde? $\square$
Proposition 10.
\begin{align*} \frac{x^m}{(1-x)^{m+1}}&=\sum_{k\ge 0}\binom{m}{k}x^k\\ (1+x)^r &= \sum_{k\ge 0}\binom{r}{k}x^k \end{align*} where $\dbinom{r}{k}=\dfrac{r(r-1)(r-2)\dots(r-k+1)}{k!}$ is the extended binomial coefficient.
Example 11. (Mathematical Olympiad Series Vol. 4)
Show that for all positive integers $n$, we have \[\sum_{i=0}^{n}\binom{2n+1}{2i}\binom{2i}{i}2^{2n-2i+1} = \binom{4n+2}{2n+1}. \]
Outline. Express $(1+x)^{4n+2}$ as $(1+x)^{2\cdot (2n+1)}$, then find the coefficient of $x^{2n+1}$. $\square$

$\S$0. Problems

Many of these problems are from the books 112 Combinatorial Problems and Problems From The Book, because I’m lazy and they’re great books.
Problem 1. (1989 AHSME) A child has a set of $96$ distinct blocks. Each block is one of $2$ materials (plastic, wood), $3$ sizes (small, medium, large), $4$ colors (blue, green, red, yellow), and $4$ shapes (circle, hexagon, square, triangle). How many blocks in the set differ from the ’plastic medium red circle’ in exactly $2$ ways? (The ’wood medium red square’ is such a block)
Problem 2. (2005 Alabama ARML TST) Two six-sided dice are constructed such that each face is equally likely to show up when rolled. The numbers on the faces of one of the dice are $1, 3, 4, 5, 6,\text{ and }8$. The numbers on the faces of the other die are $1, 2, 2, 3, 3,\text{ and }4$. Find the probability of rolling a sum of $9$ with these two dice.
Problem 3. (2006 AIME) Seven teams play a soccer tournament in which each team plays every other team exactly once. No ties occur, each team has a $50\%$ chance of winning each game it plays, and the outcomes of the games are independent. In each game, the winner is awarded a point and the loser gets 0 points. The total points are accumulated to decide the ranks of the teams. In the first game of the tournament, team $A$ beats team $B.$ The probability that team $A$ finishes with more points than team $B$ is $m/n,$ where $m$ and $n$ are relatively prime positive integers. Find $m+n.$
Problem 4. (2008 Mock ARML) Given that $\sum_{i = 0}^{n}a_ia_{n - i} = 1$ and $a_n > 0$ for all non-negative integers $n$, evaluate $\sum_{j = 0}^{\infty}\frac {a_j}{2^j}$.
Problem 5. (Tribonacci) Define the tribonacci sequence as $(T_n)$ such that $T_0=T_1=T_2=1$, and $T_n=T_{n-1}+T_{n-2}+T_{n-3}$. Find the generating function for $(T_n)$.
Problem 6. (Partitions) The partition function $p(n)$ takes in an integer $n$, and gives the number of ways to split it into an ordered sum of integers. For example, $p(3)=3$, because $3=1+1+1,1+2,2+1$. Find the generating function $\sum_{n\ge 0}p(n)x^n$. (Unfortunately, this doesn’t give a closed form for $p(n)$.)
Problem 7. (2007 iTest) Fermi and Feynman play the game Probabicloneme in which Fermi wins with probability $a/b$, where $a$ and $b$ are relatively prime positive integers such that $a/b<1/2$. The rest of the time Feynman wins (there are no ties or incomplete games). It takes a negligible amount of time for the two geniuses to play Probabicloneme so they play many many times. Assuming they can play infinitely many games (eh, they’re in Physicist Heaven, we can bend the rules), the probability that they are ever tied in total wins after they start (they have the same positive win totals) is $17/77$. Find the value of $a$.
Problem 8. (Catalan sequence) The catalan numbers $C_n$ are defined by the recursive relation \[C_n=C_0C_{n-1}+C_1C_{n-2}+\dots+C_kC_{n-k-1}+\dots+C_{n-1}C_0,\] and its first few terms are $C_0=1,\ C_1=2,\ C_2=5,\ \dots$. Find its generating function, and thus a closed form for $C_n$.
Problem 9. The set of natural nmbers is partitioned into finitely many arithmetic progressions $\{a_i+dr_i\}$, $1\le i\le n$. Prove that:
  1. $\sum_{i=1}^{n} \frac{1}{r_i}=1$.
  2. There exist $i\neq j$ such that $r_i=r_j$.
  3. $\sum_{i=1}^{n} \frac{a_i}{r_i} = \frac{n-1}{2}$.
Problem 10. Let $\delta_{ij}=1$ if $i=j$ and zero otherwise. Show that \[\sum_{k=p}^{n}(-1)^k\binom nk\binom kp=(-1)^n\delta_{pn}. \]
Problem 11. (USAMO 1986) By a partition $\pi$ of an integer $n\ge 1,$ we mean here a representation of $n$ as a sum of one or more positive integers where the summands must be put in nondecreasing order. (E.g., if $n=4,$ then the partitions $\pi$ are $1+1+1+1,$ $1+1+2,$ $1+3, 2+2,$ and $4$). For any partition $\pi,$ define $A(\pi)$ to be the number of $1$’s which appear in $\pi,$ and define $B(\pi)$ to be the number of distinct integers which appear in $\pi$ (E.g., if $n=13$ and $\pi$ is the partition $1+1+2+2+2+5,$ then $A(\pi)=2$ and $B(\pi) = 3$). Prove that, for any fixed $n,$ the sum of $A(\pi)$ over all partitions of $\pi$ of $n$ is equal to the sum of $B(\pi)$ over all partitions of $\pi$ of $n.$
Problem 12. Prove that $\sum_{k=0}^{m} \binom mk\binom{n+k}{m} = \sum_{k=0}^{m}\binom mk \binom nk 2^k$.
Problem 13. \[\sum_{\substack{a_1+\dots+a_k=n\\a_1,a_2,\dots a_k>0}} a_1a_2\dots a_k \]
Problem 14. Find the generating functions for \[A(x)=\sum_{n\ge 0}x^{a_n},\ B(n)=\sum_{ge 0} x^{b_n},\] where $a_n$ is the $n$th number which has an even number of ones in its binary representation, $b_n$ is the $n$th number with an odd nmber of ones in its binary representation.
Problem 15. (Root of unity filter) This is a trick which allows us to extract only every $n$th term in a generating function. The most basic application is, for example, finding $\sum_{i\ge 0} \binom{n}{3i}$, but it applies to any generating function $f(x)=\sum_{n\ge 0}a_n x^n$.
  1. Find \[\sum_{n=0}^{50}\binom{100}{50} \] by plugging in $x=1,-1$ to $(1+x)^{100}$.
  2. To find \[\sum_{k\ge 0}\binom{n}{pk}, \] what values of $x$ would allow cancellation in every term in $(1+x)^n$ except those wanted?
Problem 16. (Bulgaria TST 2006) Let $p>2$ be a prime. How many subsets of $\{1,2,\dots,p-1\}$ have the sum of their elements divisible by $p$?
Problem 17. (MOP 1997) Let $p$ be an odd prime. Find the number of 6-tuples $(a,b,c,d,e,f)$ of integers between $0$ and $p-1$ such that \[a^2+b^2+c^2\equiv d^2+e^2+f^2\pmod{p}.\]
Problem 18. (China TST 2018) Let $p(n)$ denote the partition function. Find all positive integers $n$ so that $p(n)+p(n+4)=p(n+2)+p(n+3)$.