Glossary
What are generating functions?
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 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.