Generating function coefficient

Question

I have a generating function $\frac{1}{(1-x-x^{3}+x^{4})^{2}}$. I have to find the $x^{n}$ coefficient. So far it seems that the next step is to convert this function back to the sequence, but I am not sure how to proceed.

Answer 1

One route is via the inverse-Z transform of $G(1/x)$ with $$ G(x) = \frac{1}{(1-x-x^3+x^4)^2} = 1 + 2 x + 3 x^2 + 6 x^3 + \cdots $$ For an ordinary generating function of the form $$ G(x) = \sum_{k=0}^\infty a_k x^k $$ we can use the transform defined as $$ \mathcal{Z}^{-1} \{X(z) \}= \frac{1}{2 \pi j} \oint_{C} X(z) z^{n-1} dz $$ to get $$ a_n = \mathcal{Z}^{-1}[G(1/x)] $$ In this case (using Mathematica's InverseZTransform routine) we have $$a_n= \frac{1}{54} \left((n+4) (n (n+8)+11)+\frac{2 (3 n+11) \sin \left(\frac{2 \pi n}{3}\right)}{\sqrt{3}}+2 (n+5) \cos \left(\frac{2 \pi n}{3}\right)\right) $$

there may be a way to simplify this further. The key thing is that this transform is exactly the map between generating functions and their $x^n$ coefficients. But computing the integral can be non-trivial for complicated generating functions, so computers can be useful for these calculations.

Answer 2

First note that $$1-x-x^3+x^4=(1-x)(1-x^3)=(1-x)^2(1+x+x^2)\,,$$

so if nothing else, you can decompose

$$\frac1{(1-x)^4(1+x+x^2)^2}$$

into partial fractions and go from there. Alternatively, you can work with

$$\frac1{(1-x)^2}\cdot\frac1{(1-x^3)^2}\,.$$

It’s standard that

$$\frac1{(1-x)^2}=\sum_{n\ge 0}(n+1)x^n\,,$$

so

$$\begin{align*} \frac1{(1-x^3)^2}&=1+2x^3+3x^6+4x^9+\ldots\\ &=\sum_{n\ge 0}a_nx^n\,, \end{align*}$$

where

$$a_n=\begin{cases} k+1,&\text{if }n=3k\\ 0,&\text{otherwise.} \end{cases}$$

Now use the fact that

$$\frac1{1-x}\sum_{n\ge 0}b_nx^n=\sum_{n\ge 0}\left(\sum_{k=0}^nb_k\right)x^n$$

for any power series $\sum_nb_nx^n$ to see that

$$\begin{align*} \frac1{(1-x)(1-x^3)^2}&=1+x+x^2+3x^3+3x^4+3x^5+6x^6+\ldots\\ &=\sum_{n\ge 0}\binom{\lfloor n/3\rfloor+2}2x^n \end{align*}$$

and hence that

$$\frac1{(1-x)^2(1-x^3)^2}=\sum_{n\ge 0}\sum_{k=0}^n\binom{\lfloor k/3\rfloor+2}2x^n\,.$$

Finally, if $n=3m+r$ for $\in\{0,1,2\}$, then

$$\begin{align*} \sum_{k=0}^n\binom{\lfloor k/3\rfloor+2}2&=3\sum_{k=0}^{m-1}\binom{k+2}2+(r+1)\binom{m+2}2\\ &=3\binom{m+2}3+(r+1)\binom{m+2}2\\ &=3\binom{m+3}3-(2-r)\binom{m+2}2\,. \end{align*}$$

Expressed directly in terms of $n$ this is

$$3\binom{\lfloor n/3\rfloor+3}3-\big(2-(n\bmod 3)\big)\binom{\lfloor n/3\rfloor+2}2\,.$$

For example, the coefficient of $x^{10}$ is

$$3\binom63-(2-1)\binom52=60-10=50\,.$$