Find sequence from the generating function $ A(x)= \dfrac{2x^2-x-2}{3x^3+2x^2+x-1}$ I am working with the sequence $a_0=2, a_1=3$ and $a_2=5$ and
$$a_n=3a_{n-3}+2a_{n-2}+a_{n-1}$$
Using $$A(x)=\sum_{n=0}^\infty a_n x^n = 2+3x+5x^2 + \sum_{n=3}^\infty (3a_{n-3}+2a_{n-2}+a_{n-1})x^n$$
I found an equation for $A(x)$ and hence got the generating function
$$ A(x)= \dfrac{2x^2-x-2}{3x^3+2x^2+x-1}$$
Is there an easy way now to state the sequence explicitly after I have found the generating function
a) in this case or
b) in general?
 A: In general, this sort of problem can be approached by using partial fractions. Let's use your problem as an example. Let $P(x)=2x^2-x-2$ and $Q(x)=3x^3+2x^2+x-1$, and let $\alpha_1,\alpha_2,\alpha_3$ be the roots of $Q(x)$. We can expand by partial fractions as follows
\begin{equation}
A(x)=\frac{P(x)}{Q(x)}=\frac{P(\alpha_1)}{Q'(\alpha_1)}\frac{1}{x-\alpha_1}+\frac{P(\alpha_2)}{Q'(\alpha_2)}\frac{1}{x-\alpha_2}+\frac{P(\alpha_3)}{Q'(\alpha_3)}\frac{1}{x-\alpha_3}
\end{equation}
(which we can do in this way since $Q(x)$ has no repeated roots) Now we determine the coefficients of $A(x)$ by
\begin{equation}
[x^n]A(x)=\frac{P(\alpha_1)}{Q'(\alpha_1)}[x^n]\frac{1}{x-\alpha_1}+\frac{P(\alpha_2)}{Q'(\alpha_2)}[x^n]\frac{1}{x-\alpha_2}+\frac{P(\alpha_3)}{Q'(\alpha_3)}[x^n]\frac{1}{x-\alpha_3}=-\frac{P(\alpha_1)}{Q'(\alpha_1)\alpha_1^{n+1}}-\frac{P(\alpha_2)}{Q'(\alpha_2)\alpha_2^{n+1}}-\frac{P(\alpha_3)}{Q'(\alpha_3)\alpha_3^{n+1}}
\end{equation}
From here, your options are to explicitly find the roots $\alpha_i$ or to use algebraic relationships between the roots $\alpha_i$ to simplify $\frac{P(\alpha_i)}{Q'(\alpha_i)\alpha_1^{n+1}}$, or their sum. You can also numericaly calculate the coefficients by noting that since $A(x)$ is the generating function of a recurrence relationship, then it's coefficients will always be integers, so you can use your favourite numerical method to approximate $[x^n]A(x)$ to a good enough accuracy, and then round it to the nearest integer. It is important to note that this sort of sum does not often simplify in any reasonable sense; that is, if you can't explicitly compute the roots $\alpha_i$ (and you can't do so nicely in this case), then the above formula is as close to a closed form as you're going to get.
A: This is a linear recurrence for which you can get explicit solutions. The characteristic polynomial is $p(\lambda) = 3\lambda^3+2 \lambda^2+\lambda -1$. Computing its zeros, you see that is has a real root, $r$, and two complex conjugate roots $a\pm ib$. The general solution is then
$$
a_n = c_1 r^n + (a^2+b^2)^{n/2}(c_2 + \cos \omega n + c_3 \sin(\omega n))
$$
($\omega$ is the principal argument of $a+bi$)
The constants $c_1, c_2, c_3$ are computed from the initial conditions.
A: Given is the rational function
\begin{align*}
\color{blue}{A(x)=\frac{2x^2-x-2}{3x^3+2x^2+x-1}}\tag{1}
\end{align*}
We can derive from (1) a recurrence relation by recalling the following theorem:

Theorem: If a generating function has a representation as rational function of the form
\begin{align*}
A(x)=\sum_{n=0}^\infty a_n x^n=\frac{P(x)}{\color{blue}{Q(x)}}
\end{align*}
with $P(x), Q(x)$ polynomials, $\deg Q=q>\deg P$ and
\begin{align*}
\color{blue}{Q(x)=1+\alpha_1 x+\alpha_2 x^2+\cdots + \alpha_q x^q}
\end{align*}
then the coefficients $a_n$ follow the recurrence relation
\begin{align*}
\color{blue}{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.

Thanks to this theorem we write $A(x)$ as
\begin{align*}
A(x)=\frac{2+x-2x^2}{1-x-2x^2-3x^3}\tag{2}
\end{align*}
and derive the recurrence relation from the denominator of (2) as
\begin{align*}
a_{n+3}-a_{n+2}-2a_{n+1}-3a_n=0\qquad\qquad n\geq 0
\end{align*}

resp. by shifting the indices we get
\begin{align*}
\color{blue}{a_n}&\color{blue}{=a_{n-1}+2a_{n-2}+3_{n-3}\qquad\qquad n\geq 3}\\
\end{align*}

Initial conditions:
We want to find starting values $a_0,a_1$ and $a_2$. We get from (1)
\begin{align*}
A(x)\left(3x^2+2x^2+x-1\right)&=2x^2-x-2\\
\left(a_0+a_1x+a_2x^2+\cdots\right)\left(3x^2+2x^2+x-1\right)&=2x^2-x-2\tag{3}
\end{align*}

*

*We obtain from (3) by inspection:
\begin{align*}
a_0(-1)=-2\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\to\qquad \color{blue}{a_0=2}
\end{align*}


*In the following we use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ of a series. Putting $a_0=2$ we obtain from (3)
\begin{align*}
[x^1](2+a_1x)(x-1)&=-1\\
2-a_1&=-1\qquad\qquad\qquad\qquad\qquad\qquad\to\qquad \color{blue}{a_1=3}
\end{align*}


*Putting $a_0=2$ and $a_1=3$ we obtain from (3)
\begin{align*}
[x^2](2+3x+a_2x^2)\left(3x^2+2x^2+x-1\right)&=2\\
2\cdot 2+3\cdot 1+a_2(-1)&=2\qquad\qquad\qquad\to\qquad\color{blue}{a_2=5}\\
\end{align*}
and get finally the recurrence relation
\begin{align*}
\color{blue}{a_n}&\color{blue}{=a_{n-1}+2a_{n-2}+3_{n-3}\qquad\qquad n\geq 3}\\
\color{blue}{a_0}&\color{blue}{=2, a_1=3, a_2=5}\\
\end{align*}
