How to find the recurrence relation from a given polynomial?

Question

Consider the formal power series: $A(x)=\sum a_nx^n$.

and

$A(x)= \frac{8+14x-50x^2}{1-7x^2+6x^3}$

I am trying to derive a recurrence relation, Is there a general method for doing it?

Please help, Thanks in advance

Answer 1

Let me suppose that you want $$A(x)=\sum_{n=0}^\infty a_i x^i$$ So, let us mutliply both sides by the denominator $$8+14x-50x^2=(1-7x^2+6x^3)\sum_{n=0}^\infty a_i x^i$$ Now, decompose the product $$8+14x-50x^2=\sum_{n=0}^\infty a_i x^i-7\sum_{n=0}^\infty a_i x^{i+2}+6\sum_{n=0}^\infty a_i x^{i+3}$$ So, for the constant term $$8=a_0$$ For the first power of $x$ $$14=a_1$$ For the $x^2$ term $$-50=a_2-7a_0$$ So, to summarize $a_0=8,a_1=14,a_2=6$.

Now, for any power $n\gt 2$, the term $x^n$ is zero in the lhs. So, $$0=a_n-7a_{n-2}+6a_{n-3}$$ So, the recurrence is $$a_n=7a_{n-2}-6a_{n-3}$$ This is exactly what is described in the Wikipedia page and the same procedure applies for all cases like your one (just identify the coefficients for a given power of $x$ on each side).

Is this clear ? If not, just post.