The Central Idea
Suppose a sequence is
\[ a_0,a_1,a_2,a_3,\ldots \]Its ordinary generating function is
\[ \boxed{ A(x)=a_0+a_1x+a_2x^2+a_3x^3+\cdots }. \]The sequence values become the coefficients of powers of \(x\).
The generating function therefore acts as an algebraic container for the entire sequence.
Ordinary Generating Functions
The generating functions used in this lesson are ordinary generating functions, often abbreviated OGF.
For a sequence \(\{a_n\}_{n\ge0}\),
\[ \boxed{ A(x)=\sum_{n=0}^{\infty}a_nx^n }. \]The coefficient of \(x^n\) is exactly \(a_n\).
Coefficient Extraction
A convenient notation for "the coefficient of \(x^n\)" is
\[ [x^n]A(x). \]Therefore, if
\[ A(x)=\sum_{n=0}^{\infty}a_nx^n, \]then
\[ \boxed{a_n=[x^n]A(x)}. \]This notation lets us move cleanly between a sequence and its generating function.
Example: Encode a Finite Beginning
Consider the sequence
\[ 2,\ 5,\ 7,\ 9,\ldots \]beginning at index \(0\).
Its generating function begins
\[ \boxed{ A(x)=2+5x+7x^2+9x^3+\cdots }. \]The coefficient of \(x^0\) is \(2\), the coefficient of \(x^1\) is \(5\), and so on.
Example: Constant Sequence
Consider
\[ 1,\ 1,\ 1,\ 1,\ldots \]The generating function is
\[ 1+x+x^2+x^3+\cdots. \]Using the geometric-series identity,
\[ \boxed{ 1+x+x^2+x^3+\cdots=\frac{1}{1-x} }. \]Therefore, the constant sequence \(a_n=1\) has generating function
\[ \boxed{A(x)=\frac{1}{1-x}}. \]Formal Power Series Viewpoint
In many combinatorial uses, generating functions are treated as formal power series.
This means the main concern is the algebra of coefficients rather than the numerical value obtained by substituting a particular real number for \(x\).
The symbol \(x\) acts as a bookkeeping variable that records index.
The Geometric-Series Pattern
The identity
\[ \frac{1}{1-x} = 1+x+x^2+x^3+\cdots \]is the most basic generating-function pattern.
More generally,
\[ \frac{1}{1-rx} = 1+rx+r^2x^2+r^3x^3+\cdots. \]Therefore,
\[ \boxed{ [x^n]\frac{1}{1-rx}=r^n }. \]Generating Function for a Geometric Sequence
Consider
\[ a_n=Ar^n,\qquad n\ge0. \]Then
\[ A(x) = \sum_{n=0}^{\infty}Ar^nx^n. \]Factor out \(A\):
\[ A(x) = A\sum_{n=0}^{\infty}(rx)^n. \]Therefore,
\[ \boxed{ A(x)=\frac{A}{1-rx} }. \]Example: Powers of Two
The sequence
\[ 1,\ 2,\ 4,\ 8,\ 16,\ldots \]has
\[ a_n=2^n. \]Therefore,
\[ \boxed{ A(x)=\frac{1}{1-2x} }. \]The coefficient of \(x^n\) in this rational function is \(2^n\).
Shifting a Sequence by Multiplying by \(x\)
If
\[ A(x)=a_0+a_1x+a_2x^2+\cdots, \]then
\[ xA(x) = a_0x+a_1x^2+a_2x^3+\cdots. \]Multiplication by \(x\) shifts every coefficient one position to the right.
Repeated Shifts
Multiplying by \(x^k\) shifts coefficients \(k\) positions:
\[ x^kA(x) = a_0x^k+a_1x^{k+1}+a_2x^{k+2}+\cdots. \]This simple operation is one of the key reasons generating functions work so naturally with recurrence relations.
Adding Generating Functions
Suppose
\[ A(x)=\sum_{n\ge0}a_nx^n \]and
\[ B(x)=\sum_{n\ge0}b_nx^n. \]Then
\[ A(x)+B(x) = \sum_{n\ge0}(a_n+b_n)x^n. \]Therefore,
\[ \boxed{ [x^n](A(x)+B(x))=a_n+b_n }. \]Scaling a Generating Function
If
\[ A(x)=\sum_{n\ge0}a_nx^n, \]then
\[ cA(x) = \sum_{n\ge0}(ca_n)x^n. \]Multiplying a generating function by a constant scales every sequence term by that constant.
Product of Generating Functions
Products combine coefficients through convolution.
If
\[ A(x)=\sum_{n\ge0}a_nx^n \]and
\[ B(x)=\sum_{n\ge0}b_nx^n, \]then the coefficient of \(x^n\) in the product is
\[ \boxed{ [x^n]A(x)B(x) = \sum_{k=0}^{n}a_kb_{n-k} }. \]Why Product Coefficients Convolve
To produce a term \(x^n\) in
\[ A(x)B(x), \]we may multiply
\[ x^k \]from the first series by
\[ x^{n-k} \]from the second.
Every decomposition
\[ n=k+(n-k) \]contributes to the coefficient.
Example: Squaring the Basic Geometric Series
Since
\[ \frac{1}{1-x} = 1+x+x^2+x^3+\cdots, \]we have
\[ \frac{1}{(1-x)^2} = (1+x+x^2+\cdots)^2. \]The coefficient of \(x^n\) counts the number of pairs
\[ (i,j) \]of nonnegative integers satisfying
\[ i+j=n. \]There are \(n+1\) such pairs, so
\[ \boxed{ \frac{1}{(1-x)^2} = \sum_{n=0}^{\infty}(n+1)x^n }. \]Generating Function for \(n+1\)
From the previous identity,
\[ \boxed{ [x^n]\frac{1}{(1-x)^2}=n+1 }. \]Thus, the sequence
\[ 1,\ 2,\ 3,\ 4,\ldots \]has generating function
\[ \boxed{ \frac{1}{(1-x)^2} }. \]Generating Function for \(n\)
The sequence
\[ 0,\ 1,\ 2,\ 3,\ 4,\ldots \]has generating function
\[ x+2x^2+3x^3+\cdots. \]This is
\[ \boxed{ \frac{x}{(1-x)^2} }. \]Generating Functions Can Encode Finite Sequences
A finite sequence can be encoded by a polynomial.
For example,
\[ 3,\ 1,\ 4,\ 2 \]corresponds to
\[ \boxed{ A(x)=3+x+4x^2+2x^3 }. \]There are no nonzero coefficients beyond \(x^3\).
Generating Functions and Recurrences
A recurrence relates nearby terms of a sequence.
A generating function turns those shifted terms into shifted power series.
Algebra can then combine the recurrence into an equation for the single function \(A(x)\).
This is the central recurrence-solving idea behind generating functions.
Example: Constant Recurrence
Consider
\[ a_0=1, \] \[ a_n=a_{n-1}\qquad(n\ge1). \]The sequence is
\[ 1,\ 1,\ 1,\ 1,\ldots \]so
\[ \boxed{ A(x)=\frac{1}{1-x} }. \]This is the simplest recurrence-to-generating-function example.
Example: Geometric Recurrence
Let
\[ a_0=1, \] \[ a_n=2a_{n-1}\qquad(n\ge1). \]Write
\[ A(x)=a_0+a_1x+a_2x^2+\cdots. \]The recurrence implies
\[ a_1x+a_2x^2+a_3x^3+\cdots = 2x(a_0+a_1x+a_2x^2+\cdots). \]The left side is
\[ A(x)-a_0. \]Therefore,
\[ A(x)-1=2xA(x). \]Solve the Generating-Function Equation
From
\[ A(x)-1=2xA(x), \]collect \(A(x)\):
\[ A(x)(1-2x)=1. \]Hence,
\[ \boxed{ A(x)=\frac{1}{1-2x} }. \]Extracting coefficients gives
\[ \boxed{a_n=2^n}. \]A Basic Arithmetic Recurrence
Consider
\[ a_0=0, \] \[ a_n=a_{n-1}+1\qquad(n\ge1). \]Then
\[ 0,\ 1,\ 2,\ 3,\ldots \]and therefore
\[ \boxed{ A(x)=\frac{x}{(1-x)^2} }. \]Generating functions can therefore encode arithmetic sequences as rational functions as well.
Fibonacci Generating Function
Let
\[ F_0=0,\qquad F_1=1, \] \[ F_n=F_{n-1}+F_{n-2}\qquad(n\ge2). \]Define
\[ F(x)=F_0+F_1x+F_2x^2+\cdots. \]Because \(F_0=0\) and \(F_1=1\),
\[ F(x)=x+F_2x^2+F_3x^3+\cdots. \]Translate the Fibonacci Recurrence
For \(n\ge2\),
\[ F_n=F_{n-1}+F_{n-2}. \]Multiplying by \(x^n\) and summing produces
\[ F(x)-x = xF(x)+x^2F(x). \]Therefore,
\[ F(x)(1-x-x^2)=x. \]Hence,
\[ \boxed{ F(x)=\frac{x}{1-x-x^2} }. \]What the Fibonacci Generating Function Means
The rational function
\[ \frac{x}{1-x-x^2} \]is another representation of the sequence
\[ 0,\ 1,\ 1,\ 2,\ 3,\ 5,\ldots. \]Formally,
\[ \boxed{ \frac{x}{1-x-x^2} = \sum_{n=0}^{\infty}F_nx^n }. \]Later algebraic methods can extract explicit formulas from this expression.
Generating Functions as Sequence Algebra
Generating functions convert sequence operations into algebraic operations.
- adding sequences corresponds to adding generating functions;
- scaling a sequence corresponds to scaling its generating function;
- shifting indices corresponds to multiplying by powers of \(x\);
- convolution corresponds to multiplication.
This translation is what makes generating functions so powerful.
Combinatorial Interpretation of Products
Suppose \(a_n\) counts objects of size \(n\) of one type and \(b_n\) counts objects of size \(n\) of another type.
The coefficient
\[ \sum_{k=0}^{n}a_kb_{n-k} \]counts ways to choose a first object of size \(k\) and a second object of size \(n-k\).
Therefore, multiplication naturally models combined structures whose sizes add.
Example: Two Nonnegative Parts
Suppose we want to count ordered pairs
\[ (i,j) \]of nonnegative integers with
\[ i+j=n. \]Each coordinate contributes generating function
\[ \frac{1}{1-x}. \]Therefore, the pair contributes
\[ \frac{1}{(1-x)^2}. \]Its coefficient is
\[ n+1. \]Hence, there are
\[ \boxed{n+1} \]such ordered pairs.
Example: Three Nonnegative Parts
For ordered triples
\[ (i,j,k) \]satisfying
\[ i+j+k=n, \]the generating function is
\[ \left(\frac{1}{1-x}\right)^3. \]The coefficient of \(x^n\) counts the possible triples.
This is an early example of generating functions connecting algebra with counting.
Restrictions Can Be Encoded Algebraically
Suppose one component may contribute only sizes
\[ 0,2,4,6,\ldots. \]Its generating function is
\[ 1+x^2+x^4+x^6+\cdots. \]Therefore,
\[ \boxed{ \frac{1}{1-x^2} }. \]Restrictions on allowable sizes become restrictions on which powers of \(x\) appear.
Example: Positive Contributions
If a component must contribute at least \(1\), then its possible sizes are
\[ 1,2,3,\ldots \]and the generating function is
\[ x+x^2+x^3+\cdots. \]Therefore,
\[ \boxed{ \frac{x}{1-x} }. \]Example: At Most One Choice
Suppose an item can be selected either zero times or one time, and selecting it contributes size \(m\).
The generating function is
\[ \boxed{1+x^m}. \]The term \(1\) represents not selecting it, while \(x^m\) represents selecting it once.
Example: Any Number of Copies
If an item of size \(m\) may be used any nonnegative number of times, then its possible contributions are
\[ 0,m,2m,3m,\ldots. \]The generating function is
\[ 1+x^m+x^{2m}+x^{3m}+\cdots. \]Therefore,
\[ \boxed{ \frac{1}{1-x^m} }. \]Generating Functions and Partition-Style Counting
Products such as
\[ \frac{1}{(1-x)(1-x^2)(1-x^3)} \]encode ways to combine parts of sizes \(1\), \(2\), and \(3\), with any nonnegative number of each size.
The coefficient of \(x^n\) records the number of permitted combinations whose total size is \(n\).
Detailed partition theory appears later, but the encoding principle begins here.
Rational Generating Functions
Many important recurrence sequences have generating functions that are rational functions:
\[ \boxed{ A(x)=\frac{P(x)}{Q(x)} }. \]Arithmetic, geometric, Fibonacci-type, and many constant-coefficient linear recurrences produce generating functions of this type.
Why Rational Forms Matter
Rational functions can often be:
- expanded into power series;
- factored;
- decomposed into partial fractions;
- used to derive coefficient formulas;
- used to expose recurrence structure.
These algebraic operations turn sequence questions into familiar symbolic manipulation.
From a Rational Generating Function Back to a Recurrence
Suppose
\[ A(x)=\frac{1}{1-3x}. \]Then
\[ (1-3x)A(x)=1. \]Comparing coefficients gives
\[ a_0=1 \]and, for \(n\ge1\),
\[ \boxed{a_n=3a_{n-1}}. \]Thus, generating functions can translate in both directions.
Coefficient Comparison
If two formal power series are equal,
\[ A(x)=B(x), \]then corresponding coefficients are equal:
\[ [x^n]A(x)=[x^n]B(x). \]This coefficient-by-coefficient equality is the foundation of many generating-function arguments.
Initial Conditions Matter in Generating-Function Derivations
When a shifted sum is rewritten in terms of \(A(x)\), the first few terms must be handled separately.
For example,
\[ \sum_{n=1}^{\infty}a_nx^n = A(x)-a_0. \]Forgetting the initial term changes the resulting algebra and usually gives the wrong generating function.
Another Shift Identity
If
\[ A(x)=\sum_{n=0}^{\infty}a_nx^n, \]then
\[ \sum_{n=1}^{\infty}a_{n-1}x^n = xA(x). \]This identity is used constantly when translating first-order recurrences.
Second-Order Shift Identity
Similarly,
\[ \sum_{n=2}^{\infty}a_{n-2}x^n = x^2A(x). \]These shifts align the indices in second-order recurrences such as the Fibonacci relation.
Generating Functions versus Closed Forms
A generating function is not the same thing as a closed form for \(a_n\).
The expression
\[ A(x)=\frac{x}{1-x-x^2} \]encodes all Fibonacci numbers at once, but it does not itself directly give \(F_n\) until we extract the coefficient of \(x^n\).
Generating functions are sequence encodings; closed forms are direct term formulas.
Generating Functions Can Lead to Closed Forms
If a rational generating function is decomposed into simpler pieces, those pieces may correspond to familiar coefficient sequences.
This can produce explicit formulas for \(a_n\).
The detailed connection with characteristic roots and partial fractions is beyond the introductory scope here, but the pathway is important:
\[ \boxed{ \text{recurrence} \longrightarrow \text{generating function} \longrightarrow \text{coefficient formula} }. \]Generating Functions as a Proof Tool
Because a generating function encodes an entire sequence, an algebraic identity between generating functions can prove infinitely many coefficient identities at once.
Once two power series are shown equal, every corresponding coefficient is equal.
Example: A Simple Sequence Identity
Since
\[ \frac{1}{1-x} = 1+x+x^2+\cdots, \]multiplying by \(1-x\) gives
\[ (1-x)(1+x+x^2+\cdots)=1. \]The coefficient cancellation reflects the recurrence
\[ a_n=a_{n-1} \]for the constant sequence.
Generating Functions and Recursive Counting
Counting problems often produce recurrences because an object of size \(n\) can be decomposed into smaller cases.
Generating functions package the resulting count sequence and can convert the recurrence into algebra.
This creates a bridge between recursive counting and symbolic algebra.
Example: Tiling Recurrence
Suppose \(T_n\) counts tilings of length \(n\) using pieces of length \(1\) and \(2\).
Then
\[ T_n=T_{n-1}+T_{n-2}. \]With suitable initial conditions, the generating function is therefore rational with denominator
\[ 1-x-x^2. \]The same denominator that appears in Fibonacci generating functions reflects the same recursive structure.
Denominators Often Reflect Recurrence Structure
For a constant-coefficient linear recurrence, the denominator of a rational generating function often records the coefficients of the recurrence.
For example,
\[ a_n=3a_{n-1}-2a_{n-2} \]is associated with a denominator of the form
\[ \boxed{1-3x+2x^2}. \]This is another algebraic bridge between recurrence relations and generating functions.
Generating Functions Are Not Ordinary Functions in Every Context
When treated formally, the power series
\[ A(x)=\sum_{n\ge0}a_nx^n \]is manipulated according to coefficient rules even when convergence at a particular numerical value of \(x\) is not being discussed.
This formal viewpoint is standard in combinatorics and discrete mathematics.
Analytic Questions Are Separate
A power series may also be studied as an analytic function on values of \(x\) where it converges.
That perspective introduces radius of convergence and analytic methods.
Those topics are valuable, but they are not required for the basic coefficient-manipulation methods used here.
Common Error: Using the Wrong Starting Index
If the sequence begins at \(a_0\), then
\[ A(x)=a_0+a_1x+a_2x^2+\cdots. \]If the sequence begins at \(a_1\), either reindex it or define the generating function convention explicitly.
Indexing determines which coefficient corresponds to which term.
Common Error: Forgetting Initial Terms after a Shift
The identity
\[ \sum_{n=1}^{\infty}a_nx^n = A(x)-a_0 \]is not the same as \(A(x)\).
The missing \(a_0\) term must be removed explicitly.
Common Error: Treating \(x\) as a Sequence Term
In a generating function, \(x\) is a bookkeeping variable.
The sequence values are the coefficients:
\[ a_0,a_1,a_2,\ldots. \]The powers of \(x\) record index.
Common Error: Confusing Product with Termwise Multiplication
If
\[ C(x)=A(x)B(x), \]then the coefficient \(c_n\) is generally
\[ \sum_{k=0}^{n}a_kb_{n-k}, \]not simply
\[ a_nb_n. \]Generating-function multiplication produces convolution.
Common Error: Calling the Generating Function the Sequence
The sequence is
\[ a_0,a_1,a_2,\ldots. \]Its generating function is the formal power series
\[ A(x)=\sum_{n\ge0}a_nx^n. \]They encode the same information but are different mathematical objects.
Common Error: Assuming Every Generating Function Is Rational
Many important examples are rational, especially those arising from simple linear recurrences.
But generating functions can have many other forms.
Rationality is an important special case, not part of the definition.
Common Error: Ignoring Coefficient Meaning
The purpose of a generating function is not merely to manipulate an algebraic expression.
Every coefficient should retain a clear interpretation as a sequence term or count.
Good generating-function work moves back and forth between the algebra and the coefficients it encodes.
A Reliable Procedure for Building a Generating Function
- Identify the indexing convention.
- Write the sequence terms \(a_0,a_1,a_2,\ldots\).
- Attach \(x^n\) to the term \(a_n\).
- Form \(A(x)=\sum_{n\ge0}a_nx^n\).
- Look for a familiar series pattern or algebraic simplification.
- Check that the coefficients reproduce the intended sequence.
A Reliable Procedure for Translating a Recurrence
- Define \(A(x)=\sum_{n\ge0}a_nx^n\).
- Multiply the recurrence by \(x^n\).
- Sum over the index range where the recurrence is valid.
- Rewrite shifted sums using \(A(x)\), \(xA(x)\), \(x^2A(x)\), and so on.
- Handle initial terms separately.
- Solve the resulting algebraic equation for \(A(x)\).
- Extract coefficients or identify a known power-series form.
A Reliable Procedure for Product Counting
- Identify the independent component choices.
- Write a generating function for the possible sizes of each component.
- Multiply the component generating functions.
- Extract the coefficient of the desired total size.
- Interpret the coefficient combinatorially.
Practice 1: Encode a Sequence
Write the beginning of the generating function for
\[ 3,\ 4,\ 6,\ 9,\ldots \]indexed from \(0\).
Practice 2: Extract a Coefficient
Let
\[ A(x)=5+2x+7x^2+4x^3+\cdots. \]Find
\[ [x^2]A(x). \]Practice 3: Constant Sequence
Find the generating function for
\[ 1,\ 1,\ 1,\ 1,\ldots. \]Practice 4: Geometric Sequence
Find the generating function for
\[ 1,\ 3,\ 9,\ 27,\ldots. \]Practice 5: Shift a Generating Function
If
\[ A(x)=a_0+a_1x+a_2x^2+\cdots, \]write the first several terms of \(x^2A(x)\).
Practice 6: Product Coefficient
Suppose
\[ A(x)=1+x+x^2+\cdots \]and
\[ B(x)=1+x+x^2+\cdots. \]What is the coefficient of \(x^4\) in \(A(x)B(x)\)?
Practice 7: Fibonacci Generating Function
State the ordinary generating function for the Fibonacci sequence with
\[ F_0=0,\qquad F_1=1. \]Practice 8: Allowed Even Contributions
Write the generating function for choosing any nonnegative number of units, each contributing size \(2\).
Practice 9: Recurrence from a Rational Function
Suppose
\[ A(x)=\frac{1}{1-4x}. \]Identify the encoded sequence and a recurrence for it.
Practice 10: Positive Parts
What generating function represents one component that may contribute any positive integer size?
Practice Answers
Practice 1
Since the sequence is indexed from \(0\),
\[ \boxed{ A(x)=3+4x+6x^2+9x^3+\cdots }. \]Practice 2
The coefficient of \(x^2\) is
\[ \boxed{7}. \]Practice 3
\[ 1+x+x^2+x^3+\cdots = \boxed{\frac{1}{1-x}}. \]Practice 4
The sequence is \(3^n\), so
\[ \boxed{ A(x)=\frac{1}{1-3x} }. \]Practice 5
\[ x^2A(x) = \boxed{ a_0x^2+a_1x^3+a_2x^4+\cdots }. \]Practice 6
The coefficient counts pairs
\[ (i,j) \]of nonnegative integers satisfying
\[ i+j=4. \]These are
\[ (0,4),(1,3),(2,2),(3,1),(4,0). \]Therefore,
\[ \boxed{5}. \]Practice 7
\[ \boxed{ F(x)=\frac{x}{1-x-x^2} }. \]Practice 8
\[ 1+x^2+x^4+x^6+\cdots = \boxed{ \frac{1}{1-x^2} }. \]Practice 9
Since
\[ \frac{1}{1-4x} = 1+4x+4^2x^2+4^3x^3+\cdots, \]the sequence is
\[ \boxed{a_n=4^n}. \]A recurrence is
\[ \boxed{ a_0=1,\qquad a_n=4a_{n-1}\quad(n\ge1) }. \]Practice 10
\[ x+x^2+x^3+\cdots = \boxed{ \frac{x}{1-x} }. \]What to Remember
An ordinary generating function encodes a sequence as coefficients:
\[ \boxed{ A(x)=\sum_{n=0}^{\infty}a_nx^n }. \]- The coefficient of \(x^n\) is the sequence term \(a_n\).
- Multiplying by \(x\) shifts coefficients by one position.
- Adding generating functions adds sequences term by term.
- Multiplying generating functions produces coefficient convolution.
- The geometric-series identity is the basic generating-function pattern.
- Many linear recurrences produce rational generating functions.
- Recurrences can be translated into algebraic equations for generating functions.
- Generating functions encode counting restrictions through allowable powers of \(x\).
- Products naturally represent combined structures whose sizes add.
- Generating functions are sequence encodings, not the same thing as closed forms.
- Formal power series methods focus on coefficients rather than numerical substitution.
Where We Go Next
Generating functions transform recursive and combinatorial structure into algebra. Another important recursive tool analyzes how a problem branches into smaller subproblems and how the resulting work accumulates across levels.
The next lesson, Recursion Trees, develops tree representations of recursive processes, level-by-level expansion, branching structure, repeated subproblems, and accumulated cost.