This post is part 1 of a series on generating functions, based on notes we have been working through from Sedgewick and Flajolet's Analysis of Algorithms and Trotter's Applied Combinatorics. The full set of notes lives on our wiki: Generating Functions.

Generating functions are one of those techniques that look completely mysterious the first time you see them, and then look like the obvious thing to do the tenth time you see them. They turn recurrences into functions, functions into series, and series back into closed forms for the coefficients you actually wanted. This post walks through one of the …