
Generating Functions for Catalan Numbers
Peter Shor, teaching MIT's 18.200 Principles of Discrete Applied Mathematics, derives the generating function for the Catalan numbers and uses it to produce the closed-form formula for the sequence. The lecture builds the generating function step by step from a recurrence relation, works through the algebra needed to solve for it explicitly, and then extracts the Catalan number formula from the resulting expression. As the seventh session in the course, it assumes familiarity with earlier material on generating functions and recurrences, and it runs a full seventy two minutes at blackboard pace, with Shor working through each derivation in detail rather than skipping steps. The content is squarely combinatorics, useful for students wanting a worked example of how generating functions turn a recursive definition into a direct formula.