Introduction to Combinatorics, 2nd Edition

CHAPTER 2

GENERATING FUNCTIONS

Generating functions are algebraic objects that provide a powerful tool for analyzing recurrence relations. In this chapter, we will cover the basic theory of generating functions and examine many specific examples.

2.1 Rational generating functions

Given any sequence a₀, a₁, a₂,…,the ordinary generating function is

(2.1)

The generating function f(x) contains all of the information about the sequence {a_n}, and, being an algebraic entity, it is often easier to manipulate than the sequence itself. The term a_n is recovered by finding the coefficient of xⁿ in f(x).

EXAMPLE 2.1 Generating function for the Fibonacci sequence

Find the ordinary generating function for the Fibonacci sequence {F₀, F₁, F₂,…}.

Solution: Let . We obtain

Through mass cancellation, the recurrence relation for the Fibonacci numbers yields

and

(2.2)

The function f(x) contains complete ...