Generating functions with power series

Question

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

Answer 1

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

Answer 2

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

Answer 3

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.

Answer 4

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