Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
$\dfrac{1}{1-(-x^2)} = 1 + (-x^2) + (-x^2)^2 + (-x^2)^3 + \dots$ – user2468 Aug 21 '12 at 21:14
up vote 2 down vote accepted

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

share|cite|improve this answer
@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.

share|cite|improve this answer

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

share|cite|improve this answer
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(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} $$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.