Extracting coefficients from 2-D generating function for recurrence relation

Question

We want to extract the coefficients for a recurrent relation from the 2-dimensional generating function $$G(x,y)=\frac{y^{n-1}(1-y)x}{xy^n-x-y+1}$$ where $n$ is a strictly positive integer constant.

I am able to perform the following manipulations: \begin{align} G(x,y) & = xy^{n-1}(1-y) \frac{1}{1-\left(x+y-xy^n\right)} \\ & = xy^{n-1}(1-y) \sum_{i=0}^{\infty}\left(x+y-xy^n\right)^i \\ & = xy^{n-1}(1-y) \sum_{i=0}^{\infty}\left(x\left(1-y^n\right)+y\right)^i \\ & = xy^{n-1}(1-y) \sum_{i=0}^{\infty}y^i\left(1+\frac{x\left(1-y^n\right)}{y}\right)^i \\ & = xy^{n-1}(1-y) \sum_{i=0}^{\infty}y^i\sum_{k=0}^i \binom{i}{k} \left(\frac{x}{y}\right)^k \left(1-y^n\right)^k \\ & = xy^{n-1}(1-y) \sum_{i=0}^{\infty}y^i\sum_{k=0}^i \binom{i}{k} \left(\frac{x}{y}\right)^k \sum_{j=0}^{\infty} \binom{k}{j} \left(-y^n\right)^j \\ \end{align}

such that the coefficient $[x^py^q]G(x,y)$ is $$ [x^py^q] xy^{n-1}(1-y) \sum_{i=0}^{\infty} y^i\sum_{k=0}^i \binom{i}{k} \left(\frac{x}{y}\right)^k \sum_{j=0}^{\infty} \binom{k}{j} \left(-y^n\right)^j $$ or $$ [x^{p-1}y^{q-n+1}] (1-y) \sum_{i=0}^{\infty} y^i\sum_{k=0}^i \binom{i}{k} \left(\frac{x}{y}\right)^k \sum_{j=0}^{\infty} \binom{k}{j} \left(-y^n\right)^j $$

Unfortunately I am not certain how to proceed further. All suggestions welcome.

Answer 1

Starting with OP's last line we obtain \begin{align*} \color{blue}{[x^{p-1}}&\color{blue}{y^{q-n+1}](1-y)\sum_{i=0}^{\infty} y^i\sum_{k=0}^i \binom{i}{k} \left(\frac{x}{y}\right)^k \sum_{j=0}^{\infty} \binom{k}{j} \left(-y^n\right)^j}\\ &=[y^{q-n+1}]\sum_{i=p-1}^\infty y^i\binom{i}{p-1}y^{1-p}\sum_{j=0}^\infty\binom{p-1}{j}(-1)^jy^{nj}(1-y)\tag{1}\\ &=\left([y^{q-n+1}]-[y^{q-n}]\right)\sum_{i=0}^\infty \binom{i+p-1}{p-1}y^i\sum_{j=0}^\infty\binom{p-1}{j}(-1)^jy^{nj}\tag{2}\\ &=\sum_{i=0}^{q-n+1}\binom{i+p-1}{p-1}[y^{q-n+1-i}]\sum_{j=0}^\infty\binom{p-1}{j}(-1)^jy^{nj}\\ &\qquad\quad-\sum_{i=0}^{q-n}\binom{i+p-1}{p-1}[y^{q-n-i}]\sum_{j=0}^\infty\binom{p-1}{j}(-1)^jy^{nj}\tag{3}\\ &=\sum_{i=0}^{q-n+1}\binom{q-n+p-i}{p-1}[y^{i}]\sum_{j=0}^\infty\binom{p-1}{j}(-1)^jy^{nj}\\ &\qquad\quad-\sum_{i=0}^{q-n}\binom{q-n+p-1-i}{p-1}[y^{i}]\sum_{j=0}^\infty\binom{p-1}{j}(-1)^jy^{nj}\tag{4}\\ &=\sum_{i=0}^{\left\lfloor\frac{q+1}{n}-1\right\rfloor}\binom{q-n+p-ni}{p-1}[y^{ni}]\sum_{j=0}^\infty\binom{p-1}{j}(-1)^jy^{nj}\\ &\qquad\quad-\sum_{i=0}^{\left\lfloor\frac{q}{n}-1\right\rfloor}\binom{q-n+p-1-ni}{p-1}[y^{ni}]\sum_{j=0}^\infty\binom{p-1}{j}(-1)^jy^{nj}\tag{5}\\ &\,\,\color{blue}{=\sum_{i=0}^{\left\lfloor\frac{q+1}{n}-1\right\rfloor}\binom{q+p-n(1+i)}{p-1}\binom{p-1}{i}(-1)^i}\\ &\qquad\quad\color{blue}{-\sum_{i=0}^{\left\lfloor\frac{q}{n}-1\right\rfloor}\binom{q+p-1-n(1+i)}{p-1}\binom{p-1}{i}(-1)^i}\tag{6}\\ \end{align*}

Comment:

• In (1) we select the coefficient of $x^{p-1}$ and note that $i$ has to be greater or equal to $p-1$ for a non-zero contribution.

• In (2) we shift the index to start with $i=0$ and take the factor $1-y$ for the coefficient of operator.

• In (3) we apply the rule $[y^{p-q}]A(y)=[y^p]y^qA(y)$ and set the upper limits of the sums accordingly to avoid terms which do not contribute.

• In (4) we change the order of summation $i\to q-n+1-i$ and $i\to q-n-i$ to conveniently select coefficients in the following steps.

• In (5) we replace $i$ with $ni$ noting that we need coefficients of multiples of $n$ due to $y^{nj}$. We set the upper limits of the sums accordingly.

• In (6) we finally select the coefficient of $y^{ni}$.