# what are generating functions

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

• "A generating function is a clothesline on which we hang up a sequence of numbers for display." -Wilf, Generatingfunctionology. – Semiclassical Oct 6 '14 at 14:45

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