Lecture 22: Generating Functions
\( \newcommand{\set}[1]{\{#1\}} \newcommand{\comprehension}[2]{\{#1\,\vert\,#2\}} \newcommand{\size}[1]{\left\vert#1\right\vert} \newcommand{\true}{\top} \newcommand{\false}{\bot} \newcommand{\limplies}{\rightarrow} \newcommand{\divides}{\mathbin{\vert}} \newcommand{\mult}{\mathbin{\cdot}} \newcommand{\xor}{\oplus} \newcommand{\union}{\cup} \newcommand{\intersect}{\cap} \newcommand{\complement}[1]{\overline#1} \newcommand{\powerset}{\mathcal{P}} \newcommand{\ixUnion}{\bigcup} \newcommand{\ixIntersect}{\bigcap} \newcommand{\Div}{\mathrm{div}} \newcommand{\gcd}{\mathrm{gcd}} \newcommand{\divmod}{\mathop{\mathbf{divmod}}} \newcommand{\div}{\mathop{\mathbf{div}}} \newcommand{\mod}{\mathop{\mathbf{mod}}} \newcommand{\ceiling}[1]{\lceil#1\rceil} \newcommand{\floor}[1]{\lfloor#1\rfloor} \DeclareMathOperator{\Pr}{Pr} \DeclareMathOperator{\rng}{rng} \DeclareMathOperator{\E}{E} \DeclareMathOperator{\V}{V} \DeclareMathOperator{\T}{T} \DeclareMathOperator{\O}{O} \newcommand{\abs}[1]{\left\lvert#1\right\rvert} \)This is an idea that is both bizarre and brilliant:
Definition 22.1 Let $a_0, a_1, \ldots, a_k ,\ldots $ be an infinite sequence of real numbers. The generating function for this series is the formal power series
\begin{equation*} G(x) = a_0 + a_1 x + a_2 x^2 + \cdots =\sum_{n=0}^\infty a_n x^n \end{equation*}There's more going on here than meets the eye. First, you may be struck by the phrase “formal power series.” This means that we're defining the series without making any assumptions about its convergence for various values of $x$. This also means that calling this a “function” is a misnomer, albeit a suggestive one. In many cases of interest, the series will converge (at least for some open interval containing $0$), and so $G(x)$ can indeed be thought of as a function.
At this point, we run into couple of fruitful collection of coincidences
- Many interesting series have generating functions with simple closed forms, and
- Many important manipulations of series correspond to manipulations of their generating functions
Example 22.2 Consider the sequence defined by $a_k = 1$ for all $k$. This corresponds to the generating function
\begin{equation*} G(x) = 1 + x + x^2 + \cdots = {1 \over 1-x}. \end{equation*}This is a result that's important enough that we should try to understand it in a few different ways.
First, we can approach this by noting
\begin{align*} G(x) &= 1 + x + x^2 + x^3 +\cdots\\ x G(x) &= \phantom{1} \mathop{\phantom{+}} x + x^2 + x^3 +\cdots\\ \end{align*}Subtracting the second equation from the first yields
\begin{align*} G(x) - x G(x) &=1\\ (1-x) G(x) &=1\\ G(x) = {1\over 1-x}\\ \end{align*}Second, if we know a little calculus, we can prove by induction on $k$ that
\begin{equation*} \frac{d^k (1-x)^{-1}}{dx^k} = k! (1-x)^{-k-1} \end{equation*}so
\begin{equation*} \left. \frac{d^k (1-x)^{-1}}{dx^k} \right|_{x=0} = k! \end{equation*}from which we get the Taylor series
\begin{equation*} 1 + {1!\over 1!}x + {2!\over 2!} x^2 + {3! \over 3!} x^3 \cdots = 1 + x + x^2 + x^3 + \cdots \end{equation*}Finally, we can do a polynomial long division, but with the powers reversed. (I don't yet know how to display this using MathJax...)
Example 22.3 Let $n$ be a positive integer. Consider the sequence $a_k = {n\choose k}$, where $a_k = 0$ for $k \gt n$. The generating function is
\begin{equation*} G(x) = {n \choose 0} 1 + {n \choose 1} x + {n \choose 2}x^2 + \cdots + {n \choose n} x^n. \end{equation*}By the binomial theorem, $G(x) = (1+x)^n$. Note that in this case (and in all cases where $a_k$ is almost always $0$, the generating function turns out to be a simple polynomial.
Theorem 22.4 Let $F(x) = \sum_{k=0}^\infty a_k x^k$ and $G(x) = \sum_{k=0}^\infty b_k x^k$. Then
- $F(x) + G(x) = \sum_{k=0}^\infty (a_k + b_k) x^k$, and
- $F(x) \mult G(x) = \sum_{k=0}^\infty \left(\sum_{j=0}^\infty (a_j b_{k-j}) \right)x^k$.
Note that we can take these as definitions of sums and powers of formal power series without worrying about convergence, but if we want to use them with closed-form expressions that happen to have power series of interest, we need that the series for $F$ and $G$ both converge in an open interval including $0$. Fortunately, that is the usual case.
Example 22.5 We know that the generating function for the series $a_k=1$ is $1/(1-x)$. Consider $1/(1-x)^2 = 1/(1-x) \mult 1/(1-x)$. The generating function for this will be \begin{align*} G(x) &= \sum_{k=0}^\infty \left(\sum_{j=0}^k (1 \mult 1) \right)x^k.\\ &= \sum_{k=0}^\infty (k+1) x^k \end{align*}
by applying Theorem 22.4.
Interestingly enough, there's another road to the same destination. Consider again the generating function
\begin{align*} G(x) &= 1 + x + x^2 + x^3 + \cdots \end{align*}If we differentiate(!) each side, we get
\begin{align*} G'(x) &= \frac{d}{dx} \left(\sum_{k=0}^\infty x^k\right)\\ &= \sum_{k=0}^\infty \frac{d}{dx}(x^k)\\ &= \sum_{k=1}^\infty k x^{k-1}\\ &= \sum_{k=0}^\infty (k+1) x^k\tag{replace $k$ with $k+1$} \end{align*}But
\begin{align*} G'(x) &= \frac{d}{dx}\left({1\over 1-x}\right)\\ &= \frac{d}{dx} (1-x)^{-1}\\ &= (-1)(1-x)^{-2} \frac{d}{dx}(1-x)\\ &= (-1)(1-x)^{-2}(-1)\\ &= (1-x)^{-2} \end{align*}as before.
This a bit annoying, though. That $k+1$ term offends my sense of symmetry and good order. We could get rid of it easily enough, by simply subtracting...
\begin{align*} {1 \over (1-x)^2} - {1 \over 1-x} &= \left(\sum_{k=0}^\infty (k+1) x^k\right) - \left(\sum_{k=0}^\infty x^k\right)\\ {x \over (1-x)^2} &= \sum_{k=0}^\infty k x^k \end{align*}But another approach would be to get the powers to align:
\begin{align*} x G'(x) &= x \left(\sum_{k=0}^\infty (k+1) x^k\right)\\ {x \over (1-x)^2} &= \sum_{k=0}^\infty (k+1)x^{k+1}\\ &= \sum_{k=1}^\infty k x^k\tag{replace $k$ by $k-1$}\\ &= \sum_{k=0}^\infty k x^k\tag{the $k=0$ term is $0$} \end{align*}It's nice that we ended up in the same place!
Definition 22.6 We define the decending powers of a real number $u$ much as we defined the ascending powers:
\begin{equation*} u^{\underline{k}} = \begin{cases} 1, &\text{if $k=0$}\\ u(u-1)\cdots(u-k+1), &\text{otherwise} \end{cases} \end{equation*}The extended binomial coefficient is
\begin{equation*} {u \choose k} = u^{\underline{k}}/k! \end{equation*}Example 22.7
- ${1/2 \choose 2} = {(1/2)(-1/2) \over 1 \mult 2} = {-1\over 8}$.
- $ {-1 \choose k} = {(-1)(-2)\cdots(-k)\over 1 \mult 2 \mult \cdots \mult k} = (-1)^k$.
The significance of extended binomial coefficients comes from their appearance in a natural generalization of the binomial theorem:
Theorem 22.8 (Generalized Binomial Theorem) Let $x$ be real with $\abs{x} \lt 1$ and let $u$ be a real number. Then
\begin{equation*} (1+x)^u = \sum_{k=0}^\infty {u \choose k}x^k \end{equation*}Example 22.9 Consider the function $(1+x)^{-n}$, where $n$ is a positive integer. By the generalized binomial theorem,
\begin{equation*} (1+x)^{-n} = \sum_{k=0}^\infty {-n \choose k} x^k \end{equation*}But falling powers of negative numbers are essentially just rising powers:
\begin{align*} {-n \choose k} &= {(-n)(-n-1)\cdots(-n-k+1)\over k!}\\ &= (-1)^k {(n+k-1)^{\underline{k}} \over k!}\\ &= (-1)^k{n+k-1 \choose k} \end{align*}If we substitute $-x$ in for $x$, we now have
Corollary 22.10 (Reciprocal powers)
\begin{equation*} (1-x)^{-n} = \sum_{k=0}^\infty {n+k-1 \choose k} x^k \end{equation*}Remarkable.
The generating function approach can be used profitably even with simple polynomial generating functions.
Example 22.11 Find the number of solutions of
\begin{equation*} x_1 + x_2 + x_3 = 17 \end{equation*}where $2 \leq x_1 \leq 5$, $3\leq x_2 \leq 6$, and $4 \leq x_3 \leq 7$.
A simple approach is to consider the polynomial
\begin{equation*} (x^2 + x^3 + x^4 + x^5)(x^3 + x^4 + x^5 + x^6)(x^4 + x^5 + x^6 + x^7) \end{equation*}The number we're interested in is the coefficient of $x^17$, which is easily determined by a computer algebra system to be $3$. (I just typed it in to wolframalpha.com.)
Recurrence Equations
One of the simpler, and more striking applications of generating functions is in solving recurrence equations. Let's start with a simple observation: the generating function for the series $c\mult r^n$ is
\begin{equation*} G(x) = {c \over 1-rx} \end{equation*}*Exercise 22.12 Prove that $G(x) = c /(1-rx)$ is the generating function for $c \mult r^n$ two different ways:
- By deriving the series from the closed form by long division based on the closed form, justifying your argument through an explicit induction, and
- By starting with the formal series, and manipulating it in the style of the arguments that follow.
Example 22.13 Let's consider the recurrence that we lead off Lecture 21 with:
\begin{equation*} f(n) = \begin{cases} 0,&\text{if $n = 0$}\\ 1,&\text{if $n = 1$}\\ 5 f(n-1) - 6 f(n-2),&\text{otherwise}\\ \end{cases} \end{equation*}Let $G(x)$ be the generating function for the sequence $f(n)_{n\in\mathbb{N}}$. The idea is to built set up a formal power series for $G(x)$, and then use the recurrence to replace the coefficients that occur in that power series. We then manipulate the right hand side, with the aim of re-introducing $G(x)$.
Define $G(x)$ as a formal power series
\begin{equation*} G(x) = \sum_{n=0}^\infty f(n)x^n \end{equation*}Break off the first two terms of the sum, setting ourselves up to apply the recurrence
\begin{equation*} = f(0) + f(1)x + \sum_{n=2}^\infty f(n)x^n \end{equation*}Apply the recurrence, substituting out $f(0)$, $f(1)$ and $f(n)$ for $n>2$
\begin{equation*} = x + \sum_{n=2}^\infty (5 f(n-1) - 6 f(n-2)) x^n \\ \end{equation*}Distribute the summation
\begin{equation*} = x + \sum_{n=2}^\infty 5 f(n-1) x^n - \sum_{n=2}^\infty 6 f(n-2) x^n \end{equation*}Having reached this point, our goal is to massage the two summations, until we recover the original form within each, which we can then rewrite as $G(x)$. A first step is to re-index the summations, so that that argument of $f$ inside of each sum is $n$, rather than $n-1$ or $n-2$
\begin{equation*} = x + \sum_{n=1}^\infty 5 f(n) x^{n+1} - \sum_{n=0}^\infty 6 f(n) x^{n+2} \end{equation*}Pull out common factors from each of the summations
\begin{equation*} = x + 5 x \sum_{n=1}^\infty f(n) x^n - 6 x^2 \sum_{n=0}^\infty f(n) x^n \end{equation*}At this point, the second summation is in the form we want, but the first is not, as it is indexed from $n=1$ rather than from $n=0$. We fix this by adding and subtracting the missing term
\begin{equation*} = x + 5 x (\sum_{n=0}^\infty f(n) x^n - f(0) x^0) - 6 x^2 \sum_{n=0}^\infty f(n) x^n \end{equation*}Of course, $f(0) = 0$, so that added and subtracted term was just $0$
\begin{equation*} = x + 5 x \sum_{n=0}^\infty f(n) x^n - 6 x^2 \sum_{n=0}^\infty f(n) x^n \end{equation*}We're now set up to replace the summations by $G(x)$
\begin{equation*} = x + 5 x G(x) - 6 x^2 G(x) \end{equation*}The game now changes from manipulation of summations to solving for $G(x)$ algebraically.
\begin{align*} G(x) &= x + 5 x G(x) - 6 x^2 G(x) \\ G(x) - 5x G(x) + 6 x^2 G(x) &= x \\ (1 - 5x + 6 x^2) G(x) &= x \\ G(x) &= {x \over 1 - 5x + 6 x^2} \\ &= {1 \over 1-3x} - {1 \over 1-2x}\\ \end{align*}Where the last line follows from a partial fraction decomposition.
We can immediately infer, from the additivity of generating functions and our knowledge of the these reciprocal forms, that $f(n) = 3^n-2^n$.
Example 22.14 While it's nice to be able to do old things in new ways, it's even nicer when the new way allows us to do new things.
That non-homogeneous term $3^n$ prevents us from approaching this by yesterday's technology, but we can use generating functions. Working as before, we start with a definition of the power series Because the recurrence has only two cases, we need only split off a single term, We now begin “fixing” the sums. For the first, we have to reindex, for the second, we have to deal with a missing term.. We can now deal with the two sums in different ways, for the first, re-introducing $G(x)$, and for the second, introducing an explicit function. Finally, we solve for $G(x)$ From this, we can immediately infer that $a_n = 3^{n+1} - 2^{n+1}$. A simple inductive argument provides a check on the form of the solution. *Exercise 22.15 Consider the recurrence Solve the recurrence using generating functions. [Note a surprising cancellation!] The first year I taught discrete math, I assigned what I though was a straightforward exercise: A Broken Exercise: Solve the recurrence It turns out that this can be done, but it's hardly trivial. For that interested, here is a gutting it out solution via generating functions.A Mea Culpa