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?
Best Answer
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.