2
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ 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}$ $\endgroup$ – Thomas Andrews Mar 1 '13 at 21:38
  • $\begingroup$ I get from Wolfram Alpha: $$\frac{1}{3(3x-1)}-\frac{1}{12(3x+1)}+\frac{1}{4(x-1)}$$ $\endgroup$ – Thomas Andrews Mar 1 '13 at 21:42
  • $\begingroup$ I think you are missing a negative in front of the first term. $\endgroup$ – intervade Mar 1 '13 at 21:48
  • $\begingroup$ Whoops, yes, but the key is, what you wrote above is not really even close to what WA gives - you got four signs wrong $\endgroup$ – Thomas Andrews Mar 1 '13 at 21:49
  • $\begingroup$ Yes, I have just found my mistake, thanks for pointing it out. $\endgroup$ – intervade Mar 1 '13 at 21:54
3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I'm not sure what to think then, from a pure laziness factor, wolframalpha $\endgroup$ – intervade Mar 1 '13 at 21:41
  • $\begingroup$ Look at that answer again in your link, @intervade, it is not what you wrote in your question above. $\endgroup$ – Thomas Andrews Mar 1 '13 at 21:46
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ – intervade Mar 1 '13 at 21:59
  • 1
    $\begingroup$ @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}$. $\endgroup$ – Brian M. Scott Mar 1 '13 at 22:00
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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