generating functions, can't seem to get the correct answers.

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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

so

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

and

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