Generating Functions

Generating functions are one of the most surprising, useful, and clever inventions in discrete mathematics.

Generating functions transform problems about sequences into problems about functions.
For example:
* sequence {1, 4, 9, 16, 25, ... }
* closed form a(n) = n^2
* generating function: F(x)=x(1+x)/(1-x)^3.
Interested? An introduction to generating functions (pdf document) can be found [ here ].