Find sequence from the generating function $ A(x)= \dfrac{2x^2-x-2}{3x^3+2x^2+x-1}$

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

That's how I learned to solve these equations in high-school:

I assume $a_n=r^n$ then the recursive equation of the sequence gives $r^3-r^2-2r-3=0$. Its roots are approximately found by WA: $r_1\approx 2.3744$, $r_2,3\approx -0.6872\pm0.8895i$.

Hence, by theory, $a_n\approx c_1(2.3744)^n+c_2(-0.6872-0.8895i)^n+c_3(-0.6872+0.8895i)^n$.

From the initial conditions, $a_0=2,a_1=3,a_2=5$, WA found $c_1\approx 1.14615$, $c_2\approx 0.426927+0.466434i$ and $c_3\approx 0.426927-0.466434i$ which is the conjugate of $c_2$.

Thus, $a_n\approx (1.14615)(2.3744)^n+2\Re{ \large( (0.426927+0.466434i)(-0.6872-0.8895i)^n \big)}$

Ex: https://www.wolframalpha.com/input?i=1.14615*2.3744%5E3%2B%280.4269%2B0.4864i%29*%28-0.68721-0.8895i%29%5E3%2B%280.4269-0.4864i%29*%28-0.68721%2B0.8895i%29%5E3