Start typing to search every page on this site.

Use ↑ and ↓ to move through results, then Enter to open one.

    Skip to main content

    8. Ordinary generating functions: constructions and coefficient extraction#

    In earlier notes, we introduced ordinary generating functions as polynomials to solve finite selection problems. However, many counting problems involve unrestricted choices or sequences that go on indefinitely. To tackle these, we must extend our toolkit from finite polynomials to infinite formal power series.

    Our main goal in this note is to learn how to efficiently manipulate infinite power series (which are not polynomials) using algebraic tricks, Taylor series expansions, and operational rules.

    8.1 Infinite formal power series and rational functions#

    Let’s start with a fundamental question: how can we represent an infinite sequence using a compact algebraic expression?

    Example 8.1 (Representing the constant sequence )#

    Consider the sequence for all . Its generating function is the infinite series Is there a closed-form "function" that represents ?

    Let’s try a clever algebraic trick. Multiply by : Now, subtract from term by term: Factoring out on the left gives: Dividing both sides by , we arrive at the classic rational expression:

    Warning (A note on formal division)#

    The identity is completely justified in formal power series algebra—it follows directly from the definition of series multiplication without worrying about limits or convergence.

    However, division is not generally defined for arbitrary generating functions! We have not formally defined what it means to divide one series by another. In practice, we do it anyway whenever the denominator has a non-zero constant term (like , whose constant term is ), because such series possess formal multiplicative inverses.

    Connecting generating functions to Taylor series.

    Where do these closed-form expressions come from in calculus?

    If a calculus function is infinitely differentiable at , we can associate it with its Taylor expansion at :

    Example 8.2 (Taylor expansion of )#

    Let’s compute the first 4 terms of the Taylor expansion of at and compare them to our geometric series: Evaluating the Taylor coefficients gives , matching term-for-term the power series we found above!

    8.2 Solving constrained integer equations#

    Generating functions give us a powerful, automated way to count non-negative integer solutions to equations.

    Suppose we want to find the number of integer solutions to subject to specific bounds on each variable:

    Encoding variable bounds with shifting and geometric series.

    Each variable gets its own generating factor tracking its allowable values as exponents of :

    • Lower bounds (Shifting): A lower bound means we factor out . For example, gives:

    • Finite ranges: For a range , begin with the unrestricted series shifted by , then remove the unrestricted series shifted by . The ensures that values through remain:

    Putting all 5 factors together, the overall generating function is:

    Example 8.3 (Computing selected solution counts by hand)#

    Find the number of solutions when , and . These values are useful checkpoints: is the smallest possible total, and , , and are the degrees at which the correction terms from the two smaller upper bounds first appear.

    Write Thus . For , the factor cannot contribute, so expanding the two relevant numerator factors gives We now substitute the selected values one at a time:

    8.2.1 Expanding a rational generating function in Sage#

    Once the generating function has been written in closed form, Sage can expand it as a power series and extract a specified coefficient. In the following example, records the possible even nonnegative values of , records the possible positive odd values of , and records the values . Their product records the total .

    The following code may be run in SageCell.

    var('x')

U(x)=1/(1-x^2)
V(x)=x/(1-x^2)
W(x)=(x^10-x^21)/(1-x)

A(x)=U(x)*V(x)*W(x)

