# convert generating function to recurrence

How do we convert generating function to a recurrence:

Lets say we have this function $x\mapsto x\cdot \frac{8+2x-2x^2}{1-6x-3x^2+2x^3}$

how do we get it back to a recurrence?

-
Well, the 'recurrence' sequence itself is obtained as the coefficients in the Taylor series of the function. –  Berci Nov 8 '12 at 12:59

## 2 Answers

You can get a recurrence from the denominator such as

$$f(n)=6f(n-1)+3f(n-2)-2f(n-3).$$

-

There are many recurrence relations that a given sequence can satisfy. One way of finding one such sequence is the following:
Suppose that $f(x)=\sum_{n=0}^\infty a_nx^n$ is a generating function for the sequence $a_n$, which satisfies the recurrence relation $a_n+\alpha_{1}a_{n-1}+..+\alpha_{r}a_{n-r}=b(n)$, with initial values of $a_0,...,a_{r-1}$
Then we have \begin{align*}&(1+\alpha_1x+...+\alpha_rx^r)f(x)=f(x)+\alpha_1xf(x)+...+\alpha_rx^rf(x)\\=&\sum_{n=0}^\infty a_nx^n+\alpha_1\sum_{n=0}^\infty a_nx^{n+1}+...+\alpha_r\sum_{n=0}^\infty a_nx^{n+r}\\=& \sum_{n=0}^\infty a_nx^n+\alpha_1\sum_{n=1}^\infty a_{n-1}x^n+...+\alpha_r\sum_{n=r}^\infty a_{n-r}x^n\\ =& (a_0+a_1x+...+a_{r-1}x^{r-1})+\alpha_1(a_0x+...+a_{r-2}x^{r-1})+...+\alpha_{r-1}a_0x^{r-1}+\sum_{n=r}^\infty (a_n+..+\alpha_{r}a_{n-r})x^n\\ =& a_0+(a_1+\alpha_1 a_0)x+...+(a_{r-1}+...+\alpha_{r-1}a_0)x^{r-1}+\sum_{n=r}^\infty b(n)x^n\end{align*} In your example we have $(1-6x-3x^2+2x^3)f(x)=8+2x-2x^2$. Comparing to the general case, we can see that $r=3$, $b(n)=0$, $\alpha_1=-6,\alpha_2=-3,\alpha_3=2$ $a_0=8$, $a_1=2-(-6)8=50$, \ $a_2=-2-50(-6)-8(-3)=322$. So the recurrence relation will be $$a_n-6a_{n-1}-3a_{n-2}+2a_{n-3}=0, \hspace{10 pt} a_0=8, a_1=50, a_2=322$$

-