---
title: "Generating Functions"
description: "Store a whole sequence as the coefficients of a power series, then use algebra on the series to answer questions about the sequence."
canonical: https://lightmysky.com/learn/mathematics/generating-functions-mt_WAX3O-HjRk
source: https://lightmysky.com/learn/mathematics/generating-functions-mt_WAX3O-HjRk.md
retrieved: 2026-09-12
---

> **Agent view.** This is the Markdown twin of the page, for tools and assistants.
> When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md
> API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md
> Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt
> Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json
> Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`.

# Generating Functions

Store a whole sequence as the coefficients of a power series, then use algebra on the series to answer questions about the sequence.

Subject: Mathematics · Area: Discrete Mathematics · Ages 20 to 21
Page: https://lightmysky.com/learn/mathematics/generating-functions-mt_WAX3O-HjRk

## Ready when they can

- Write the generating function of a simple sequence and read a coefficient back out
- Solve a recurrence by converting it into an equation for the generating function
- Explain what a product of two generating functions counts

## Lesson: Packing a whole sequence into one function

A generating function stores a whole sequence as the coefficients of a power series. The short expression 1 divided by (1 minus x) expands to 1 plus x plus x squared and on forever. Hard sequence problems turn into easier algebra on the function.

**Example.** Reading a coefficient recovers any term. In 1 divided by (1 minus x) every coefficient is 1, so the x to the power 5 term is 1. The polynomial (1 plus x) cubed expands to 1 plus 3x plus 3x squared plus x cubed. Differentiating gives 1 divided by (1 minus x) squared, which stores 1, 2, 3, and on.

Recurrences become equations for the series. For a(n) equal to 2 times a(n minus 1) with a0 equal 1, multiply through and sum to get A(x) minus 1 equal to 2x times A(x). Solving gives 1 divided by (1 minus 2x), which expands as 1 plus 2x plus 4x squared and on, so a4 is 16.

**Tip.** Multiplying generating functions convolves the sequences instead of adding them term by term. Each new coefficient sums products of pairs, which counts combined choices. Test it: (1 plus x) times (1 plus x) is 1 plus 2x plus x squared, not 2 plus 2x.

**Recap.** Store the sequence as coefficients, do algebra on the function, and read the answer back as a coefficient.

## Practice

14 questions on this page, each with its working shown.

## Needs first

- [Partial Fractions for Rational Integrands](https://lightmysky.com/learn/mathematics/partial-fractions-for-rational-integrands-mt_PA8qxs424c)
- [Recurrence Relations and Characteristic Roots](https://lightmysky.com/learn/mathematics/recurrence-relations-and-characteristic-roots-mt_q0b2bi0iAB)
- [Power Series and the Radius of Convergence](https://lightmysky.com/learn/mathematics/power-series-and-the-radius-of-convergence-mt_RnYb0JLKbD)

## Opens up

- [Graphs, Degrees and the Handshake Lemma](https://lightmysky.com/learn/mathematics/graphs-degrees-and-the-handshake-lemma-mt_1oqO_o3bTO)