Get closed form from a complicated closed-form generating function

Question

I have a closed form for a generating function:

$A(x)=\frac{x(x-1)(x+1)^3(x^3-x-1)}{(x^3+x^2-1)^2}$

The coefficient of $x^n$ in the above represents $a_n$ (the $n^{th}$ term of a sequence). I want a closed form for the sequence $a_n$. For example, the expansion done in:

http://www.wolframalpha.com/input/?i=x%5E2(1%2Bx%2B(x%5E2(x%2B1)%5E2)%2F(1-x%5E2-x%5E3))%2Bx*(1%2Bx%2B(x%5E2*(x%2B1)%5E2)%2F(1-x%5E2-x%5E3))(x%5E2%2Bx%5E2(1%2Bx%2B(x%5E2*(x%2B1)%5E2)%2F(1-x%5E2-x%5E3)))%2Bx%2B(x%5E2%2Bx%5E2*(1%2Bx%2B(x%5E2*(x%2B1)%5E2)%2F(1-x%5E2-x%5E3)))

shows the first few coefficients: $x+3x^2+4x^3+5x^4+8x^5+O(x^6)$. But I want a closed form for the general $n^{th}$ term $a_n$. What method should I use to get it?

Answer 1

Convert $A(x)$ to partial fractions: if $r_1,r_2,r_3$ are the roots of $x^3+x^2-1$ (which is irreducible over the rationals):

$$ A(x) = {x}^{2}-2+\sum _{j=1}^3{\frac {-{r_j}^{2}+2\,r_j+2}{23\; \left( x-r_j \right) ^ {2}}}+\sum _{j=1}^3 \frac{-75\; r_j^2-370\; r_j + 78}{529\;(x-r_j)} $$ and then use the Maclaurin series for $1/(x-r_j)$ and $1/(x-r_j)^2$.

Answer 2

Hint: Though not a closed form we can use the binomial series expansion to derive an alternate explicit expression for $[x^n]A(x)$, the coefficient of $x^n$ of $A(x)$.

At first we write $A(x)$ with increasing powers of the denominator $1-x^2-x^3$. We obtain using the Euclidian algorithm for polynomials: \begin{align*} A(x)&=\frac{x(x-1)(x+1)^3(x^3-x-1)}{(x^3+x^2-1)^2}\\ &=\frac{x^8+2x^7-x^6-5x^5-3x^4+2x^3+3x^2+x}{(x^3+x^2-1)^2}\\ &=\cdots\\ &=x^2-2-\frac{x^2-x}{1-x^2-x^3}+\frac{x^2+x}{\left(1-x^2-x^3\right)^2}\tag{1} \end{align*}

Next we calculate the coefficient of $x^n$ of $\frac{1}{(1-x^2-x^3)^\alpha}$ which we need with $\alpha\in\{0,1\}$.

We obtain \begin{align*} [x^n]\frac{1}{\left(1-x^2-x^3\right)^{\alpha}}&=[x^n]\frac{1}{\left(1-x^2\left(1+x\right)\right)^{\alpha}}\\ &=[x^n]\sum_{j=0}^\infty\binom{-\alpha}{j}(-1)^jx^{2j}(1+x)^j\tag{2}\\ &=\sum_{j=0}^{\left\lfloor\frac{n}{2}\right\rfloor}\binom{\alpha+j-1}{j}[x^{n-2j}](1+x)^j\tag{3}\\ &=\sum_{j=0}^{\left\lfloor\frac{n}{2}\right\rfloor}\binom{\alpha+j-1}{j}\binom{j}{n-2j}\tag{4} \end{align*}

Comment:

• In (2) we apply the binomial series expansion of $(1+z)^{\alpha}$ with $z=-x^2(1+x)$.

• In (3) we use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$.

• In (4) we select the coefficient of $x^{2j}$ and set the upper bound of the series to $\left\lfloor\frac{n}{2}\right\rfloor$ since the coefficient of $[x^{n-2j}]$ has to be non-negative.

From (1) and (4) we obtain the coefficient of $A(x)$ as \begin{align*} \color{blue}{[x^n]A(x)}&=[x^n]\left(x^2-2\right)-\left([x^{n-2}]-2[x^n]\right)\frac{1}{1-x^2-x^3}\\ &\qquad+\left([x^{n-2}]+[x^n]\right)\frac{1}{\left(1-x^2-x^3\right)^2}\tag{5}\\ &=[[n=2]]-2[[n=0]]-\left([x^{n-2}]-2[x^n]\right)\sum_{j=0}^{\left\lfloor\frac{n}{2}\right\rfloor}\binom{j}{n-2j}x^j\\ &\qquad+\left([x^{n-2}]-[x^{n-1}]\right)\sum_{j=0}^{\left\lfloor\frac{n}{2}\right\rfloor}(j+1)\binom{j}{n-2j}x^j\tag{6}\\ &\color{blue}{=[[n=2]]-2[[n=0]]+2\sum_{j=0}^{\left\lfloor\frac{n}{2}\right\rfloor}\binom{j}{n-2j}}\\ &\qquad\color{blue}{+\sum_{j=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}(j+1)\binom{j}{n-1-2j} +\sum_{j=0}^{\left\lfloor\frac{n}{2}-1\right\rfloor}j\binom{j}{n-2-2j}}\tag{7} \end{align*}

Comment:

• In (5) we use the linearity of the coefficient of operator.

• In (6) we use the Iverson brackets $[[P]]$ which is $1$ if and only if the proposition $P$ is true and $0$ otherwise. We also use the representation of the coefficients from (2).

• In (7) we select the coefficients accordingly and collect corresponding terms.

Note: The sequence $\left(\sum_{j}\binom{j}{n-2j}\right)_{n\geq 0}=(1,0,1,1,1,2,2,3,4,5,7,9,12,16,\ldots)$ is archived in OEIS as A000931.