4
$\begingroup$

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

  • 5
    $\dfrac{1}{1-(-x^2)} = 1 + (-x^2) + (-x^2)^2 + (-x^2)^3 + \dots$2012-08-21

4 Answers 4

0

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

3

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

But this is the wrong generating function.

2

Your generating function is incorrect.

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}\;.$

Your function is

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

  • 0
    @saadtaame: Suppose that $r,s$, and $t$ are the zeroes of $2x^3-x^2+1$; then $(x-r)(x-s)(x-t)=x^3-\frac12x^2+\frac12$, and $A(x)=\frac{x^2}{(x-r)(x-s)(x-t)}$, and you can decompose it into partial fractions. The problem is finding $r,s$, and $t$; they can be found exactly, but [the algorithm](http://mathworld.wolfram.com/CubicFormula.html) is messy. [This page](http://www.1728.org/cubic.htm) gives the approximate values $-0.6572981061383739$ and $ 0.5786490530691869\pm0.6525757632523738i$.2012-08-21
1

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

  • 0
    With the correction to [Brian M. Scott's answer](http://math.stackexchange.com/a/185202), this is now just a verification.2012-08-21