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

So, I've been having some issues with generating functions and counting problems. An example problem is: $$ a_n = a_{n-1} + 9a_{n-2} - 9a_{n-3} \;\;\; (n \geq 3)$$

Where $a_0 = 0, a_1 = 1, a_2 = 2$

Let's define $g(x)$ as our generating function, in which case, $$ g(x) = a_0 + a_1x + a_2x^2+... = 0 + x + 2x^2 + (a_2 + 9a_1 - 9a_0)x^3 + (a_3+9a_2-9a_1)x^4+...$$

We can factor this like so...

$$g(x) = x + 2x^2 + x(a_2x^2 + a_3x^3 + ...) + 9x^2(a_1x + a_2x^2+...) - 9x^3(a_0 + a_1x + a_2x^2+...)$$

Now, the infinite series, $a_2x^2 + a_3x^3+...$ can be defined as $g(x) - a_0 - a_1x$, and the series $a_1x + a_2x^2+...$ can be defined as $g(x) - a_0$, and lastly, the series $a_0 + a_1x + a_2x^2+...$ is $g(x)$

So, making substitutions:

$$g(x) = x + 2x^2 + xg(x) - x^2 + 9x^2g(x) - 9x^3g(x)$$

and finally,

$$g(x) = \frac{x^2 + x}{9x^3 - 9x^2 - x + 1}$$

I decided to run this through wolfram alpha for the partial fraction decomposition and I get: $$g(x) = \frac{1}{3}\left (\frac{1}{1+3x}\right ) + \frac{1}{12}\left (\frac{1}{1+3x}\right ) - \frac{1}{4}\left (\frac{1}{1+x}\right )$$

Each of the terms in parenthesis can be expressed as a series, in summation notation:

$$\frac{1}{3}\sum_{k = 0}^{\infty }(-3)^kx^k + \frac{1}{12}\sum_{k = 0}^{\infty }(-3)^kx^k - \frac{1}{4}\sum_{k=0}^{\infty }(-1)^kx^k$$

And, my final answer should be:

$$a_n = \frac{1}{3}(-3)^n + \frac{1}{12}(-3)^n - \frac{1}{4}(-1)^n$$

Which, is incorrect. Could someone point out what I'm doing wrong?

share|cite|improve this question
Okay, I think you either misused Alpha or it is very wrong. In particular, $x-1$ is a factor of the denominator, so there should be a term $\frac{a}{x-1}$ – Thomas Andrews Mar 1 '13 at 21:38
I get from Wolfram Alpha: $$\frac{1}{3(3x-1)}-\frac{1}{12(3x+1)}+\frac{1}{4(x-1)}$$ – Thomas Andrews Mar 1 '13 at 21:42
I think you are missing a negative in front of the first term. – intervade Mar 1 '13 at 21:48
Whoops, yes, but the key is, what you wrote above is not really even close to what WA gives - you got four signs wrong – Thomas Andrews Mar 1 '13 at 21:49
Yes, I have just found my mistake, thanks for pointing it out. – intervade Mar 1 '13 at 21:54
up vote 3 down vote accepted

The partial fraction decomposition is not correct: Note that the expression in the denominator factors as $(3x-1)(3x+1)(x-1)$. Calculating by hand may be faster, and safer.

share|cite|improve this answer
I'm not sure what to think then, from a pure laziness factor, wolframalpha – intervade Mar 1 '13 at 21:41
Look at that answer again in your link, @intervade, it is not what you wrote in your question above. – Thomas Andrews Mar 1 '13 at 21:46

Your partial fractions aren’t right. However, there’s an easier way to handle such problems.

Let $g(x)=\sum_{n\ge 0}a_nx^n$. be the generating function. With the convention that $a_n=0$ if $n<0$, we can write the recurrence as

$$a_n = a_{n-1}+9a_{n-2}-9a_{n-3}+[n=1]+[n=2]\;,\tag{1}$$

valid for all $n\ge 0$, where the last two terms are Iverson brackets; they ensure that the initial values are correct.

Now multiply $(1)$ by $x^n$ and sum over $n$ to get

$$\begin{align*} g(x)&=\sum_{n\ge 0}a_nx^n\\ &=\sum_n(a_{n-1}+9a_{n-2}-9a_{n-3}+[n=1]+[n=2])x^n\\ &=\sum_n a_{n-1}x^n+9\sum_n a_{n-2}x^n-9\sum_n a_{n-3}x^n+x+x^2\\ &=x\sum_n a_nx^n+9x^2\sum_n a_nx^n-9x^3\sum_n a_nx^n+x+x^2\\ &=g(x)\left(x+9x^2-9x^3\right)+x+x^2\;, \end{align*}$$


$$\begin{align*}g(x)&=\frac{x+x^2}{1-x-9x^2+9x^3}\\ &=\frac{x+x^2}{(1-x)(1-3x)(1+3x)}\\ &=\frac{-1}{4(1-x)}+\frac1{3(1-3x)}-\frac1{12(1+3x)}\\ &=-\frac14\sum_{n\ge 0}x^n+\frac13\sum_{n\ge 0}3^nx^n-\frac1{12}\sum_{n\ge 0}(-1)^n3^nx^n\;, \end{align*}$$


$$\begin{align*} a_n&=-\frac14+3^{n-1}-\frac14(-1)^n3^{n-1}\\ &=3^{n-1}-\frac14\left(1+(-1)^n3^{n-1}\right)\;. \end{align*}$$

share|cite|improve this answer
This could be a completely different question but could you explain more of how you come to $a_n$, I can't see where you are getting $3^{n-1}$ from. – intervade Mar 1 '13 at 21:59
@intervade: In the middle term it’s $\frac13\cdot3^n$, and in the last term it’s $\frac1{12}(-1)^n3^n=\frac14\cdot\frac13(-1)^n3^n=\frac14(-1)^n3^{n-1}$. – Brian M. Scott Mar 1 '13 at 22:00

A simpler way, due to Wilf: Your recurrence is $a_{n + 3} = a_{n + 2} + 9 a_{n + 1} - 9 a_n$. If you multiply by $x^n$ and add for $n \ge 0$ it is: $$ \begin{align*} \sum_{n \ge 0} a_{n + 3} x^n &= \sum_{n \ge 0} a_{n + 2} x^n + 9 \sum_{n \ge 0} a_{n + 1} x^n - 9 \sum_{n \ge 0} a_n x^n \\ \frac{g(x) - a_0 - a_1 x - a_2 x^2}{x^3} &= \frac{g(x) - a_0 - a_2 x}{x^2} + 9 \frac{g(x) - a_0}{x} - 9 g(x) \end{align*} $$ As you see, it is almost immediate to write the last equation just by looking at the recurrence. A term $a_{n + k}$ gives rise to $$ \frac{g(x) - a_0 - a_1 x - \ldots - a_{k - 1} x^{k - 1}}{x^k} $$ The rest, as they say, is algebra (a computer algebra package like maxima helps a lot) and a bit of series expansion.

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.