0
$\begingroup$

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}$ ?

1 Answers 1

1

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

If

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

  • 0
    thank you very much for the nice answer, I am currently reading generatingfunctionology.2012-02-01