# What are generating functions?

> A generating function packs a whole sequence into one power series so you can solve recurrences and sums with algebra. Fibonacci as the worked example.

**Generating function**: A generating function represents a sequence a0, a1, a2, ... as the coefficients of a power series a0 + a1 z + a2 z^2 + ..., so that operations on the series correspond to operations on the sequence.

A **generating function** turns a sequence into a single object you can do algebra on: the sequence a0, a1, a2, ... becomes the power series G(z) = a0 + a1 z + a2 z^2 + .... Shifting the sequence is multiplying by z, convolving two sequences is multiplying their series, and a recurrence becomes an equation you can solve for G(z).

## Fibonacci in three lines

Let F(z) = F0 + F1 z + F2 z^2 + ... with F(n) = F(n-1) + F(n-2). Multiply the recurrence by z^n and sum: F(z) = z + z F(z) + z^2 F(z). So F(z) = z / (1 - z - z^2). Split that into partial fractions and read off the closed form with the golden ratio. The same steps solve most of the recurrences you get from analyzing algorithms.

## Why it is on a programming path

Knuth analyzes algorithms exactly: average comparisons, variance, distributions. Generating functions are his main tool for that, from [§1.2.9](https://cracked.guide/guide/knuth-w025-0) in Volume 1 all the way to BDDs in Volume 4A. They are also the hardest week of the early math for many people. Work the examples with pencil and do not rush.

## Questions

### Do I need calculus for generating functions?

Mostly algebra. Differentiation shows up for things like averages, but a first course in calculus is plenty.

---

Source: https://cracked.guide/glossary/generating-functions
cracked.guide: A free, dated 145-week path to getting genuinely cracked at programming.