“mcs” — 2018/6/6 — 13:43 — page 735 — #743

16 Generating Functions
Generating Functions are one of the most surprising and useful inventions in Dis-
crete Mathematics. Roughly speaking, generating functions transform problems
about sequences into problems about algebra. This is great because we’ve got piles
of algebraic rules. Thanks to generating functions, we can reduce problems about
sequences to checking properties of algebraic expressions. This will allow us to
use generating functions to solve all sorts of counting problems.
Several flavors of generating functions such as ordinary, exponential, and Dirich-
let come up regularly in combinatorial mathematics. In addition, Z-transforms,
which are closely related to ordinary generating functions, are important in control
theory and signal processing. But ordinary generating functions are enough to il-
lustrate the power of the idea, so we’ll stick to them. So from now on generating
function will mean the ordinary kind, and we will offer a taste of this large subject
by showing how generating functions can be used to solve certain kinds of count-
ing problems and how they can be used to find simple formulas for linear-recursive
functions.

16.1 Infinite Series

Informally, a generating function F .x/ is an infinite series

F .x/ D f0 C f1 x C f2 x 2 C f3 x 3 C


: (16.1)

We use the notation Œx n F .x/ for the coefficient of x n in the generating function
F .x/. That is, Œx n F .x/ WWD fn .
We can analyze the behavior of any sequence of numbers f0 ; f1 : : : fn : : : by
regarding the elements of the sequence as successive coefficients of a generating
function. It turns out that properties of complicated sequences that arise from
counting, recursive definition, and programming problems are easy to explain by
treating them as generating functions.
Generating functions can produce noteworthy insights even when the sequence
of coefficients is trivial. For example, let G.x/ be the generating function for the
infinite sequence of ones 1; 1; : : : , namely, the geometric series.

G.x/ WWD 1 C x C x 2 C


C x n C


: (16.2)

 “mcs” — 2018/6/6 — 13:43 — page 736 — #744

736 Chapter 16 Generating Functions

We’ll use typical generating function reasoning to derive a simple formula for
G.x/. The approach is actually an easy version of the perturbation method of
Section 14.1.2. Specifically,
G.x/ D 1 C x C x 2 C x 3 C


C x n C



xG.x/ D x x2 x3


xn



G.x/ xG.x/ D 1:
Solving for G.x/ gives
1
1 X
D G.x/ WWD xn: (16.3)
1 x
nD0
In other words,  
n 1
Œx  D1
1 x
Continuing with this approach yields a nice formula for
N.x/ WWD 1 C 2x C 3x 2 C


C .n C 1/x n C


: (16.4)
Specifically,
N.x/ D 1 C 2x C 3x 2 C 4x 3 C


C .n C 1/x n C



xN.x/ D x 2x 2 3x 3


nx n



N.x/ 2 3
xN.x/ D 1 C x C x C x C


C x n C



D G.x/:
Solving for N.x/ gives
1
1 G.x/ X
D D N.x/ WWD .n C 1/x n : (16.5)
.1 x/2 1 x
nD0
In other words,  
n 1
Œx  D n C 1:
.1 x/2

16.1.1 Never Mind Convergence

Equations (16.3) and (16.5) hold numerically only when jxj < 1, because both
generating function series diverge when jxj  1. But in the context of generat-
ing functions, we regard infinite series as formal algebraic objects. Equations such
as (16.3) and (16.5) define symbolic identities that hold for purely algebraic rea-
sons. In fact, good use can be made of generating functions determined by infinite
series that don’t converge anywhere (besides x D 0). We’ll explain this further in
Section 16.5 at the end of this chapter, but for now, take it on faith that you don’t
need to worry about convergence.
 “mcs” — 2018/6/6 — 13:43 — page 737 — #745

16.2. Counting with Generating Functions 737

16.2 Counting with Generating Functions

Generating functions are particularly useful for representing and counting the num-
ber of ways to select n things. For example, suppose there are two flavors of donuts,
chocolate and plain. Let dn be the number of ways to select n chocolate or plain
flavored donuts. dn D n C 1, because there are n C 1 such donut selections—all
chocolate, 1 plain and n 1 chocolate, 2 plain and n 2 chocolate,. . . , all plain.
We define a generating function D.x/ for counting these donut selections by letting
the coefficient of x n be dn . This gives us equation (16.5)
1
D.x/ D : (16.6)
.1 x/2

16.2.1 Apples and Bananas too

