# 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?

• It's similar to taking the Fourier transform. It's called the Z-transform. The idea is that there are different bases for the vector space (just like in linear algebra) of all sequences, and some operations are simpler to view in some bases than in others. One operation which is simpler in the Z-basis is convolution which becomes just multiplication. – jkabrg Jul 15 '15 at 17:36
• What makes them valuable ? - Who said they're “valuable” ? They're... invaluable ! ;-$)$ – Lucian Jul 15 '15 at 18:53
• Did you learn about exponential generating functions and Dirichlet generation functions yet? (They are discussed in the book.) He states that they're useful mainly from the rules for multiplying two series together. I'm not sure how relevant this is, though. – Akiva Weinberger Jul 15 '15 at 22:12
• Often, the reason some things are useful is "because they work." – Akiva Weinberger Jul 15 '15 at 22:13

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...