Page 558 - Discrete Mathematics and Its Applications

8.4 Generating Functions 537

8.4 Generating Functions

Introduction

Generating functions are used to represent sequences efficiently by coding the terms of a se-
quence as coefficients of powers of a variable x in a formal power series. Generating functions
can be used to solve many types of counting problems, such as the number of ways to select
or distribute objects of different kinds, subject to a variety of constraints, and the number of
ways to make change for a dollar using coins of different denominations. Generating functions
can be used to solve recurrence relations by translating a recurrence relation for the terms of
a sequence into an equation involving a generating function. This equation can then be solved
to find a closed form for the generating function. From this closed form, the coefficients of the
power series for the generating function can be found, solving the original recurrence relation.
Generating functions can also be used to prove combinatorial identities by taking advantage of
relatively simple relationships between functions that can be translated into identities involving
the terms of sequences. Generating functions are a helpful tool for studying many properties of
sequences besides those described in this section, such as their use for establishing asymptotic
formulae for the terms of a sequence.
We begin with the definition of the generating function for a sequence.

DEFINITION 1 The generating function for the sequence a 0 ,a 1 ,...,a k ,... of real numbers is the infinite
series

∞
k k
G(x) = a 0 + a 1 x + ··· + a k x + ··· = a k x .
k = 0

Remark: The generating function for {a k } given in Definition 1 is sometimes called the ordinary
generating function of {a k } to distinguish it from other types of generating functions for this
sequence.
EXAMPLE 1 The generating functions for the sequences {a k } with a k = 3,a k = k + 1, and a k = 2 k

∞ k ∞ k ∞ k k
are k = 0 3x , k = 0 (k + 1)x , and k = 0 2 x , respectively. ▲
We can define generating functions for finite sequences of real numbers by extending a
finite sequence a 0 ,a 1 ,...,a n into an infinite sequence by setting a n+1 = 0,a n+2 = 0, and so
on. The generating function G(x) of this infinite sequence {a n } is a polynomial of degree n
j
because no terms of the form a j x with j> n occur, that is,
n
G(x) = a 0 + a 1 x + ··· + a n x .

EXAMPLE 2 What is the generating function for the sequence 1, 1, 1, 1, 1, 1?

Solution: The generating function of 1, 1, 1, 1, 1, 1 is
5
2
3
4
1 + x + x + x + x + x .
By Theorem 1 of Section 2.4 we have
4
2
6
3
(x − 1)/(x − 1) = 1 + x + x + x + x + x 5