26
$\begingroup$

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?

$\endgroup$
  • 10
    $\begingroup$ 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. $\endgroup$ – jkabrg Jul 15 '15 at 17:36
  • 3
    $\begingroup$ What makes them valuable ? - Who said they're “valuable” ? They're... invaluable ! ;-$)$ $\endgroup$ – Lucian Jul 15 '15 at 18:53
  • $\begingroup$ 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. $\endgroup$ – Akiva Weinberger Jul 15 '15 at 22:12
  • 1
    $\begingroup$ Often, the reason some things are useful is "because they work." $\endgroup$ – Akiva Weinberger Jul 15 '15 at 22:13
22
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.