Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
Well, the 'recurrence' sequence itself is obtained as the coefficients in the Taylor series of the function. – Berci Nov 8 '12 at 12:59
up vote 1 down vote accepted

You can get a recurrence from the denominator such as


share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.