Given an infinite sequence of numbers \(u_0, u_1, u_2, \ldots\), we define the generating function, \(\mathrm{f}\), for the sequence by \[\mathrm{f}(x) = u_0 + u_1x + u_2x^2 + u_3x^3 + \cdots.\] Issues of convergence can be ignored in this question.
Using the binomial series, show that the sequence given by \(u_n = n\) has generating function \(x(1 - x)^{-2}\), and find the sequence that has generating function \(x(1 - x)^{-3}\).
Hence, or otherwise, find the generating function for the sequence \(u_n = n^2\). You should simplify your answer.
The sequence \(u_0, u_1, u_2, \ldots\) is determined by \(u_n = ku_{n-1}\) (\(n \geq 1\)), where \(k\) is independent of \(n\), and \(u_0 = a\). By summing the identity \(u_nx^n \equiv ku_{n-1}x^n\), or otherwise, show that the generating function, \(\mathrm{f}\), satisfies \[\mathrm{f}(x) = a + kx\,\mathrm{f}(x).\] Write down an expression for \(\mathrm{f}(x)\).
The sequence \(u_0, u_1, u_2, \ldots\) is determined by \(u_n = u_{n-1} + u_{n-2}\) (\(n \geq 2\)) and \(u_0 = 0\), \(u_1 = 1\). Obtain the generating function.
The hook
Work out \(1/89\) on a calculator: \(0.011235955\ldots\). The digits begin \(0, 1, 1, 2, 3, 5\), the Fibonacci numbers. Is this a coincidence? It is not, and this question explains why.
The idea is one of the most powerful in combinatorics. Take an infinite sequence of numbers and package it as a single function, by using the terms as the coefficients of a power series. Then facts about the sequence become facts about the function, and you can use algebra and calculus on them. Herbert Wilf put it memorably: “A generating function is a clothesline on which we hang up a sequence of numbers for display.”
Before you start
What sequence has generating function \(\dfrac{1}{1 - x}\)? What about \(\dfrac{1}{1 - 2x}\)? What happens to the sequence if you multiply its generating function by \(x\)?
The geometric series \(\frac{1}{1 - x} = 1 + x + x^2 + \cdots\) is the generating function of \(1, 1, 1, \ldots\), and \(\frac{1}{1 - 2x} = 1 + 2x + 4x^2 + \cdots\) that of the powers of \(2\). Multiplying by \(x\) shifts every term one place along: \(x \cdot \frac{1}{1-x} = x + x^2 + \cdots\) belongs to \(0, 1, 1, 1, \ldots\).
Working it through
Stage 1 The natural numbers and the triangle numbers
Expand \((1 - x)^{-2}\) by the binomial series. What is the coefficient of \(x^n\)?
The binomial series gives \[(1 - x)^{-2} = 1 + 2x + 3x^2 + 4x^3 + \cdots = \sum_{n \geq 0}(n + 1)x^n,\] so \(x(1 - x)^{-2} = x + 2x^2 + 3x^3 + \cdots = \sum n x^n\): the generating function of \(u_n = n\).
Similarly, the coefficient of \(x^n\) in \((1 - x)^{-3}\) is \(\frac{(-3)(-4)\cdots(-3-n+1)}{n!}(-1)^n = \frac{(n + 1)(n + 2)}{2}\), so \[x(1 - x)^{-3} = \sum_{n \geq 1}\frac{n(n + 1)}{2}\,x^n = x + 3x^2 + 6x^3 + 10x^4 + \cdots,\] the generating function of the triangle numbers \(u_n = \frac12 n(n + 1)\).
How can you write \(n^2\) in terms of \(n\) and \(\frac12n(n + 1)\)?
Since \(n^2 = 2 \cdot \frac12 n(n + 1) - n\), and generating functions add just as sequences do, \[\sum n^2 x^n = \frac{2x}{(1 - x)^3} - \frac{x}{(1 - x)^2} = \frac{2x - x(1 - x)}{(1 - x)^3} = \frac{x(1 + x)}{(1 - x)^3}. \qed\]
Stage 2 A recurrence becomes an equation
Multiply \(u_n = ku_{n-1}\) by \(x^n\) and add up over all \(n \geq 1\). What is each side, in terms of \(\mathrm{f}\)?
The left side is \(\sum_{n \geq 1}u_nx^n = \mathrm{f}(x) - u_0 = \mathrm{f}(x) - a\). The right side is \(kx\sum_{n \geq 1}u_{n-1}x^{n-1} = kx\,\mathrm{f}(x)\). So \(\mathrm{f}(x) = a + kx\,\mathrm{f}(x)\), and \[\mathrm{f}(x) = \frac{a}{1 - kx}. \qed\] Of course, \(u_n = ak^n\); expanding \(\frac{a}{1 - kx}\) as a geometric series confirms it.
Stage 3 The Fibonacci numbers
Do the same with \(u_n = u_{n-1} + u_{n-2}\), for \(n \geq 2\): \[\sum_{n \geq 2}u_nx^n = x\sum_{n \geq 2}u_{n-1}x^{n-1} + x^2\sum_{n \geq 2}u_{n-2}x^{n-2},\] that is, \[\mathrm{f}(x) - u_0 - u_1x = x\bigl(\mathrm{f}(x) - u_0\bigr) + x^2\,\mathrm{f}(x).\] With \(u_0 = 0\) and \(u_1 = 1\), this says \(\mathrm{f}(x) - x = x\,\mathrm{f}(x) + x^2\,\mathrm{f}(x)\), so \[\mathrm{f}(x) = \frac{x}{1 - x - x^2}. \qed\]
Stage 4 Explaining \(1/89\)
Ignoring convergence (which is fine here: the series converges for \(|x| < 0.618\)), put \(x = \frac{1}{10}\) in \(\mathrm{f}\). What do you get?
\[\frac{1}{10}F_1 + \frac{1}{100}F_2 + \frac{1}{1000}F_3 + \cdots = \mathrm{f}\Bigl(\frac{1}{10}\Bigr) = \frac{1/10}{1 - 1/10 - 1/100} = \frac{10}{89}.\] Dividing by \(10\), \(\frac{1}{89} = \sum F_n/10^{n+1}\). The Fibonacci numbers are placed in successive decimal places, overlapping when they get bigger than \(9\) (Figure 9.4.1). The early digits of \(1/89\) show the Fibonacci numbers; later ones are blurred by carrying.
Looking back
Turn a sequence into a function. The whole infinite sequence became one rational function.
Recurrences become equations. Multiplying by \(x^n\) and summing turned the rule \(u_n = u_{n-1} + u_{n-2}\) into an equation for \(\mathrm{f}\) that could be solved by algebra.
Build new from old. Adding, shifting and differentiating generating functions produced new ones without starting from scratch.
What’s really going on
From generating function to formula
Generating functions do not just encode a sequence: they can solve for it. The denominator factorises as \(1 - x - x^2 = (1 - \varphi x)(1 - \psi x)\), where \(\varphi = \frac{1 + \sqrt5}{2}\) and \(\psi = \frac{1 - \sqrt5}{2}\) are the roots of \(t^2 = t + 1\). Partial fractions give \[\frac{x}{1 - x - x^2} = \frac{1}{\sqrt5}\Bigl(\frac{1}{1 - \varphi x} - \frac{1}{1 - \psi x}\Bigr),\] and expanding each fraction as a geometric series, \[F_n = \frac{\varphi^n - \psi^n}{\sqrt5}.\] This is Binet’s formula. Since \(|\psi| < 1\), the second term is tiny, so \(F_n\) is the nearest integer to \(\varphi^n/\sqrt5\), and the ratio of successive Fibonacci numbers tends to the golden ratio (the subject of Section 2.2). The same method solves any linear recurrence with constant coefficients; the exercises include an example from STEP I 2004.
Why generating functions are so useful
The real power appears when we multiply. The coefficient of \(x^n\) in a product \(\mathrm{f}(x)\mathrm{g}(x)\) is \(\sum_k u_kv_{n-k}\), which adds up over all ways of splitting \(n\) into two parts. That is exactly what we need to count things built from two pieces. The next two sections use it to count the ways of making change (Section 9.5) and to find strangely numbered dice with the same totals as ordinary ones (Section 9.6). In probability, the same idea gives the probability generating function, which turns sums of independent random variables into products.
Abraham de Moivre used generating functions in the 1720s to solve linear recurrences, essentially by the method above. Leonhard Euler used them in 1748 to study partitions of whole numbers, and Pierre-Simon Laplace made them the foundation of his Théorie analytique des probabilités (1812). In the twentieth century they became central to combinatorics, and analytic methods (studying a generating function as a function of a complex variable) now give precise estimates for counting problems far too complicated to solve exactly.
The thinking skill
A problem about a sequence may become easy when the sequence is turned into a function, a matrix, or a picture.
Generating functions translate recurrences into algebra and counting into multiplication. At university you will meet many such translations: Fourier series turn functions into sequences, Laplace transforms turn differential equations into algebra, and matrices turn geometry into arithmetic.
Try this next
Two digits at a time. (From STEP II, 2022.) Using \(F_r \leq 2^{r-n}F_n\) for \(r \geq n\), show that \(\sum_{r \geq 7}F_r/10^r < 2 \times 10^{-6}\), and hence find the first six digits after the decimal point of \(1/89\) with justification. Then find a fraction \(r/s\), with \(r\) and \(s\) positive integers less than \(10000\), whose decimal expansion starts \(0.0001010203050813213455\ldots\).
Solving a recurrence. (From STEP I, 2004.) Let \(a_0 = 2\), \(a_1 = 7\) and \(a_n = 7a_{n-1} - 10a_{n-2}\). Show that the generating function is \(\frac{1}{1 - 2x} + \frac{1}{1 - 5x}\), and hence that \(a_n = 2^n + 5^n\). If \(b_0 = 5\), \(b_1 = 10\), \(b_2 = 40\), \(b_3 = 100\) and \(b_n = pb_{n-1} + qb_{n-2}\), find \(p\), \(q\) and \(b_n\).
Counting numbers. Show that \(\frac{1}{9801} = 0.00\,01\,02\,03\,04\ldots\), with the two-digit blocks counting upwards. Where does the pattern first go wrong, and why?
Sums of squares. Explain why \(\frac{1}{1-x}\mathrm{f}(x)\) is the generating function of the partial sums \(u_0 + u_1 + \cdots + u_n\). Use this and the answer to part (i) to find a formula for \(1^2 + 2^2 + \cdots + n^2\).
Further reading
Herbert Wilf, generatingfunctionology (A K Peters; free online). The classic introduction. Chapter 1 is perfect after this section.
Ronald Graham, Donald Knuth & Oren Patashnik, Concrete Mathematics (Addison-Wesley), Chapter 7.
Philippe Flajolet & Robert Sedgewick, Analytic Combinatorics (Cambridge University Press; free online). Far beyond first year, but the opening pages show where the subject leads.