0
$\begingroup$

If I have to explain in simple terms the intuition of what is meant by generating function .

e.g.: in my notes I have fibonacci sequence := $0,1,1,2,3,5,8$ .

it's recurrence relation is given by : $a_{\text{n+1}}=a_n+a_{\text{n-1}}$.So,generating function of $\{a_n\}_0^\infty$ is :

$f(x)=a_0+a_1x+a_2x^2\ldots$

what actually the statement means by this...

$\endgroup$
1
  • 2
    $\begingroup$ "A generating function is a clothesline on which we hang up a sequence of numbers for display." -Wilf, Generatingfunctionology. $\endgroup$ Oct 6 '14 at 14:45
4
$\begingroup$

It has no meaning - that's simply the definition. The generating function of a sequence $a_n$ is the function $f(x) = \sum_{k=0}^\infty a_kx^k$ (for values of $x$ where that makes sense, i.e. where the infinite sum converges).

The point about generating functions is that they can sometimes give you information about the sequence that generated them. For example, if $f_n$ is the $n$-th fibonacci number, and $F(x)=\sum_{k=0}^\infty f_kx^k$, then $F(x)=x+xF(x)+x^2F(x)$ (you can just check that for each $k$ the coefficient of $x^k$ is the same on both sides), and from that you can go on to derive a closed form formula for the Fibonacci numbers (which I won't do, but I'm sure it's on stackexchange or wikipedia already).

$\endgroup$
1
  • 1
    $\begingroup$ Even the convergence aspect is sometimes ignored by working with these as formal power series i.e. elements of some appropriate polynomial ring. But being able to treat them as actual power series is very useful for asymptotic analysis, since then one can bring tools of complex analysis to bear. $\endgroup$ Oct 6 '14 at 14:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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