ABSTRACT
In this chapter we discuss the technique of generating functions, an extremely powerful tool that has applications in a large number of areas. For example, generating functions can be used to find the solutions to counting problems, to solve recurrences, and to prove a wide variety of identities. In their classic text Concrete Mathematics, Graham, Knuth, and Patashnik call generating functions “the most important idea in this whole book.” [32, p. 196]
