# Generating functions with power series

How to find the series expansion for generating function $$\frac {1} {1-2x-x^2}$$?

I have got so far $$\frac {1} {1-2x-x^2}=-\frac {1} {2\sqrt2} (\frac {1} {1-\sqrt2+x} -\frac {1} {1+\sqrt2+x})$$

$$\frac {1} {1-\sqrt2+x}$$ is expanded power series of Sum of $$(\sqrt2-x)^k$$ for $$k=0$$ to infinity, but how would I express it in terms of $$x^k$$?

• Welcome to Maths SX! Do you want an expansion as a power series in a neighbourhood of $0$? Commented May 8, 2019 at 10:57
• i have to find a power series in terms of $a_nx^n$ and then find a recursion relation for an, is that around x=0? sorry im new to Generating functions Commented May 8, 2019 at 11:40
• I'm not sure, as this is probably different from questions of convergence. Commented May 8, 2019 at 11:44

If you call

$$P(x) = \frac{1}{1-2x-x^2} = \sum_{i=0}^{\infty} a_i x^i$$

then:

$$(1-2x-x^2) P(x) = 1$$ $$P(x) = 1 + 2x P(x) + x^2 P(x)$$

Then we can see that $$a_0$$ = 1, $$a_1 = 2a_0 = 2$$, and $$a_{n+2} = 2a_{n+1} + a_n$$

You can then find the closed form for $$a_n$$ by finding the roots $$r_1, r_2$$ of the characteristic polynomial $$x^2 - 2x -1 = 0$$, namely $$r_1 = 1 + \sqrt{2}, r_2 = 1-\sqrt{2}$$, and calculating $$A,B$$ in $$a_n = Ar_1^n + Br_2^n$$ for the initial conditions $$a_0 = A+B = 1$$ $$a_1 = A(1+\sqrt{2} + B(1-\sqrt{2} = 2$$ Solving for $$A,B$$ gives $$A=\frac{2+\sqrt{2}}{4}, B = \frac{2-\sqrt{2}}{4}$$, and $$a_n = \frac{2+\sqrt{2}}{4} (1+\sqrt{2})^n + \frac{2-\sqrt{2}}{4}(1-\sqrt{2})^n$$

If you want to get the expansion near $$x=0$$, then for $$\frac {1} {1-\sqrt2+x}$$ you should see it as $$\frac{-1}{\sqrt2-1-x}=\frac{-1}{\sqrt2-1}\cdot\frac{1}{1-(\frac{x}{\sqrt 2-1})}$$ and then use $$\frac{1}{1-y}=1+y+y^2+\cdots$$.

We may actually find the sequence $$(r_n)$$ defined by $$\frac1{ax^2+bx+c}=\sum_{n\geq0}r_nx^n.$$ We have that \begin{align} 1&=a\sum_{n\geq0}r_nx^{n+2}+b\sum_{n\geq0}r_nx^{n+1}+c\sum_{n\geq0}r_nx^n\\ 1&=cr_0+(cr_1+br_0)x+\sum_{n\geq0}(ar_{n}+br_{n+1}+cr_{n+2})x^{n+2}. \end{align} Then if we define $$cr_0=1$$ and $$cr_1+br_0=0$$ then $$r_0=1/c$$ and $$r_1=-b/c^2$$, and $$0=\sum_{n\geq0}(ar_{n}+br_{n+1}+cr_{n+2})x^{n+2}.$$ So for any $$n\geq0$$ $$ar_n+br_{n+1}+cr_{n+2}=0$$ We then have that there exists a solution to the recurrence in the form $$r_n=\alpha_1\phi_1^n+\alpha_2\phi_2^n$$ Where $$\phi_1$$, $$\phi_2$$ are roots of the recurrence's characteristic polynomial, namely $$cx^2+bx+a=0.$$ So $$\phi_1=\frac{-b+\sqrt{b^2-4ac}}{2c},\qquad \phi_2=\frac{-b-\sqrt{b^2-4ac}}{2c}.$$ Thus, with $$n=0$$: $$r_0=\frac1c=\alpha+\beta$$ and with $$n=1$$: $$r_1=-\frac{b}{c^2}=\alpha\phi_1+\beta\phi_2,$$ Which you can use to solve for $$\alpha$$ and $$\beta$$.

In your case, $$a=-1\\ b=-2\\ c=1.$$ So $$r_0=1,\qquad r_1=2$$ and $$\phi_1=1+\sqrt2,\qquad \phi_2=1-\sqrt2.$$ So finally $$\alpha=\frac{2+\sqrt2}{4},\qquad\beta=\frac{2-\sqrt2}{4}.$$ This gives $$\frac1{1-2x-x^2}=\frac14\sum_{n\geq0}x^n\left[(2+\sqrt2)(1+\sqrt2)^n+(2-\sqrt2)(1-\sqrt2)^n\right].$$

Directly: \begin{align}\frac {1} {1-2x-x^2}&=1+(2x+x^2)+(2x+x^2)^2+(2x+x^2)^3+(2x+x^2)^4+\cdots =\\ &=1+2x+(1+4)x^2+(4+8)x^3+(1+12+16)x^4+(6+32+32)x^5+\cdots=\\ &=1+2x+5x^2+12x^3+29x^4+70x^5+\cdots=\\ &=\sum_{k=0}^{\infty}P_kx^{k-1},\end{align} where $$P_k=2P_{k-1}+P_{k-2},P_0=0,P_1=1$$ is a Pell number.