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?

  • 1
    $\begingroup$ Well, the 'recurrence' sequence itself is obtained as the coefficients in the Taylor series of the function. $\endgroup$ – Berci Nov 8 '12 at 12:59

You can get a recurrence from the denominator such as



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


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.