what are generating functions

255 Views Asked by At

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

1

There are 1 best solutions below

1
On BEST ANSWER

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