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.
What a learner can do afterwards
- 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
1 · Read
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.
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.
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.
Store the sequence as coefficients, do algebra on the function, and read the answer back as a coefficient.
More to read
6.1 Power Series and Functions
A power series can store a whole sequence in its coefficients. The function 1/(1 minus x) looks like one short expression, yet it expands into 1 plus x plus x squared and so on forever. Reading a coefficient back out recovers any term you want.
6.2 Properties of Power Series
Series can be added, multiplied, differentiated, and integrated term by term inside their range. Multiplying two generating functions convolves their sequences: the new coefficient sums products of pairs. That operation counts combined choices, like picking one object of each of two kinds. Differentiation turns 1, 1, 1, ... into 1, 2, 3, ..., which is how x/(1 minus x) squared arises.
13.3 Geometric Sequences
Geometric sequences are the simplest generating function examples. The sequence 1, 2, 4, 8, ... satisfies a first order recurrence, and its generating function is 1/(1 minus 2 x). Converting the recurrence into an equation for the series solves it in one move. The same method scales to harder recurrences where guessing a formula directly would fail.
Explore more
2 · Watch
En anglaisTake it off screen
Where it sits
This opens up
Nothing builds on it yet.
14 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.