show(A(x).series(x,100))
show(A(x).series(x,100).coefficient(x,25))

    The command var(’x’) declares as a symbolic variable. The next three lines name the generating functions for the three variables, and the line defining multiplies those factors. The command A(x).series(x,100) expands the rational expression at far enough to include the coefficient of . Applying .coefficient(x,25) to that expansion returns the coefficient of . To extract a different coefficient, change and make the series order larger than the requested exponent.

    8.3 Combinatorial interpretations of powers and products#

    We begin with the familiar algebraic identity that will guide the first interpretation.

    Theorem 8.4 (Binomial Theorem)#

    For every integer ,

    We will reinterpret the Binomial Theorem using generating functions: each factor will encode one choice, and the coefficient of will count the outcomes in which exactly choices contribute .

    The same multiplication principle also explains the generating functions for multisets and for the restricted integer equations studied earlier.

    Subset selection: generating function for with fixed.

    When choosing a subset of size from distinct items, each item presents a binary choice: either don’t choose it () or choose it (). The factor for a single item is .

    Why does the product count choices from items?

    Let’s assign a distinct variable to represent selecting item (for ). The choice polynomial is:

    Example 8.5 (Explicit expansion for )#

    Let’s expand completely: Every single term in this expansion corresponds to a specific subset of items!

    If we substitute for all , every product of distinct variables becomes . Collecting like terms yields: In general, .

    Multiset selection: generating function for with fixed.

    Now consider finding non-negative integer solutions to for a fixed .

    For a single variable , there is exactly 1 way to choose the value . We represent these options with the formal series: For variables, the product of all choice series is: When we replace each with , every product becomes .

    Each individual factor becomes . Multiplying identical copies together gives: By the negative binomial expansion, , which matches our known formula for multiset selection!

    8.4 Operations on generating functions#

    By applying algebraic operations to a generating function , we systematically transform its sequence of coefficients :

    1. Argument Scaling (): Replacing with multiplies the -th coefficient by :

    2. Right Index Shift (): Multiplying by shifts all sequence terms one position to the right (inserting a at index ):

    3. Index Multiplication (): Differentiating and multiplying by multiplies each term by its index :

    4. Cumulative Summation (): Multiplying by builds running partial sums of the sequence:

    Summary of standard operations.

    OperationGenerating Function Generated Sequence
    Scaling
    Right Shift (for )
    Index Multiplication
    Double Index Multiplication
    Cumulative Sum
    Cauchy Product

    8.5 Application: computing the sum of squares#

    Let’s use these operational rules to derive the classic formula for the sum of squares .

    Step 1: Start with the constant sequence. The generating function for is .

    Step 2: Generate . Apply index multiplication :

    Step 3: Generate . Apply index multiplication a second time:

    Step 4: Accumulate the sum up to . Multiply by to sum terms from to :

    The columns below accumulate the functions obtained in Steps 1–4. Each entry is the coefficient of in the function at the top of its column. Reading down a column shows the first ten terms of the corresponding sequence.

    010
    111
    212
    313
    414
    515
    616
    717
    818
    919

    Step 5: Extract the coefficient manually. Split the numerator into two terms: Using the negative binomial extraction rule : Expanding the binomial coefficients:

    8.6 Exercises and solutions#

    Problem 8.6 (Coefficient extraction practice)#

    Compute closed-form expressions for the coefficients of the following series manually. Then evaluate each expression at the indicated values of .

    1. for .

    2. for .

    3. for .

    4. for .

    Solutions:

    1. Solution to Part 1: Using argument scaling () together with the negative binomial series formula : Thus the requested coefficients are when , when , and when .

    2. Solution to Part 2: Distribute the term : Applying the shift rule : Since the first shifted series begins in degree and the second begins in degree , the coefficient formula valid for every is For the requested values, the coefficients are when , when , when , and when .

    3. Solution to Part 3: We first simplify the finite sum before multiplying it by . Since , this is a finite geometric series: The exponent marks the first term after the final term . Now multiply by the remaining factor:

      To extract the coefficient for every , define Thus . The zero case makes the shifts below work even when is smaller than one of the displayed exponents. Therefore,

      At , this gives , , and , respectively. The zero at occurs because the smallest degree in the product is .

    4. Solution to Part 4: Let . The finite sum in this part is obtained by applying to the finite geometric series from Part 3: Multiplying by adds five more factors of to the denominator: Define so that . Distributing the numerator and shifting the coefficients gives, for every , At , the corresponding coefficients are , , and .

    On this page