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

1 Answer 1

24
$\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.