How do I get a sequence from a generating function?

151 Views Asked by At

For example if I have the generating function $\frac{1}{1-2x}$ then it corresponds to the sequence $1 + 2x + 4x^2 + 8x^3 +~...$. I know how to start from the sequence and get the generating function, but I don't know how to start from the generating function and get the sequence.

Similarly, what if I have a generating function like $\frac{1}{1+x}$? How do I get the corresponding sequence? Same way?

1

There are 1 best solutions below

2
On BEST ANSWER

Maybe the following may help you. If you have a linear recurrence of the form $$ u_{n+2}+a\cdot u_{n+1}+b\cdot u_n=0 \tag1 $$ then, multiplying out $(1)$ by $x^{n+2}$ and summing one gets $$ \sum_{n=0}^\infty u_{n+2}x^{n+2}+a\cdot \sum_{n=0}^\infty u_{n+1}x^{n+2}+b\cdot \sum_{n=0}^\infty u_nx^{n+2}=0\tag2 $$ or, with changes of index, $$ \sum_{n=2}^\infty u_{n}x^n+a\cdot x\sum_{n=1}^\infty u_{n}x^{n}+b\cdot x^2\sum_{n=0}^\infty u_nx^{n}=0\tag3 $$ $$ \sum_{n=0}^\infty u_{n}x^n+a\cdot x\sum_{n=0}^\infty u_{n}x^{n}+b\cdot x^2\sum_{n=0}^\infty u_nx^{n}=u_0+(u_1+au_0)\cdot x\tag4 $$ that is, by factorizing $\displaystyle \sum_{n=0}^\infty u_{n}x^n=f(x)$, $$ (1+ax+b x^2)f(x)=u_0+(u_1+au_0)\cdot x $$ and

$$ f(x)=\frac{u_0+(u_1+au_0)\cdot x}{1+ax+b x^2} \tag5 $$

Going from $(1)$ to $(5)$ and vice-versa is a usual link between a generating function and a recurrent relation between its coefficients.