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.
2 · Watch
Take it off screen
Where it sits
8 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.