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.


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


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

  • $\begingroup$ 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}$? $\endgroup$ – MrABBA May 11 at 16:42
  • $\begingroup$ @MrABBA: Good review. Thanks for pointing at the mistake. Corrected. $\endgroup$ – Markus Scheuer May 11 at 17:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.