Generating Functions

Why we bother (motivation before formulas)

You already know two common ways to describe a sequence:

1. 1)Explicitly: “$aₙ = 3·2ⁿ$.”
2. 2)Recursively: “$aₙ = 2a_{n-1}$ with $a₀=3$.”

Generating functions add a third option: describe the sequence as a single formal power series and then use algebra to manipulate it. The surprise is that many sequence operations (shifting, summing, combining choices) become simple algebra.

This is especially useful for counting: when you build objects out of parts, generating functions let you multiply the “part choices” and automatically produce counts for each size.

Definition: ordinary generating function (OGF)

Given a sequence $(aₙ)_{n≥0}$, its ordinary generating function is

• •Think of $x$ as a bookkeeping variable that tracks “size” (like number of steps, total sum, total length).
• •Think of $aₙ$ as “how many objects have size $n$.”

Important: in discrete math we often treat $A(x)$ as a formal power series. That means we’re not worried (at first) about whether the series converges for a numeric value of $x$. We’re using it as an algebraic container for coefficients.

Coefficient extraction

To recover the original sequence, we use the coefficient operator:

Read $[x^n]A(x)$ as: “the coefficient of $xⁿ$ in the series $A(x)$.”

Example:

If $A(x)=2 + 0x + 5x^2 + 7x^3 + \cdots$, then

• •$[x^0]A(x)=2$
• •$[x^1]A(x)=0$
• •$[x^2]A(x)=5$
• •$[x^3]A(x)=7$

One minute of intuition: why a power series encodes a sequence

Because powers of $x$ act like “bins” labeled by $n$:

• •The $x^0$ bin stores $a₀$.
• •The $x^1$ bin stores $a₁$.
• •The $x^2$ bin stores $a₂$.

When you add or multiply series, the bins combine in structured ways—and those structures match common combinatorial constructions.

Quick examples of OGFs you should recognize

1) Constant 1’s:

So the sequence $(1,1,1,1,\dots)$ has OGF $\frac{1}{1-x}$.

2) Geometric weights $(c^n)$:

So $(1,c,c^2,\dots)$ has OGF $\frac{1}{1-cx}$.

3) A shifted sequence:

If $A(x)=\sum_{n\ge0}aₙxⁿ$, then

So multiplying by $x$ shifts coefficients to the right.

That “shift = multiply by $x$” fact will be one of our core tools.

Why this matters

Most generating-function solutions follow a pattern:

1. 1)Express a recurrence or a counting construction as an equation involving $A(x)$.
2. 2)Solve that equation with algebra.
3. 3)Extract $[x^n]$ from the result.

To do step 1 correctly, you need fluency with coefficient extraction and shifts.

The coefficient operator behaves like a “read-off” function

The operator $[x^n]$ is linear:

and constants pull out:

These properties let you extract terms after you do algebra.

Shifts: multiplying by x moves the sequence

Let

Then:

• •Right shift (delay by 1):

So

• •Right shift by k:

So

• •Left shift is slightly trickier because you lose initial terms. Observe:

So

This is the algebraic way to represent “drop the first term and shift left.”

A small but crucial identity: summing a recurrence becomes multiplying by a power series

Suppose you have a recurrence like

If you multiply both sides by $x^n$ and sum over $n\ge1$, you get

Left side:

Right side:

But

So the equation becomes

Now solve:

Finally extract coefficients. A known expansion is

so

Thus $a_n = n$ (with $a_0=0$), matching the recurrence.

The point isn’t this easy recurrence—the point is the workflow:

• •turn shift terms into $xA(x)$,
• •use a geometric series for simple sums,
• •solve algebraically,
• •read off coefficients.

Partial fractions: how we often get closed forms

When $A(x)$ is a rational function like

you can often decompose it into sums of terms like

Then coefficient extraction is straightforward because

and

You don’t need to master every algebra trick yet; you do need to recognize that “rational generating function” usually means “closed form exists and can be extracted with algebra.”

Why products show up in counting

When you build a combinatorial object by choosing Part A and Part B independently, the total size is usually the sum of sizes. Generating functions model exactly that: multiplying series adds exponents.

Let

Then

Group terms by total exponent $n=i+j$:

So the coefficient rule is:

That inner sum is the convolution of sequences $(aₙ)$ and $(bₙ)$.

Static visualization: coefficient extraction in a product

Think of a grid where rows are $i$ (from $A$) and columns are $j$ (from $B$). Each cell contributes to exponent $i+j$.

            j=0      1       2       3       4
          ----------------------------------------
 i=0 |     a0b0    a0b1    a0b2    a0b3    a0b4
 i=1 |     a1b0    a1b1    a1b2    a1b3    a1b4
 i=2 |     a2b0    a2b1    a2b2    a2b3    a2b4
 i=3 |     a3b0    a3b1    a3b2    a3b3    a3b4
 i=4 |     a4b0    a4b1    a4b2    a4b3    a4b4

