Extracting the sequence generated by $\frac{1}{(1-x)(1-x^2)(1-x^3)}$

Question

So I need the general formula for the sequence generated by the generating function $$ \frac{1}{(1-x)(1-x^2)(1-x^3)}. $$ My idea was the decompose this into partial fractions and thus easily deduce the sequence, since the terms would be of the form $\frac{C}{(1-x)^n}$, but I'm left with a term of the form $\frac{x+2}{9(x^2+x+1)}$... How should I proceed?

Answer 1

if a generating function has a representation as rational function of the form \begin{align*} A(z)=\sum_{n=0}^\infty a_n z^n=\frac{P(z)}{Q(z)} \end{align*} with $P(z), Q(z)$ polynomials, $\deg Q=q>\deg P$ and \begin{align*} Q(z)=1+\alpha_1 z+\alpha_2 z^2+\cdots + \alpha_q z^q \end{align*} then the coefficients $a_n$ follow the recurrence relation \begin{align*} a_{n+q}+\alpha_1 a_{n+q-1}+\alpha_2 a_{n+q-2}+\cdots +\alpha_q a_{n}=0\qquad\qquad n\geq 0 \end{align*} See for instance theorem 4.1.1 in Enumerative Combinatorics, Vol. I by R. P. Stanley.

Here, $Q(z)=1-x-x^2+x^4+x^5-x^6$

So, $$a_{n+6}-a_{n+5}-a_{n+4}+a_{n+2}+a_{n+1}-a_{n}=0$$ $$a_n=a_{n-1}+a_{n-2}-a_{n-4}-a_{n-5}+a_{n-6}$$ where $a_0=a_1=1$ if you make polynomial divison.

You can check the recurrence relation here

Answer 2

You also have $\frac k{x+1}$.
If that led to $(-1)^n$ in your formula, you may be happy with $\omega^n$ and $\omega^{-n}$ where $\omega$ is a cube root of $1$.
Instead, if $\frac k{x+1}$ led you to two formulas, one for even $n$ and one for odd $n$, you may be happy with six formulas, one for each value of $n\pmod6$

Answer 3

You can handle a quadratic denominator by rendering

$\dfrac1{1+ax+bx^2}=\sum\limits_{n=0}^\infty c_nx^n; c_{-1}=0,c_0=1,c_n=-ac_{n-1}-bc_{n-2},$

from which (if the quadratic polynomial $x^2+ax+b$ has distinct roots $\alpha,\beta$):

$c_n=\dfrac{\alpha^{n+1}-\beta^{n+1}}{\alpha-\beta}.$

With $a=b=1$ and thus $\alpha,\beta=(-1\pm i\sqrt3)/2$, this yields a relatively simple form, to wit:

$\dfrac{1}{x^2+x+1}=(1-x)+(x^3-x^4)+(x^6-x^7)+...$

This is for a numerator of $1$; multiplying in a different numerator is then straightforward.

Answer 4

Let $\tau=2\pi$.

The fraction $\frac{x+2}{9(x^2+x+1)}$ can itself be decomposed with partial fractions: $$ \frac{x+2}{9(x^2+x+1)}= \frac{x+2}{9(x-e^{i(1/3)\tau})(x-e^{i(2/3)\tau})}=\frac{A}{x-e^{i(1/3)\tau}} + \frac{B}{x-e^{i(2/3)\tau}} $$ Solving as usual, you get $$ \begin{align} A&=\frac{e^{i(1/3)\tau}+2}{9(e^{i(1/3)\tau}-e^{i(2/3)\tau})}& B&=\frac{e^{i(2/3)\tau}+2}{9(e^{i(2/3)\tau}-e^{i(1/3)\tau})} \\ &= i\cdot \frac{-e^{i(1/3)\tau}-2}{9\sqrt 3}& &= i\cdot \frac{e^{i(2/3)\tau}+2}{9\sqrt 3} \end{align} $$

Therefore, $$ \begin{align} [x^n]\frac{x+2}{9(x^2+x+1)} &= [x^n]\left(\frac{-Ae^{i(2/3)\tau}}{1-e^{i(2/3)\tau}x}+\frac{-Be^{i(1/3)\tau}}{1-e^{i(1/3)\tau}x}\right)\\ \\&= (-A)[e^{i(2/3)\tau}]^{n+1}+(-B)[e^{i(1/3)\tau}]^{n+1} \\&= i\cdot \frac{e^{i(2/3)\tau\cdot n}-e^{i(1/3)\tau\cdot n}+2\left(e^{i(2/3)\tau\cdot (n+1)}-e^{i(1/3)\tau\cdot (n+1)}\right)}{9\sqrt3} \\&= i\cdot \frac{e^{-i(1/3)\tau\cdot n}-e^{i(1/3)\tau\cdot n}+2\left(e^{-i(1/3)\tau\cdot (n+1)}-e^{i(1/3)\tau\cdot (n+1)}\right)}{9\sqrt3} \\&= \frac{2\sin\left(\frac13 \tau n\right) + 4\sin\left(\frac13 \tau(n+1)\right)}{9\sqrt 3} \\&= \frac{2\sin\left(\frac13 \tau n\right) + 4\sin\left(\frac13 \tau n\right)\cos\left(\frac13 \tau\right)+4\cos\left(\frac13 \tau n\right)\sin\left(\frac13 \tau \right)}{9\sqrt 3} \\&= \frac29 \cos\left(\frac13\tau n\right)=\boxed{\frac29 \cos\left(\frac23 \pi n\right)}. \end{align}$$