Take the 2-minute tour ×

I am quite new to generating functions and I don't understand how one comes from the generating function equation to the recurrence:

$A = \sum_{n\geq 0} a_nx^n$

Now if $A=A(2xA'-A)+x$ holds, why is it easy to conclude that $a_n = \sum^{n-1}_{k=1} (2k-1)a_ka_{n-k}$ ?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

The most important property of generating functions is that their multiplication is translated to a convolution of the corresponding sequences:


$$f(x)=\sum_{n=0}^\infty a_nx^n$$ $$g(x)=\sum_{n=0}^\infty b_nx^n$$

Then $h(x)=f(x)g(x)$ can be written as:

$h(x)=\sum_{n=0}^\infty (\sum_{k=0}^n a_ib_{n-i})x^n$

The sum in the middle - $\sum_{k=0}^n a_ib_{n-i}$ is what I call "convolution". It comes from the rules of multiplying power series (very similar to multiplying polynomials).

Now, if $A=\sum_{n=0}^\infty a_nx^n$, then by deriving "term-term" we have:

$$A^\prime = \sum_{n=1}^\infty a_nnx^{n-1}$$

And so:

$$2xA^\prime = \sum_{n=1}^\infty 2na_nx^x$$

And so

$$2xA^\prime-A = \sum_{n=1}^\infty (2n-1)a_nx^x$$

And the result follows.

If you're new to generating function - congratulations! This is a fascinating subject which at first glance might seem intimidating, but is actually very elegant and beautiful. I suggest Wilf's "generatingfunctionology" or Stanley's "Enumerative Combinatorics", or Flajolet and Sedgewick's "Analytic Combinatorics" (both the letter books can be quite a challenge, but are worth it).

share|improve this answer
thank you very much for the nice answer, I am currently reading generatingfunctionology. –  stefan Feb 1 '12 at 21:37

Your Answer


