2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Aaron
    Dec 26, 2011 at 19:25
  • 1
    $\begingroup$ 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. $\endgroup$
    – Alexander Vlasev
    Dec 26, 2011 at 19:35

2 Answers 2

Reset to default
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

Not really an answer, but an example of something that can be done. Take the generating function for central Delannoy numbers:

$\begin{align} D(z) = \sum_{n \ge 0} D_{n n} z^n = \frac{1}{\sqrt{1 - 6 z + z^2}} \end{align}$

This is a power, take logarithms and differentiate:

$\begin{align} \frac{D'(z)}{D(z)} &= - \frac{1}{2} \frac{-6 + 2 z}{1 - 6 z + z^2} \\ (1 - 6 z + z^2) D'(z) &= (3 - z) D(z) \end{align}$

Multiply out and compare coefficients of $z^{n - 1}$ to get:

$\begin{align} &n D_{n, n} - 6 (n - 1) D_{n - 1, n - 1} + (n - 2) D_{n - 2, n - 2} = 3 D_{n - 1, n - 1} - D_{n - 1, n - 1} \\ \end{align}$

which simplifies to:

$\begin{align} &n D_{n, n} = (6 n - 3) D_{n - 1, n - 1} - (n - 1) D_{n - 2, n - 2} \end{align}$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .