Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
1  
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 2

up vote 1 down vote accepted

You can get a recurrence from the denominator such as

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

share|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|improve this answer

Your Answer

 
discard

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.