Polynom invertieren

Man hat ein Polynom gegeben:
z.B. $P(x)=1+x+x^2$

und nun sucht man $\frac{1}{P(x)}$ bzw. $F(x)=\sum _{n\ge 0}{a}_n{x}^n$ sodass $P(x)F(x)=1$.
dazu gilt das ein $a_n$ maximal von $deg(P(x))$ vielen Stellen abhängen kann.
Also:

$$a_n+a_{n-1}+a_{n-2}+...+a_{n-d}=0$$

In unserem Beispiel

$$a_n+a_{n-1}+a_{n-2}=0$$ $$a_n=-a_{n-1}-a_{n-2}$$

Nun kann man iterative $a_0,a_1,...$ lösen

$$a_0=1$$

für $n=1$

$$a_1=-a_0=-1$$

für $n=2$

$$a_2=-a_1-a_0=-(-1)-1=0$$

für $n=3$

$$a_3=-a_2-a_1=-0-(-1)=1$$

für $n=4$

$$a_4=-a_3-a_2=-1-0=-1$$

Somit ist

$$\begin{array}{rl}F(x)& =1-x+x^3-x^4+x^6-x^7+...\\ & =\sum _{k\ge 0}{x}^{3k}-x^{3k+1}\\ & =(1-x)\sum _{k\ge 0}{x}^{3k}\\ & =(1-x)\frac{1}{1-x^3}\\ & =\frac{1-x}{1-x^3}\end{array}$$