Discrete Math › Section G · Additional topics › Topic G.1
Generating functions
A generating function packs an entire infinite sequence into one algebraic expression by using the terms as coefficients of powers of x. Ordinary algebra on that expression, such as adding, multiplying and solving, then becomes a way to handle sequences, solve recurrences and count.
In this topic
- A clothesline for a sequence
- Formal series: x is only a placeholder
- The basic generating function
- Building new generating functions
- Worked example: finding a generating function
- Differentiating to get n
- Multiplying generating functions
- Worked example: solving a recurrence
- Generating functions for counting
- Common mistakes to avoid
- Key takeaways
This topic is part of Wuanberri Pro. Checking your access…