**Generating functions** are a powerful tool that can be used to solve many counting problems elegantly. It also has several other applications. For instance, they can be applied to find closed-form formulas to some recurrences, e.g., the following formula for the Fibonacci numbers: $$F_n = {1 \over \sqrt{5}}\left(\left({1 + \sqrt{5} \over 2}\right)^n - \left({1 - \sqrt{5} \over 2}\right)^n\right).$$

This formula doesn't even look like it *should* generate the Fibonacci numbers; it doesn't even look like it will give out integers! (But they do; just try substituting several $n$.) Nonetheless, the theory of generating functions will make this result come out naturally and elegantly.

You may read this definitive book about generating functions to learn more about them. Note that the book requires knowledge of more advanced topics, but even if you are not familiar with them, you should still get a good feel on how powerful and nice generating functions are.

Nonetheless, a more accessible introduction to generating functions shall be written here at some point in the future. Email us at ask@noi.ph if you would like to have this written out sooner.