Cells on the same diagonal have the same sum $i+j$.

• •The diagonal for $n=3$ is:
• •$(i,j)=(0,3)$ contributes $a₀b₃$
• •$(1,2)$ contributes $a₁b₂$
• •$(2,1)$ contributes $a₂b₁$
• •$(3,0)$ contributes $a₃b₀$

So

This diagonal-summing picture is the most important visualization for OGFs.

Interpreting convolution combinatorially

If $a_i$ counts ways to build something of size $i$ (Part A), and $b_j$ counts ways to build something of size $j$ (Part B), then:

• •Choose a split $n=i+(n-i)$.
• •Choose Part A in $a_i$ ways.
• •Choose Part B in $b_{n-i}$ ways.
• •Multiply for independent choices, then sum over all splits.

That is exactly

A concrete “canvas-style” mental animation (shifts + product + read-off)

Even without an actual interactive widget, you can rehearse the same moves:

Example goal: compute $[x^4] \,(1 + x + x^2)(1 + 2x + 3x^2 + 4x^3 + \cdots)$.

1) Shift/limit idea: the polynomial $(1+x+x^2)$ says: take one copy of the second series, plus a copy shifted right by 1, plus a copy shifted right by 2.

2) Write that algebraically:

3) Now “read off” coefficient of $x^4$:

• •From $B(x)$ you need $[x^4]B(x)=5$ (since coefficients are 1,2,3,4,5,...)
• •From $xB(x)$ you need $[x^3]B(x)=4$
• •From $x^2B(x)$ you need $[x^2]B(x)=3$

So

This is the same as diagonal summing, but it highlights shifts explicitly: multiplication by $x^k$ delays coefficients by $k$.

Summary of the mechanics

• •Addition of generating functions: add counts for each size.
• •Multiplication: combine independent parts; coefficient becomes a convolution/diagonal sum.
• •Multiplying by $x^k$: shift sizes by $k$.

Once these feel natural, counting problems become “write the right product, then extract the coefficient.”

Two main use cases

Generating functions shine in two common scenarios:

1) Counting via construction: you build objects from components and want a formula for “# of objects of size n.”

2) Solving recurrences: you have $aₙ$ defined in terms of previous terms, and want a closed form.

We’ll do one of each, and point out the shared pattern.

A) Counting by construction: compositions with restricted parts

A classic problem:

How many ways are there to write $n$ as an ordered sum of 1s and 2s?

This is the “stairs” problem: number of ways to climb $n$ steps taking 1 or 2 at a time. You might know the answer is Fibonacci-like.

Build the generating function

A single step can contribute size 1 or 2. So the OGF for “one step” is

A whole walk is a sequence of steps of any length: 0 steps, 1 step, 2 steps, …

• •0 steps contributes size 0, counted by 1.
• •1 step contributes $S(x)$.
• •2 steps contributes $S(x)^2$.

So the total generating function is a geometric series in $S(x)$:

Thus

Now $[x^n]W(x)$ is the number of walks summing to $n$.

Connection to recurrence automatically

If

then the identity

implies, by matching coefficients, that for $n\ge2$:

So the recurrence drops out of the algebra.

This is a key theme: a rational OGF often corresponds to a linear recurrence with constant coefficients, and vice versa.

B) Solving a recurrence directly with OGFs

Suppose you have a recurrence:

You can solve this with characteristic equations, but let’s practice the OGF method because it generalizes well.

Let

Multiply the recurrence by $x^n$ and sum over $n\ge1$:

Left:

Right:

Handle each term:

• •For the shifted term:

• •For the constant forcing term:

So we get an algebraic equation:

Solve for $A(x)$:

Put the right side over a common denominator:

So

Now do partial fractions:

Assume

Then

Match coefficients:

• •Constant: $C+D = 1$
• •$x$ coefficient: $-3C - D = 1$

Solve:

From $D=1-C$:

Then $D=1-(-1)=2$.

So

Extract coefficients using geometric expansions:

Thus

So

Check: $a₀=-1+2=1$ ok; and $a₁=-1+6=5$, while recurrence gives $3·1+2=5$.

What to remember about the “reduction” step

The core skill is converting “sequence language” into “$A(x)$ algebra.” A helpful cheat sheet:

If you can do these translations slowly and correctly, you can solve a wide range of counting and recurrence problems.

Connections you’re about to unlock

From here, generating functions connect naturally to:

• •solving more complex linear recurrences (including Fibonacci closed forms),
• •more expressive generating functions (exponential generating functions),
• •analytic techniques (asymptotics) when you do care about convergence.

But the foundation is what you’ve learned here: encode → manipulate → extract.