More generally, suppose we have two kinds of things—say, apples and bananas—
and some constraints on how many of each may be selected. Say there are an ways
to select n apples and bn ways to select n bananas. The generating function for
counting apples would be
X1
A.x/ WWD an x n ;
nD0
and for bananas would be
1
X
B.x/ WWD bn x n :
nD0
Now suppose apples come in baskets of 6, so there is no way to select 1 to 5
apples, one way to select 6 apples, no way to select 7, etc. In other words,
(
1 if n is a multiple of 6;
an D
0 otherwise:

In this case we would have

A.x/ D 1 C x 6 C x 12 C


C x 6n C



D 1 C y C y2 C


C yn C


where y D x 6 ;
1 1
D D :
1 y 1 x6
Let’s also suppose there are two kinds of bananas—red and yellow. Now, bn D
n C 1 by the same reasoning used to count selections of n chocolate and plain
 “mcs” — 2018/6/6 — 13:43 — page 738 — #746

738 Chapter 16 Generating Functions

donuts, and by (16.6) we have

1
B.x/ D :
.1 x/2
So how many ways are there to select a mix of n apples and bananas? First, we
decide how many apples to select. This can be any number k from 0 to n. We can
then select these apples in ak ways, by definition. This leaves n k bananas to
be selected, which by definition can be done in bn k ways. So the total number
of ways to select k apples and n k bananas is ak bn k . This means that the total
number of ways to select some size n mix of apples and bananas is

a0 bn C a1 bn 1 C a2 bn 2 C


C an b0 : (16.7)

16.2.2 Products of Generating Functions

Now here’s the cool connection between counting and generating functions: ex-
pression (16.7) is equal to the coefficient of x n in the product A.x/B.x/.
In other words, we’re claiming that

Rule (Product).

Œx n .A.x/
B.x// D a0 bn C a1 bn 1 C a2 bn 2 C


C an b0 : (16.8)

To explain the generating function Product Rule, we can think about evaluating
the product A.x/
B.x/ by using a table to identify all the cross-terms from the
product of the sums:

b0 x 0 b1 x 1 b2 x 2 b3 x 3 :::

a0 x 0 a0 b0 x 0 a0 b1 x 1 a0 b2 x 2 a0 b3 x 3 :::

a1 x 1 a1 b0 x 1 a1 b1 x 2 a1 b2 x 3 :::

a2 x 2 a2 b0 x 2 a2 b1 x 3 :::

a3 x 3 a3 b0 x 3 :::

::
: :::

In this layout, all the terms involving the same power of x lie on a 45-degree sloped
diagonal. So, the index-n diagonal contains all the x n -terms, and the coefficient of
 “mcs” — 2018/6/6 — 13:43 — page 739 — #747

16.2. Counting with Generating Functions 739

x n in the product A.x/
B.x/ is the sum of all the coefficients of the terms on this
diagonal, namely, (16.7). The sequence of coefficients of the product A.x/
B.x/
is called the convolution of the sequences .a0 ; a1 ; a2 ; : : : / and .b0 ; b1 ; b2 ; : : : /. In
addition to their algebraic role, convolutions of sequences play a prominent role in
signal processing and control theory.
This Product Rule provides the algebraic justification for the fact that a geometric
series equals 1=.1 x/ regardless of convergence. Specifically, the constant 1
describes the generating function

1 D 1 C 0x C 0x 2 C


C 0x n C


:

Likewise, the expression 1 x describes the generating function

1 x D 1 C . 1/x C 0x 2 C


C 0x n C


:

So for the series G.x/ whose coefficients are all equal to 1, the Product Rule implies
in a purely formal way that

.1 x/
G.x/ D 1 C 0x C 0x 2 C


C 0x n C


D 1:

In other words, under the Product Rule, the geometric series G.x/ is the multiplica-
tive inverse 1=.1 x/ of 1 x.
Similar reasoning justifies multiplying a generating function by a constant term
by term. That is, a special case of the Product Rule is the
Rule (Constant Factor). For any constant c and generating function F .x/

Œx n .c
F .x// D c
Œx n F .x/: (16.9)

16.2.3 The Convolution Rule

We can summarize the discussion above with the
Rule (Convolution). Let A.x/ be the generating function for selecting items from
a set A, and let B.x/ be the generating function for selecting items from a set B
disjoint from A. The generating function for selecting items from the union A [ B
is the product A.x/
B.x/.
The Rule depends on a precise definition of what “selecting items from the union
A [ B” means. Informally, the idea is that the restrictions on the selection of items
from sets A and B carry over to selecting items from A [ B.1
1 Formally, the Convolution Rule applies when there is a bijection between n-element selections

from A [ B and ordered pairs of selections from the sets A and B containing a total of n elements.
We think the informal statement is clear enough.
 “mcs” — 2018/6/6 — 13:43 — page 740 — #748

740 Chapter 16 Generating Functions

16.2.4 Counting Donuts with the Convolution Rule

We can use the Convolution Rule to derive in another way the generating function
D.x/ for the number of ways to select chocolate and plain donuts given in (16.6).
To begin, there is only one way to select exactly n chocolate donuts. That means
every coefficient of the generating function for selecting n chocolate donuts equals
one. So the generating function for chocolate donut selections is 1=.1 x/; likewise
for the generating function for selecting only plain donuts. Now by the Convolution
Rule, the generating function for the number of ways to select n donuts when both
chocolate and plain flavors are available is
1 1 1
D.x/ D
D :
1 x 1 x .1 x/2
So we have derived (16.6) without appeal to (16.5).
Our application of the Convolution Rule for two flavors carries right over to the
general case of k flavors; the generating function for selections of donuts when k
flavors are available is 1=.1 x/k . We already derived the formula for the number
of ways to select a n donuts when k flavors are available, namely, nC.kn 1/ from

Corollary 15.5.3. So we have

  !
1 n C .k 1/
Œx n  D : (16.10)
.1 x/k n

Extracting Coefficients from Maclaurin’s Theorem

We’ve used a donut-counting argument to derive the coefficients of 1=.1 x/k ,
but it’s instructive to derive this coefficient algebraically, which we can do using
Maclaurin’s Theorem:

Theorem 16.2.1 (Maclaurin’s Theorem).

f 00 .0/ 2 f 000 .0/ 3 f .n/ .0/ n

f .x/ D f .0/ C f 0 .0/x C x C x C


C x C


:
2Š 3Š nŠ

This theorem says that the nth coefficient of 1=.1 x/k is equal to its nth deriva-
tive evaluated at 0 and divided by nŠ. Computing the nth derivative turns out not to
be very difficult

dn 1 .kCn/
n
D k.k C 1/


.k C n 1/.1 x/
d x .1 x/k
 “mcs” — 2018/6/6 — 13:43 — page 741 — #749

16.2. Counting with Generating Functions 741

(see Problem 16.5), so

   n 
n 1 d 1 1
Œx  k
D n k
.0/
.1 x/ d x .1 x/ nŠ
k.k C 1/


.k C n 1/.1 0/ .kCn/
D
! nŠ
n C .k 1/
D :
n

In other words, instead of using the donut-counting formula (16.10) to find the
coefficients of x n , we could have used this algebraic argument and the Convolution
Rule to derive the donut-counting formula.

16.2.5 The Binomial Theorem from the Convolution Rule

The Convolution Rule also provides a new perspective on the Binomial Theo-
rem 15.6.4. Here’s how: first, work with the single-element set fa1 g. The gen-
erating function for the number of ways to select n different elements from this set
is simply 1 C x: we have 1 way to select zero elements, 1 way to select the one
element, and 0 ways to select more than one element. Similarly, the number of
ways to select n elements from any single-element set fai g has the same generating
function 1 C x. Now by the Convolution Rule, the generating function for choosing
a subset of n elements from the set fa1 ; a2 ; : : : ; am g is the product .1 C x/m of the
generating functions for selecting from each of the m one-element sets. Since
we
know that the number of ways to select n elements from a set of size m is m n , we
conclude that that !
m
Œx n .1 C x/m D ;
n
which is a restatement of the Binomial Theorem 15.6.4. Thus, we have proved
the Binomial Theorem without having to analyze the expansion of the expression
.1 C x/m into a sum of products.
These examples of counting donuts and deriving the binomial coefficients illus-
trate where generating functions get their power:

Generating functions can allow counting problems to be solved by algebraic

manipulation, and conversely, they can allow algebraic identities to be derived by
counting techniques.
 “mcs” — 2018/6/6 — 13:43 — page 742 — #750

742 Chapter 16 Generating Functions

16.2.6 An Absurd Counting Problem

So far everything we’ve done with generating functions we could have done another
way. But here is an absurd counting problem—really over the top! In how many
ways can we fill a bag with n fruits subject to the following constraints?

 The number of apples must be even.

 The number of bananas must be a multiple of 5.
 There can be at most four oranges.
 There can be at most one pear.

For example, there are 7 ways to form a bag with 6 fruits:

Apples 6 4 4 2 2 0 0
Bananas 0 0 0 0 0 5 5
Oranges 0 2 1 4 3 1 0
Pears 0 0 1 0 1 0 1
These constraints are so complicated that getting a nice answer may seem impossi-
ble. But let’s see what generating functions reveal.
First, we’ll construct a generating function for choosing apples. We can choose a
set of 0 apples in one way, a set of 1 apple in zero ways (since the number of apples
must be even), a set of 2 apples in one way, a set of 3 apples in zero ways, and so
forth. So, we have:
1
A.x/ D 1 C x 2 C x 4 C x 6 C


D
1 x2
Similarly, the generating function for choosing bananas is:
1
B.x/ D 1 C x 5 C x 10 C x 15 C


D
1 x5
Now, we can choose a set of 0 oranges in one way, a set of 1 orange in one way,
and so on. However, we cannot choose more than four oranges, so we have the
generating function:
1 x5
O.x/ D 1 C x C x 2 C x 3 C x 4 D :
1 x
Here the right-hand expression is simply the formula (14.2) for a finite geometric
sum. Finally, we can choose only zero or one pear, so we have:

P .x/ D 1 C x
 “mcs” — 2018/6/6 — 13:43 — page 743 — #751

16.3. Partial Fractions 743

The Convolution Rule says that the generating function for choosing from among
all four kinds of fruit is:
1 1 1 x5
A.x/B.x/O.x/P .x/ D .1 C x/
1 x2 1 x5 1 x
1
D
.1 x/2
D 1 C 2x C 3x 2 C 4x 3 C

Almost everything cancels! We’re left with 1=.1 x/2 , which we found a power
series for earlier: the coefficient of x n is simply n C 1. Thus, the number of ways to
form a bag of n fruits is just n C 1. This is consistent with the example we worked
out, since there were 7 different fruit bags containing 6 fruits. Amazing!
This example was contrived to seem complicated at first sight so we could high-
light the power of counting with generating functions. But the simple suggests that
there ought to be an elementary derivation without resort to generating functions,
and indeed there is (Problem 16.8).

16.3 Partial Fractions

We got a simple solution to the seemingly impossible counting problem of Sec-
tion 16.2.6 because its generating function simplified to the expression 1=.1 x/2 ,
whose power series coefficients we already knew. This problem was set up so the
answer would work out neatly, but other problems are not so neat. To solve more
general problems using generating functions, we need ways to find power series co-
efficients for generating functions given as formulas. Maclaurin’s Theorem 16.2.1
is a very general method for finding coefficients, but it only applies when formulas
for repeated derivatives can be found, which isn’t often. However, there is an auto-
matic way to find the power series coefficients for any formula that is a quotient of
polynomials, namely, the method of partial fractions from elementary calculus.
The partial fraction method is based on the fact that quotients of polynomials
can be expressed as sums of terms whose power series coefficients have nice for-
mulas. For example when the denominator polynomial has distinct nonzero roots,
the method rests on
Lemma 16.3.1. Let p.x/ be a polynomial of degree less than n and let ˛1 ; : : : ; ˛n
be distinct, nonzero numbers. Then there are constants c1 ; : : : ; cn such that
p.x/ c1 c2 cn
D C C


C :
.1 ˛1 x/.1 ˛2 x/


.1 ˛n x/ 1 ˛1 x 1 ˛2 x 1 ˛n x
 “mcs” — 2018/6/6 — 13:43 — page 744 — #752

744 Chapter 16 Generating Functions

Let’s illustrate the use of Lemma 16.3.1 by finding the power series coefficients
for the function
x
R.x/ WWD :
1 x x2
We can use the quadratic formula to find the roots r1 ; r2 of the denominator 1
x x2. p p
1 5 1C 5
r1 D ; r2 D :
2 2
So
1 x x 2 D .x r1 /.x r2 / D r1 r2 .1 x=r1 /.1 x=r2 /:
With a little algebra, we find that
x
R.x/ D
.1 ˛1 x/.1 ˛2 x/
where
p
1C 5
˛1 D
2p
1 5
˛2 D :
2
Next we find c1 and c2 which satisfy:
x c1 c2
D C (16.11)
.1 ˛1 x/.1 ˛2 x/ 1 ˛1 x 1 ˛2 x
In general, we can do this by plugging in a couple of values for x to generate two
linear equations in c1 and c2 and then solve the equations for c1 and c2 . A simpler
approach in this case comes from multiplying both sides of (16.11) by the left-hand
denominator to get
x D c1 .1 ˛2 x/ C c2 .1 ˛1 x/:
Now letting x D 1=˛2 we obtain

1=˛2 1 1
c2 D D D p ;
1 ˛1 =˛2 ˛2 ˛1 5
and similarly, letting x D 1=˛1 we obtain
1
c1 D p :
5
 “mcs” — 2018/6/6 — 13:43 — page 745 — #753

16.3. Partial Fractions 745

Plugging these values for c1 ; c2 into equation (16.11) finally gives the partial frac-
tion expansion
 
x 1 1 1
R.x/ D Dp
1 x x2 5 1 ˛1 x 1 ˛2 x
Each term in the partial fractions expansion has a simple power series given by the
geometric sum formula:
1
D 1 C ˛1 x C ˛12 x 2 C



1 ˛1 x
1
D 1 C ˛2 x C ˛22 x 2 C



1 ˛2 x
Substituting in these series gives a power series for the generating function:
1
R.x/ D p .1 C ˛1 x C ˛12 x 2 C


/ .1 C ˛2 x C ˛22 x 2 C


/ ;


5
so
˛n ˛n
Œx n R.x/ D 1p 2
5
p !n p !n !
1 1C 5 1 5
Dp (16.12)
5 2 2

16.3.1 Partial Fractions with Repeated Roots

Lemma 16.3.1 generalizes to the case when the denominator polynomial has a re-
peated nonzero root with multiplicity m by expanding the quotient into a sum a
terms of the form
c
.1 ˛x/k
where ˛ is the reciprocal of the root and k  m. A formula for the coefficients of
such a term follows from the donut formula (16.10).
  !
n c n n C .k 1/
Œx  D c˛ : (16.13)
.1 ˛x/k n
When ˛ D 1, this follows from the donut formula (16.10) and termwise multipli-
cation by the constant c. The case for arbitrary ˛ follows by substituting ˛x for x
in the power series; this changes x n into .˛x/n and so has the effect of multiplying
the coefficient of x n by ˛ n .2
2 In other words,
Œx n F .˛x/ D ˛ n
Œx n F .x/:
 “mcs” — 2018/6/6 — 13:43 — page 746 — #754

746 Chapter 16 Generating Functions

16.4 Solving Linear Recurrences

16.4.1 A Generating Function for the Fibonacci Numbers
The Fibonacci numbers f0 ; f1 ; : : : ; fn ; : : : are defined recursively as follows:

f0 WWD 0
f1 WWD 1
fn D WWDfn 1 C fn 2 (for n  2):

Generating functions will now allow us to derive an astonishing closed formula for
fn .
Let F .x/ be the generating function for the sequence of Fibonacci numbers, that
is,
F .x/ WWD f0 C f1 x C f2 x 2 C


fn x n C


:
Reasoning as we did at the start of this chapter to derive the formula for a geometric
series, we have

F .x/ D f0 C f1 x C f2 x 2 C


C fn x n C


:
xF .x/ D f0 x f1 x 2


fn 1 x n C


:
x 2 F .x/ D f0 x 2


fn 2 x n C


:
F .x/.1 x x2/ D f0 C .f1 2
f0 /x C 0x C


C 0x n C


:
D 0 C 1x C 0x 2 D x;
so
x
F .x/ D :
1 x x2
But F .x/ is the same as the function we used to illustrate the partial fraction method
for finding coefficients in Section 16.3. So by equation (16.12), we arrive at what
is called Binet’s formula:
p !n p !n !
1 1C 5 1 5
fn D p (16.14)
5 2 2

Binet’s formula for Fibonacci numbers is astonishing and maybe scary. It’s not
even obvious that the expression on the right-hand side (16.14) is an integer. But
the formula is very useful. For example, it provides—via the repeated squaring
method—a much more efficient way to compute Fibonacci numbers than crunch-
ing through the recurrence. It also make explicit the exponential growth of these
numbers.
 “mcs” — 2018/6/6 — 13:43 — page 747 — #755

16.4. Solving Linear Recurrences 747

Figure 16.1 The initial configuration of the disks in the Towers of Hanoi problem.

16.4.2 The Towers of Hanoi

According to legend, there is a temple in Hanoi with three posts and 64 gold disks
of different sizes. Each disk has a hole through the center so that it fits on a post.
In the misty past, all the disks were on the first post, with the largest on the bottom
and the smallest on top, as shown in Figure 16.1.
Monks in the temple have labored through the years since to move all the disks
to one of the other two posts according to the following rules:
 The only permitted action is removing the top disk from one post and drop-
ping it onto another post.

 A larger disk can never lie above a smaller disk on any post.
So, for example, picking up the whole stack of disks at once and dropping them on
another post is illegal. That’s good, because the legend says that when the monks
complete the puzzle, the world will end!
To clarify the problem, suppose there were only 3 gold disks instead of 64. Then
the puzzle could be solved in 7 steps as shown in Figure 16.2.
The questions we must answer are, “Given sufficient time, can the monks suc-
ceed?” If so, “How long until the world ends?” And, most importantly, “Will this
happen before the final exam?”

A Recursive Solution
The Towers of Hanoi problem can be solved recursively. As we describe the pro-
cedure, we’ll also analyze the minimum number tn of steps required to solve the
n-disk problem. For example, some experimentation shows that t1 D 1 and t2 D 3.
The procedure illustrated above uses 7 steps, which shows that t3 is at most 7.
The recursive solution has three stages, which are described below and illustrated
in Figure 16.3. For clarity, the largest disk is shaded in the figures.

Stage 1. Move the top n 1 disks from the first post to the second using the solution
for n 1 disks. This can be done in tn 1 steps.
 “mcs” — 2018/6/6 — 13:43 — page 748 — #756

748 Chapter 16 Generating Functions

Figure 16.2 The 7-step solution to the Towers of Hanoi problem when there are
n D 3 disks.

Figure 16.3 A recursive solution to the Towers of Hanoi problem.

 “mcs” — 2018/6/6 — 13:43 — page 749 — #757

16.4. Solving Linear Recurrences 749

Stage 2. Move the largest disk from the first post to the third post. This takes just
1 step.
Stage 3. Move the n 1 disks from the second post to the third post, again using
the solution for n 1 disks. This can also be done in tn 1 steps.
This algorithm shows that tn , the minimum number of steps required to move n
disks to a different post, is at most tn 1 C 1 C tn 1 D 2tn 1 C 1. We can use this
fact to upper bound the number of operations required to move towers of various
heights:
t3  2
t2 C 1 D 7
t4  2
t3 C 1  15
Continuing in this way, we could eventually compute an upper bound on t64 , the
number of steps required to move 64 disks. So this algorithm answers our first
question: given sufficient time, the monks can finish their task and end the world.
This is a shame. After all that effort, they’d probably want to smack a few high-fives
and go out for burgers and ice cream, but nope—world’s over.

Finding a Recurrence
We cannot yet compute the exact number of steps that the monks need to move the
64 disks, only an upper bound. Perhaps, having pondered the problem since the
beginning of time, the monks have devised a better algorithm.
Lucky for us, there is no better algorithm. Here’s why: at some step, the monks
must move the largest disk from the first post to a different post. For this to happen,
the n 1 smaller disks must all be stacked out of the way on the only remaining
post. Arranging the n 1 smaller disks this way requires at least tn 1 moves. After
the largest disk is moved, at least another tn 1 moves are required to pile the n 1
smaller disks on top.
This argument shows that the number of steps required is at least 2tn 1 C 1.
Since we gave an algorithm using exactly that number of steps, we can now write
an expression for tn , the number of moves required to complete the Towers of Hanoi
problem with n disks:
t0 D 0
tn D 2tn 1 C1 (for n  1):
Solving the Recurrence
We can now find a formula for tn using generating functions. Let T .x/ be the
generating function for the tn ’s, that is,
T .x/ WWD t0 C t1 x C t2 x 2 C


tn x n C


:
 “mcs” — 2018/6/6 — 13:43 — page 750 — #758

750 Chapter 16 Generating Functions

Reasoning as we did for the Fibonacci recurrence, we have

T .x/ D t0 C t1 x C


C tn x n C



2xT .x/ D 2t0 x


2tn 1 x n C



1=.1 x/ D 1 1x


1x n C



T .x/.1 2x/ 1=.1 x/ D t0 1 C 0x C


C 0x n C



D 1;
so
1 x
T .x/.1 2x/ D 1D ;
1 x 1 x
and
x
T .x/ D :
.1 2x/.1 x/
Using partial fractions,
x c1 c2
D C
.1 2x/.1 x/ 1 2x 1 x
for some constants c1 ; c2 . Now multiplying both sides by the left hand denominator
gives
x D c1 .1 x/ C c2 .1 2x/:
Substituting 1=2 for x yields c1 D 1 and substituting 1 for x yields c2 D 1,
which gives
1 1
T .x/ D :
1 2x 1 x
Finally we can read off the simple formula for the numbers of steps needed to move
a stack of n disks:
   
n n 1 n 1
tn D Œx T .x/ D Œx  Œx  D 2n 1:
1 2x 1 x

16.4.3 Solving General Linear Recurrences

An equation of the form

f .n/ D c1 f .n 1/ C c2 f .n 2/ C


C cd f .n d / C h.n/ (16.15)

for constants ci 2 C is called a degree d linear recurrence with inhomogeneous

term h.n/.
The methods above can be used to solve linear recurrences with a large class of
inhomogeneous terms. In particular, when the inhomogeneous term itself has a gen-
erating function that can be expressed as a quotient of polynomials, the approach
 “mcs” — 2018/6/6 — 13:43 — page 751 — #759

16.5. Formal Power Series 751

used above to derive generating functions for the Fibonacci and Tower of Hanoi
examples carries over to yield a quotient of polynomials that defines the generating
function f .0/ C f .1/x C f .2/x 2 C


. Then partial fractions can be used to find
a formula for f .n/ that is a linear combination of terms of the form nk ˛ n where k
is a nonnegative integer  d and ˛ is the reciprocal of a root of the denominator
polynomial. For example, see Problems 16.14, 16.15, 16.18, and 16.19.

16.5 Formal Power Series

16.5.1 Divergent Generating Functions
Let F .x/ be the generating function for nŠ, that is,

F .x/ WWD 1 C 1x C 2x 2 C


C nŠx n C


:

Because x n D o.nŠ/ for all x ¤ 0, this generating function converges only at

x D 0.3
Next, let H.x/ be the generating function for n
nŠ, that is,

H.x/ WWD 0 C 1x C 4x 2 C


C n
nŠx n C


:

Again, H.x/ converges only for x D 0, so H.x/ and F .x/ describe the same,
trivial, partial function on the reals.
On the other hand, F .x/ and H.x/ have different coefficients for all powers of
x greater than 1, and we can usefully distinguish them as formal, symbolic objects.
To illustrate this, note than by subtracting 1 from F .x/ and then dividing each
of the remaining terms by x, we get a series where the coefficient if x n is .n C 1/Š.
That is  
n F .x/ 1
Œx  D .n C 1/Š : (16.16)
x
Now a little further formal reasoning about F .x/ and H.x/ will allow us to
deduce the following identity for nŠ:4
n
X
nŠ D 1 C .i 1/
.i 1/Š (16.17)
i D1
3 This
section is based on an example from “Use of everywhere divergent generating function,”
mathoverflow, response 8,147 by Aaron Meyerowitz, Nov. 12, 2010.
4 A combinatorial proof of (16.17) is given in Problem 15.72
 “mcs” — 2018/6/6 — 13:43 — page 752 — #760

752 Chapter 16 Generating Functions

To prove this identity, note that from (16.16), we have

 
n n F .x/ 1
Œx H.x/ WWD n
nŠ D .n C 1/Š nŠ D Œx  Œx n F .x/:
x

In other words,
F .x/ 1
H.x/ D F .x/; (16.18)
x
Solving (16.18) for F .x/, we get

xH.x/ C 1
F .x/ D : (16.19)
1 x
But Œx n .xH.x/ C 1/ is .n 1/
.n 1/Š for n  1 and is 1 for n D 0, so by the
convolution formula,
  n
n xH.x/ C 1 X
Œx  D1C .i 1/
.i 1/Š :
1 x
i D1

The identity (16.17) now follows immediately from (16.19).

16.5.2 The Ring of Power Series

So why don’t we have to worry about series whose radius of convergence is zero,
and how do we justify the kind of manipulation in the previous section to derive
the formula (16.19)? The answer comes from thinking abstractly about infinite
sequences of numbers and operations that can be performed on them.
For example, one basic operation combining two infinite sequences is adding
them coordinatewise. That is, if we let

G WWD .g0 ; g1 ; g2 ; : : : /;
H WWD .h0 ; h1 ; h2 ; : : : /;

then we can define the sequence sum ˚ by the rule:

G ˚ H WWD .g0 C h0 ; g1 C h1 ; : : : ; gn C hn ; : : : /:

Another basic operation is sequence multiplication ˝ defined by the convolution

rule (not coordinatewise):
n
!
X
G ˝ H WWD g0 C h0 ; g0 h1 C g1 h0 ; : : : ; gi hn i ; : : : :
i D0
 “mcs” — 2018/6/6 — 13:43 — page 753 — #761

16.5. Formal Power Series 753

These operations on infinite sequences have lots of nice properties. For example,
it’s easy to check that sequence addition and multiplication are commutative:

G ˚ H D H ˚ G;
G ˝ H D H ˝ G:

If we let

Z WWD .0; 0; 0; : : : /;
I WWD .1; 0; 0; : : : ; 0; : : : /;

then it’s equally easy to check that Z acts like a zero for sequences and I acts like
the number one:

Z ˚ G D G;
Z ˝ G D Z; (16.20)
I ˝ G D G:

Now if we define
G WWD . g0 ; g1 ; g2 ; : : : /
then
G ˚ . G/ D Z:
In fact, the operations ˚ and ˝ satisfy all the commutative ring axioms described
in Section 9.7.1. The set of infinite sequences of numbers together with these op-
erations is called the ring of formal power series over these numbers.5
A sequence H is the reciprocal of a sequence G when

G ˝ H D I:

A reciprocal of G is also called a multiplicative inverse or simply an “inverse”

of G. The ring axioms imply that if there is a reciprocal, it is unique (see Prob-
lem 9.33), so the suggestive notation 1=G can be used unambiguously to denote
this reciprocal, if it exists. For example, letting

J WWD .1; 1; 0; 0; : : : ; 0; : : : /
K WWD .1; 1; 1; 1; : : : ; 1; : : : /;

the definition of ˝ implies that J ˝ K D I , and so K D 1=J and J D 1=K.

5 Theelements in the sequences may be the real numbers, complex numbers, or, more generally,
may be the elements from any given commutative ring.
 “mcs” — 2018/6/6 — 13:43 — page 754 — #762

754 Chapter 16 Generating Functions

In the ring of formal power series, equation (16.20) implies that the zero se-
quence Z has no inverse, so 1=Z is undefined—just as the expression 1/0 is unde-
fined over the real numbers or the ring Zn of Section 9.7.1. It’s not hard to verify
that a series has an inverse iff its initial element is nonzero (see Problem 16.25).
Now we can explain the proper way to understand a generating function defini-
tion
X1
G.x/ WWD gn x n :
nD0

It simply means that G.x/ really refers to its infinite sequence of coefficients .g0 ; g1 ; : : : /
in the ring of formal power series. The simple expression x can be understood as
referring to the sequence

X WWD .0; 1; 0; 0; : : : ; 0; : : : /:

Likewise, 1 x abbreviates the sequence J above, and the familiar equation

1
D 1 C x C x2 C x3 C


(16.21)
1 x
can be understood as a way of restating the assertion that K is 1=J . In other words,
the powers of the variable x just serve as a place holders—and as reminders of the
definition of convolution. The equation (16.21) has nothing to do with the values
of x or the convergence of the series. Rather, it is stating a property that holds in
the ring of formal power series. The reasoning about the divergent series in the
previous section is completely justified as properties of formal power series.

16.6 References
[50], [25], [10] [20]

Problems for Section 16.1

Practice Problems
Problem 16.1.
The notation Œx n F .x/ refers to the coefficient of x n in the generating function
 “mcs” — 2018/6/6 — 13:43 — page 755 — #763

16.6. References 755

F .x/. Indicate all the expressions below that equal Œx n 4xG.x/ (most of them do).

4Œx n xG.x/ 4xŒx n G.x/ Œx n 1 4G.x/

.Œx n 4x/
Œx n G.x/ .Œx4x/
Œx n xG.x/ Œx nC1 4x 2 G.x/

Problem 16.2.
What is the coefficient of x n in the generating function
1Cx
‹
.1 x/2

Problems for Section 16.2

Practice Problems
Problem 16.3.
You would like to buy a bouquet of flowers. You find an online service that will
make bouquets of lilies, roses and tulips, subject to the following constraints:

 there must be at most 1 lily,

 there must be an odd number of tulips,

 there must be at least two roses.

Example: A bouquet of no lilies, 3 tulips, and 5 roses satisfies the constraints.

Express B.x/, the generating function for the number of ways to select a bouquet
of n flowers, as a quotient of polynomials (or products of polynomials). You do not
need to simplify this expression.

Problem 16.4.
Write a formula for the generating function whose successive coefficients are given
by the sequence:
(a) 0, 0, 1, 1, 1,. . .

(b) 1, 1, 0, 0, 0,. . .
 “mcs” — 2018/6/6 — 13:43 — page 756 — #764

756 Chapter 16 Generating Functions

(c) 1, 0, 1, 0, 1, 0, 1,. . .

(d) 1, 4, 6, 4, 1, 0, 0, 0,. . .

(e) 1, 2, 3, 4, 5,. . .

(f) 1, 4, 9, 16, 25,. . .

(g) 1, 1, 1/2, 1/6, 1/24, 1/120,. . .

Class Problems
Problem 16.5.
Let A.x/ D 1 n
P
nD0 an x . Then it’s easy to check that

A.n/ .0/
an D ;
nŠ

where A.n/ is the nth derivative of A. Use this fact (which you may assume) instead
of the Convolution Counting Principle 16.2.3, to prove that
1
!
1 X nCk 1 n
D x :
.1 x/k k 1
nD0

So if we didn’t already know the Bookkeeper Rule from Section 15.6, we could
have proved it from this calculation and the Convolution Rule for generating func-
tions.

Problem 16.6. (a) Let

x2 C x
S.x/ WWD :
.1 x/3
What is the coefficient of x n in the generating function series for S.x/?

(b) Explain why S.x/=.1 x/ is the generating function for P the sums of squares.
That is, the coefficient of x n in the series for S.x/=.1 x/ is nkD1 k 2 .

(c) Use the previous parts to prove that

n
X n.n C 1/.2n C 1/
k2 D :
6
kD1
 “mcs” — 2018/6/6 — 13:43 — page 757 — #765

16.6. References 757

Homework Problems
Problem 16.7.
We will use generating functions to determine how many ways there are to use
pennies, nickels, dimes, quarters, and half-dollars to give n cents change.
(a) Write the generating function P .x/ for the number of ways to use only pennies
to make n cents.

(b) Write the generating function N.x/ for the number of ways to use only nickels
to make n cents.

(c) Write the generating function for the number of ways to use only nickels and
pennies to change n cents.

(d) Write the generating function for the number of ways to use pennies, nickels,
dimes, quarters, and half-dollars to give n cents change.

(e) Explain how to use this function to find out how many ways are there to change
50 cents; you do not have to provide the answer or actually carry out the process.

Problem 16.8.
The answer derived by generating functions for the “absurd” counting problem
in Section 16.2.6 is not impossibly complicated at all. Describe a direct simple
counting argument to derive this answer without using generating functions.

Problems for Section 16.3

Class Problems
Problem 16.9.
We are interested in generating functions for the number of different ways to com-
pose a bag of n donuts subject to various restrictions. For each of the restrictions in
parts (a)-(e) below, find a closed form for the corresponding generating function.
(a) All the donuts are chocolate and there are at least 3.

(b) All the donuts are glazed and there are at most 2.

(c) All the donuts are coconut and there are exactly 2 or there are none.

(d) All the donuts are plain and their number is a multiple of 4.
 “mcs” — 2018/6/6 — 13:43 — page 758 — #766

758 Chapter 16 Generating Functions

(e) The donuts must be chocolate, glazed, coconut, or plain with the numbers of
each flavor subject to the constraints above.

(f) Now find a closed form for the number of ways to select n donuts subject to
the above constraints.

Homework Problems
Problem 16.10.
Miss McGillicuddy never goes outside without a collection of pets. In particular:

 She brings a positive number of songbirds, which always come in pairs.

 She may or may not bring her alligator, Freddy.

 She brings at least 2 cats.

 She brings two or more chihuahuas and labradors leashed together in a line.

Let Pn denote the number of different collections of n pets that can accompany
her, where we regard chihuahuas and labradors leashed in different orders as dif-
ferent collections.
For example, P6 D 4 since there are 4 possible collections of 6 pets:

 2 songbirds, 2 cats, 2 chihuahuas leashed in line

 2 songbirds, 2 cats, 2 labradors leashed in line

 2 songbirds, 2 cats, a labrador leashed behind a chihuahua

 2 songbirds, 2 cats, a chihuahua leashed behind a labrador

(a) Let
P .x/ WWD P0 C P1 x C P2 x 2 C P3 x 3 C



be the generating function for the number of Miss McGillicuddy’s pet collections.
Verify that
4x 6
P .x/ D :
.1 x/2 .1 2x/
(b) Find a closed form expression for Pn .
 “mcs” — 2018/6/6 — 13:43 — page 759 — #767

16.6. References 759

Exam Problems
Problem 16.11.
T-Pain is planning an epic boat trip and he needs to decide what to bring with him.

 He must bring some burgers, but they only come in packs of 6.

 He and his two friends can’t decide whether they want to dress formally or
casually. He’ll either bring 0 pairs of flip flops or 3 pairs.

 He doesn’t have very much room in his suitcase for towels, so he can bring
at most 2.

 In order for the boat trip to be truly epic, he has to bring at least 1 nautical-
themed pashmina afghan.

(a) Let B.x/ be the generating function for the number of ways to bring n burgers,
F .x/ for the number of ways to bring n pairs of flip flops, T .x/ for towels, and
A.x/ for Afghans. Write simple formulas for each of these.

(b) Let gn be the the number of different ways for T-Pain to bring n items (burg-
P1towels, nand/or afghans) on his boat trip. Let G.x/ be the
ers, pairs of flip flops,
generating function nD0 gn x . Verify that

x7
G.x/ D :
.1 x/2

(c) Find a simple formula for gn .

Problem 16.12.
Every day in the life of Dangerous Dan is a potential disaster:

 Dan may or may not spill his breakfast cereal on his computer keyboard.

 Dan may or may not fall down the front steps on his way out the door.

 Dan stubs his toe zero or more times.

 Dan blurts something foolish an even number of times.

 “mcs” — 2018/6/6 — 13:43 — page 760 — #768

760 Chapter 16 Generating Functions

Let Tn be the number of different combinations of n mishaps Dan can suffer in one
day. For example, T3 D 7, because there are seven possible combinations of three
mishaps:
spills 0 1 0 1 1 0 0
falls 0 0 1 1 0 1 0
stubs 3 2 2 1 0 0 1
blurts 0 0 0 0 2 2 2
(a) Express the generating function

T .x/ WWD T0 C T1 x C T2 x 2 C

as a quotient of polynomials.

(b) Put integers in the boxes that make this equation true:

g.x/ D C
1 x .1 x/2

(c) Write a closed-form expression for Tn :

Problems for Section 16.4

Practice Problems
Problem 16.13.
Let b, c, a0 , a1 , a2 ,. . . be real numbers such that

an D b.an 1/ Cc
for n  1.
Let G.x/ be the generating function for this sequence.
(a) Express the coefficient of x n for n  1 in the series expansion of bxG.x/ in
terms of b and ai for suitable i .

(b) What is the coefficient of x n for n  1 in the series expansion of cx=.1 x/?
 “mcs” — 2018/6/6 — 13:43 — page 761 — #769

16.6. References 761

(c) Use the previous results to Exhibit a very simple expression for G.x/ bxG.x/
cx=.1 x/.

(d) Using the method of partial fractions, we can find real numbers d and e such
that
G.x/ D d=L.x/ C e=M.x/:
What are L.x/ and M.x/?

Class Problems
Problem 16.14.
The famous mathematician, Fibonacci, has decided to start a rabbit farm to fill up
his time while he’s not making new sequences to torment future college students.
Fibonacci starts his farm on month zero (being a mathematician), and at the start of
month one he receives his first pair of rabbits. Each pair of rabbits takes a month
to mature, and after that breeds to produce one new pair of rabbits each month.
Fibonacci decides that in order never to run out of rabbits or money, every time a
batch of new rabbits is born, he’ll sell a number of newborn pairs equal to the total
number of pairs he had three months earlier. Fibonacci is convinced that this way
he’ll never run out of stock.
(a) Define the number rn of pairs of rabbits Fibonacci has in month n, using a
recurrence relation. That is, define rn in terms of various ri where i < n.

(b) Let R.x/ be the generating function for rabbit pairs,

R.x/ WWD r0 C r1 x C r2 x 2 C

Express R.x/ as a quotient of polynomials.

(c) Find a partial fraction decomposition of the generating function R.x/.

(d) Finally, use the partial fraction decomposition to come up with a closed form
expression for the number of pairs of rabbits Fibonacci has on his farm on month
n.

Problem 16.15.
Less well-known than the Towers of Hanoi—but no less fascinating—are the Tow-
ers of Sheboygan. As in Hanoi, the puzzle in Sheboygan involves 3 posts and n
rings of different sizes. The rings are placed on post #1 in order of size with the
smallest ring on top and largest on bottom.
 “mcs” — 2018/6/6 — 13:43 — page 762 — #770

762 Chapter 16 Generating Functions

The objective is to transfer all n rings to post #2 via a sequence of moves. As

in the Hanoi version, a move consists of removing the top ring from one post and
dropping it onto another post with the restriction that a larger ring can never lie
above a smaller ring. But unlike Hanoi, a local ordinance requires that a ring can
only be moved from post #1 to post #2, from post #2 to post #3, or from post
#3 to post #1. Thus, for example, moving a ring directly from post #1 to post #3 is
not permitted.
(a) One procedure that solves the Sheboygan puzzle is defined recursively: to
move an initial stack of n rings to the next post, move the top stack of n 1 rings
to the furthest post by moving it to the next post two times, then move the big, nth
ring to the next post, and finally move the top stack another two times to land on
top of the big ring. Let sn be the number of moves that this procedure uses. Write
a simple linear recurrence for sn .

(b) Let S.x/ be the generating function for the sequence hs0 ; s1 ; s2 ; : : : i. Care-
fully show that
x
S.x/ D :
.1 x/.1 4x/
(c) Give a simple formula for sn .

(d) A better (indeed optimal, but we won’t prove this) procedure to solve the Tow-
ers of Sheboygan puzzle can be defined in terms of two mutually recursive proce-
dures, procedure P1 .n/ for moving a stack of n rings 1 pole forward, and P2 .n/
for moving a stack of n rings 2 poles forward. This is trivial for n D 0. For n > 0,
define:
P1 .n/: Apply P2 .n 1/ to move the top n 1 rings two poles forward to the third
pole. Then move the remaining big ring once to land on the second pole. Then
apply P2 .n 1/ again to move the stack of n 1 rings two poles forward from the
third pole to land on top of the big ring.
P2 .n/: Apply P2 .n 1/ to move the top n 1 rings two poles forward to land on
the third pole. Then move the remaining big ring to the second pole. Then apply
P1 .n 1/ to move the stack of n 1 rings one pole forward to land on the first
pole. Now move the big ring 1 pole forward again to land on the third pole. Finally,
apply P2 .n 1/ again to move the stack of n 1 rings two poles forward to land
on the big ring.
Let tn be the number of moves needed to solve the Sheboygan puzzle using proce-
dure P1 .n/. Show that
tn D 2tn 1 C 2tn 2 C 3; (16.22)
for n > 1.
 “mcs” — 2018/6/6 — 13:43 — page 763 — #771

16.6. References 763

Hint: Let un be the number of moves used by procedure P2 .n/. Express each of tn
and un as linear combinations of tn 1 and un 1 and solve for tn .

(e) Derive values a; b; c; ˛; ˇ such that

tn D a˛ n C bˇ n C c:
Conclude that tn D o.sn /.

Homework Problems
Problem 16.16.
Taking derivatives of generating functions is another useful operation. This is done
termwise, that is, if
F .x/ D f0 C f1 x C f2 x 2 C f3 x 3 C


;
then
F 0 .x/ WWD f1 C 2f2 x C 3f3 x 2 C


:
For example,
 0
1 1
D D 1 C 2x C 3x 2 C



.1 x/2 .1 x/
so
x
H.x/ WWD D 0 C 1x C 2x 2 C 3x 3 C



.1 x/2
is the generating function for the sequence of nonnegative integers. Therefore
1Cx
D H 0 .x/ D 1 C 22 x C 32 x 2 C 42 x 3 C


;
.1 x/3
so
x2 C x
D xH 0 .x/ D 0 C 1x C 22 x 2 C 32 x 3 C


C n2 x n C



.1 x/3
is the generating function for the nonnegative integer squares.
(a) Prove that for all k 2 N, the generating function for the nonnegative integer
kth powers is a quotient of polynomials in x. That is, for all k 2 N there are
polynomials Rk .x/ and Sk .x/ such that
 
n Rk .x/
Œx  D nk : (16.23)
Sk .x/

Hint: Observe that the derivative of a quotient of polynomials is also a quotient of

polynomials. It is not necessary to work out explicit formulas for Rk and Sk to
prove this part.
 “mcs” — 2018/6/6 — 13:43 — page 764 — #772

764 Chapter 16 Generating Functions

(b) Conclude that if f .n/ is a function on the nonnegative integers defined recur-
sively in the form
f .n/ D af .n 1/ C bf .n 2/ C cf .n 3/ C p.n/˛ n
where the a; b; c; ˛ 2 C and p is a polynomial with complex coefficients, then
the generating function for the sequence f .0/; f .1/; f .2/; : : : will be a quotient of
polynomials in x, and hence there is a closed form expression for f .n/.
Hint: Consider
Rk .˛x/
Sk .˛x/

Problem 16.17.
Generating functions provide an interesting way to count the number of strings of
matched brackets. To do this, we’ll use a description of these strings as the set
GoodCount of strings of brackets with a good count.6
Namely, one precise way to determine if a string is matched is to start with 0
and read the string from left to right, adding 1 to the count for each left bracket
and subtracting 1 from the count for each right bracket. For example, here are the
counts for the two strings above
[ ] ] [ [ [ [ [ ] ] ] ]
0 1 0 1 0 1 2 3 4 3 2 1 0

[ [ [ ] ] [ ] ] [ ]
0 1 2 3 2 1 2 1 0 1 0
A string has a good count if its running count never goes negative and ends with 0.
So the second string above has a good count, but the first one does not because its
count went negative at the third step.
Definition. Let
GoodCount WWD fs 2 f] ; [ g j s has a good countg:
The matched strings can now be characterized precisely as this set of strings with
good counts.
Let cn be the number of strings in GoodCount with exactly n left brackets, and
let C.x/ be the generating function for these numbers:
C.x/ WWD c0 C c1 x C c2 x 2 C


:
6 Problem 7.21 also examines these strings.
 “mcs” — 2018/6/6 — 13:43 — page 765 — #773

16.6. References 765

(a) The wrap of a string s is the string, [ s ] , that starts with a left bracket fol-
lowed by the characters of s, and then ends with a right bracket. Explain why the
generating function for the wraps of strings with a good count is xC.x/.
Hint: The wrap of a string with good count also has a good count that starts and
ends with 0 and remains positive everywhere else.

(b) Explain why, for every string s with a good count, there is a unique sequence
of strings s1 ; : : : ; sk that are wraps of strings with good counts and s D s1


sk .
For example, the string r WWD [ [ ] ] [ ] [ [ ] [ ] ] 2 GoodCount equals s1 s2 s3 where
s1 WWD [ [ ] ] ; s2 WWD [ ] ; s3 WWD [ [ ] [ ] ] , and this is the only way to express r as a
sequence of wraps of strings with good counts.

(c) Conclude that

C D 1 C xC C .xC /2 C


C .xC /n C


; (i)

so
1
C D ; (ii)
1 xC
and hence p
1˙ 1 4x
C D : (iii)
2x
Let D.x/ WWD 2xC.x/. Expressing D as a power series

D.x/ D d0 C d1 x C d2 x 2 C


;

we have
dnC1
cn D : (iv)
2
(d) Use (iii), (iv), and the value of c0 to conclude that
p
D.x/ D 1 1 4x:

(e) Prove that

.2n 3/
.2n 5/


5
3
1
2n
dn D :
nŠ
Hint: dn D D .n/ .0/=nŠ

(f) Conclude that !

1 2n
cn D :
nC1 n
 “mcs” — 2018/6/6 — 13:43 — page 766 — #774

766 Chapter 16 Generating Functions

Exam Problems
Problem 16.18.
Define the sequence r0 ; r1 ; r2 ; : : : recursively by the rule that r0 WWD 1 and

rn WWD 7rn 1 C .n C 1/ for n > 0:

Let R.x/ WWD 1 n

P
0 rn x be the generating function of this sequence. Express R.x/
as a quotient of polynomials or products of polynomials. You do not have to find a
closed form for rn .

Problem 16.19.
Alyssa Hacker sends out a video that spreads like wildfire over the UToob network.
On the day of the release—call it day zero—and the day following—call it day
one—the video doesn’t receive any hits. However, starting with day two, the num-
ber of hits rn can be expressed as seven times the number of hits on the previous
day, four times the number of hits the day before that, and the number of days that
has passed since the release of the video plus one. So, for example on day 2, there
will be 7  0 C 4  0 C 3 D 3 hits.
(a) Give a linear a recurrence for rn .

(b) Express the generating function R.x/ WWD 1 n

P
0 rn x as a quotient of polyno-
mials or products of polynomials. You do not have to find a closed form for rn .

Problem 16.20.
Consider the following sequence of predicates:

Q1 .x1 / WWD x1
Q2 .x1 ; x2 / WWD x1 IMPLIES x2
Q3 .x1 ; x2 ; x3 / WWD .x1 IMPLIES x2 / IMPLIES x3
Q4 .x1 ; x2 ; x3 ; x4 / WWD ..x1 IMPLIES x2 / IMPLIES x3 / IMPLIES x4
Q5 .x1 ; x2 ; x3 ; x4 ; x5 / WWD ...x1 IMPLIES x2 / IMPLIES x3 / IMPLIES x4 / IMPLIES x5
:: ::
: :

Let Tn be the number of different true/false settings of the variables x1 ; x2 ; : : : ; xn

for which Qn .x1 ; x2 ; : : : ; xn / is true. For example, T2 D 3 since Q2 .x1 ; x2 / is
 “mcs” — 2018/6/6 — 13:43 — page 767 — #775

16.6. References 767

true for 3 different settings of the variables x1 and x2 :

x1 x2 Q2 .x1 ; x2 /
T T T
T F F
F T T
F F T
We let T0 D 1 by convention.
(a) Express TnC1 in terms of Tn and n, assuming n  0.

(b) Use a generating function to prove that

2nC1 C . 1/n
Tn D
3
for n  1.

Problem 16.21.
Define the Triple Fibonacci numbers T0 ; T1 ; : : : recursively by the rules
T0 D T1 WWD 3;
Tn WWD Tn 1 C Tn 2 (for n  2): (16.24)
(a) Prove that all Triple Fibonacci numbers are divisible by 3.

(b) Prove that the gcd of every pair of consecutive Triple Fibonacci numbers is 3.

(c) Express the generating function T .x/ for the Triple Fibonacci as a quotient of
polynomials. (You do not have to find a formula for Œx n T .x/.)

Problem 16.22.
Define the Double Fibonacci numbers D0 ; D1 ; : : : recursively by the rules
D0 D D1 WWD 1;
Dn WWD 2Dn 1 C Dn 2 (for n  2): (16.25)
(a) Prove that all Double Fibonacci numbers are odd.

(b) Prove that every two consecutive Double Fibonacci numbers are relatively
prime.

(c) Express the generating function D.x/ for the Double Fibonacci as a quotient
of polynomials. (You do not have to find a formula for Œx n D.x/.)
 “mcs” — 2018/6/6 — 13:43 — page 768 — #776

768 Chapter 16 Generating Functions

Problems for Section 16.5

Practice Problems
Problem 16.23.
In the context of formal series, a number r may be used to indicate the sequence
.r; 0; 0; : : : ; 0; : : : /:
For example the number 1 may be used to indicate the identity series I and 0
may indicate the zero series Z. Whether “r” means the number or the sequence is
supposed to be clear from context.
Verify that in the ring of formal power series,
r ˝ .g0 ; g1 ; g2 ; : : : / D .rg0 ; rg1 ; rg2 ; : : : /:
In particular,
.g0 ; g1 ; g2 ; : : : / D 1 ˝ .g0 ; g1 ; g2 ; : : : /:

Problem 16.24.
Define the formal power series
X WWD .0; 1; 0; 0; : : : ; 0; : : : /:
(a) Explain why X has no reciprocal.
Hint: What can you say about x
.g0 C g1 x C g2 x 2 C


/?

(b) Use the definition of power series multiplication ˝ to prove carefully that
X ˝ .g0 ; g1 ; g2 ; : : : / D .0; g0 ; g1 ; g2 ; : : : /:

(c) Recursively define X n for n 2 N by

X 0 WWD I WWD .1; 0; 0; : : : ; 0; : : : /;
X nC1 WWD X ˝ X n :
Verify that the monomial x n refers to the same power series as X n .

Class Problems
Problem 16.25.
Show that a sequence G WWD .g0 ; g1 ; : : : / has a multiplicative inverse in the ring of
formal power series iff g0 ¤ 0.