# Expansion of $x^4\over1+x^2$ into a power series

I calculated the generating function $A(x)$ of the recurrence $a_n = a_{n-2} - 2a_{n-3}$, $(n \ge 0, a_0 = a_1 = 0, a_2 = 2)$ and I have no clue on how to expand it into a power series in order to read the coefficients.

$$A(x) = {-2x^4 \over 1+x^2}.$$

-
$\dfrac{1}{1-(-x^2)} = 1 + (-x^2) + (-x^2)^2 + (-x^2)^3 + \dots$ – user2468 Aug 21 '12 at 21:14

You have the recurrence $$a_n=a_{n-2}-2a_{n-3}+2[n=2]\;,$$ where the last term is an Iverson bracket, and I assume that $a_n=0$ for $n<0$. Then

\begin{align*} A(x)&=\sum_{n\ge 0}a_nx^n\\ &=\sum_{n\ge 0}a_{n-2}x^n-2\sum_{n\ge 0}a_{n-3}x^n+2x^2\\ &=x^2A(x)-2x^3A(x)+2x^2\;, \end{align*}

so $$A(x)=\frac{2x^2}{1-x^2+2x^3}\;.$$

\begin{align*} \frac{-2x^4}{1+x^2}&=-2x^4\cdot\frac1{1-(-x^2)}\\ &=-2x^4\sum_{n\ge 0}(-x^2)^n\\ &=-2x^4\sum_{n\ge 0}(-1)^nx^{2n}\;, \end{align*}

in which the coefficient of $x^2$ and of every odd power of $x$ is $0$. However, $a_2=2\ne 0$, and $a_3=a_1-2a_0=0$, so $a_5=a_3-2a_2=-4\ne 0$.

-
@BrianMScott I got it but I don't see why you added the term $2[n=2]$. – saadtaame Aug 21 '12 at 21:22
@saadtaame: To get the correct value for $a_2$. Without that term, the recurrence generates $a_n=0$ for all $n$. Remember, I’m assuming that $a_n=0$ for negative $n$. Thus, without the extra term I have $a_2=a_0-2a_{-1}=0$; with it I have $a_2=a_0-2a_{-1}+2=2$. – Brian M. Scott Aug 21 '12 at 21:24
@BrianMScott Damn nice trick. – saadtaame Aug 21 '12 at 21:26
@saadtaame: I learned it from Concrete Mathematics, by Graham, Knuth, & Patashnik, one of my favorite texts ever, both as user and as teacher. – Brian M. Scott Aug 21 '12 at 21:29
@BrianMScott Do we always have to start the summation at $n=0$? I started at $n=3$, that was my error maybe. – saadtaame Aug 21 '12 at 21:38

Hint: geometric series. $1/(1+x^2) = 1/(1-r)$ where $r = ?$

But this is the wrong generating function.

-

As has been pointed out, your generating function is wrong. Suppose that $$A(x)=\sum_{k=0}^\infty a_kx^k\tag{1}$$ Then by the initial conditions and the recurrence we get that \begin{align} A(x) &=2x^2+\sum_{k=3}^\infty(a_{k-2}-2a_{k-3})x^k\\ &=2x^2+\sum_{k=1}^\infty a_kx^{k+2}-2\sum_{k=0}^\infty a_kx^{k+3}\\ &=2x^2+\sum_{k=0}^\infty a_kx^{k+2}-2\sum_{k=0}^\infty a_kx^{k+3}\\[4pt] &=2x^2+(x^2-2x^3)A(x)\tag{2} \end{align} And solving $(2)$ for $A(x)$ yields the generating function to be $$A(x)=\frac{2x^2}{1-x^2+2x^3}\tag{3}$$

-
With the correction to Brian M. Scott's answer, this is now just a verification. – robjohn Aug 21 '12 at 22:14

To make sure I understood I'm doing this example. I hope I got it right this one.

$$a_n = 2a_{n-1} + 4a_{n-2}\\a_0=1, a_1=3$$

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

$$A(x)=\sum_{n>=0} a_nx^n=2\sum_{n>=0}a_{n-1}x^n+4\sum_{n>=0}a_{n-2}x^n+1+x$$

$$=2xA(x)+4x^2A(x)+1+x$$

We get: $$A(x)={1+x\over 1-2x-4x^2}$$

-