Solution of recurrences by generating functions

Summary

This method turns a recurrence for a sequence $(u_n)$ into an equation for its generating function $U(x) = \sum_{n \ge 0} u_n x^n$. For a linear recurrence with constant coefficients, the equation is linear and its solution $U$ is a rational function. Expanding $U$ again, for example by partial fractions, gives a closed formula for $u_n$. The method is a standard tool of enumerative combinatorics and of the analysis of algorithms.