What is the intuition behind generating functions? What makes them valuable? I'm sorry if this question makes no sense. I have been reading generatingfunctionology and I have been able to solve the problems in the first chapters and I understand the mechanism I have to follow to use generating functions to obtain closed formulas for sequences given generating functions.
I don't really understand what is going on behind the obvious. It just sort of seems like magic to me that generating functions let us "solve" recurrence relations. What is it about placing the terms into an infinite series that makes it such a valuable asset?
 A: Algebraically, what's happening is that taking an ordinary generating function is a bijection between the vector space of sequences and the ring of formal power series. In the ring of formal power series you have additional algebraic structure coming from the multiplication operation (and the division operation, when applicable). Operations like differentiation and integration are also well-defined in this ring, and agree with calculus-differentiation and calculus-integration when the power series can be differentiated and integrated as a calculus object.
This extra algebraic structure allows you to do things like work with generating functions as Taylor expansions of differentiable functions, and within the ring of formal power series the associated operations and manipulations can be rigorously justified. So in fact, it's not calculus that puts generating functions on rigorous footing - it's ring theory.
I'm no expert on generating functions, and there's a lot else to be said. This discussion above for ordinary generating functions can be reproduced for exponential generating functions. NaN says they can be viewed as $Z$-transforms, there is still something to be gained by considering the convergence properties of generating functions, there is also something to be gained by working with generating functions as Fourier series, and more...
