# 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?

• Have you tried partial fractions? Sep 26, 2022 at 15:31
• I wrote it as $A(x)= \dfrac{2x^2}{3x^3+2x^2+x-1}- \dfrac{x}{3x^3+2x^2+x-1}-\dfrac{2}{3x^3+2x^2+x-1}$ but I don't know how to continue. Sep 26, 2022 at 15:34
• Find the power series of $A$ and identify coefficients. However they might be quite ugly... Sep 26, 2022 at 17:29
• The coefficients of $A(x)$ do have an explicit representation, but as Lelouch alludes to, it can be very complicated and unenlightening. I have provided such a representation in my answer. Sep 26, 2022 at 17:52
• Try $a_n=r^n$... Sep 26, 2022 at 19:06

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.

• Thank you - that was exactly what I was asking. Two questions: - What does the notation $[x^n]$ mean? If I understand this, the second question is maybe not necessary. - How do you derive for example $[x^n]\frac{1}{x-\alpha_1}=-\frac{1}{\alpha_1^{n+1}}$? Do you use $\frac{1}{1-q}=1+q+q^2+\ldots$? Sep 26, 2022 at 21:23
• @garondal The notation $[x^n]f(x)$ is a very common shorthand for the $n$-th coefficient of the generating function $f(x)$ (you'll see it a lot in the future). Written more formally, if $f(x)=\sum_{n=0}^\infty f_n x^n$ then $[x^n]f(x)=f_n$. So for example, $[x^3](1+x^2−7x^3+4x^5)=−7$ and $[x^n]e^x=\frac{1}{n!}$. $\tag*{}$For your second question, yes; just notice that $\frac{1}{x-a}=-\frac{1/a}{1-x/a}=-\frac{1}{a}\sum_{n=0}^\infty\left(\frac{x}{a}\right)^n$, so $-\frac{1}{a^{n+1}}$ is the $n$-th coefficient of $\frac{1}{x-a}$. Sep 26, 2022 at 23:06

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.

• Thanks, I know that I could do this but I wanted to know if it is possible to derive this using the generating function? Sep 26, 2022 at 15:26

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

• That's quite literally the recurrence relation the asker started with. The asker already knows this , and transformed the problem into a problem about the generating function $A(x)$ so they could obtain a closed form that was not this recurrence relation. This does not answer the asker's question at all. Sep 26, 2022 at 18:48
• @C-RAM: I don't agree. I think OP is precisely asking for a theorem which I've stated in my answer. Sep 26, 2022 at 18:51

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

• My high school friend Zapata gave -1. Sep 26, 2022 at 21:24