Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given a generating function for some sequence, I'm basically interested in the first few values. Well an explicit closed form would be nice, but often there isn't any. I suppose if there is any, I'd try to find the Taylor expansion at $0$ to get the coefficients, right? So I have to be able to calculate the n-th derivative?

But also if there is no explicit closed form a recursive formula would be nice. For a computer it shouldn't be too difficult to calculate some of the first few values then. Is it possible to derive such a recursion directly from the generating function?

The formal method provides good cooking recipes for translating a combinatorial class into a generating function (I'm referring here to Flajolet's and Sedgewick's terminology from Analytic Combinatorics). Is there something similar which yields a recursion instead of a generating function?

I couldn't find anything about recursions, except how to solve recursions by use of generating functions. But actually I find the opposite useful too.

share|improve this question
    
If you know the generating function, you can convert it into a recursion if you can recognize it as the solution to some algebraic/differential equation in a sort of backwards way from how one goes from a recursive formula to a generating function. Unfortunately, I don't know any general way to find relations satisfied by complicated formulae. –  Aaron Dec 26 '11 at 19:25
1  
Well, for example if you are given the function and if you know that your generating function satisfies some finite order differential equation, you may try using linear algebra to find a differential equation that it satisfies. –  Aleks Vlasev Dec 26 '11 at 19:35
add comment

1 Answer

up vote 0 down vote accepted

Ok, I think it's already clear to me that there is no cooking recipe as I was imaging, so I'm answering my own question to close it.

I've found now an example in Analytic Combinatorics (Example I.13) and it affirms what was written already in the comments to my question. The recursion is found by use of an differential equation, but it doesn't seem to me easy to find such an equation in any case. Since there is nothing mentioned there, I suppose there is no general method known and I'll have to find for every specific case a specific solution.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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