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.

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
add comment

1 Answer

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:

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

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