# Extracting coefficients from 2-D generating function for recurrence relation

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.

## 1 Answer

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

• Thank you for this clear derivation and detailed explanation! Quick question: from (1) to (2) $i$ is re-indexed to $0$, why does $\binom{i}{p-1}$ remain the same instead of becoming $\binom{i+p-1}{p-1}$? – MrABBA May 11 at 16:42
• @MrABBA: Good review. Thanks for pointing at the mistake. Corrected. – Markus Scheuer May 11 at 17:04