Extracting coefficients from two-dimensional generating function

Question

We have the two-dimensional recurrent series $F(r+1,s+2) = F(r,s) + F(r,s+1) + F(r,s+2)$ and the boundary conditions $F(r,0)=1$, $F(0,s)=0$ for all $s>0$ and $F(0,0)=1$ and $F(r,1)=r$. This series is for all $r\geq0$ and $s\geq0$. How do we find the general expression for the coefficient?

I used the 2D generating function $G(x,y) = \sum_{r,s\geq0} F(r,s) x^r y^s$ and applied the boundary conditions to obtain the following expression for G:

$$G(x,y) = \frac{xy}{(x-1)(1-x-xy-xy^2)}$$

which I can split to obtain

$$G(x,y) = \frac{-1}{1-x} \frac{xy}{1-x-xy-xy^2}$$

and the term $\frac{-1}{1-x}$ can be expressed as $-(1+x+x^2+x^3+\dots)$. I am having problems with the other term $\frac{xy}{1-x-xy-xy^2}$.

I referred to this post which handled a bivariate generating function but unfortunately I couldn't recast $\frac{xy}{1-x-xy-xy^2}$ into a term similar to $\frac{1}{1-y(x+1)}$ which was presented there. The closest I could get was:

$$\frac{xy}{1-x-xy-xy^2} = \frac{xy}{1-x(y^2+y+1)} = \frac{xy}{1-x[(y+1)^2-y]}$$

which is again not similar to the expression $H(x,y) = \frac{xy}{1-x-y}$ in this post.

All suggestions welcome.

Answer 1

We use the coefficient of operator $[z^n]$ do denote the coefficient of $z^n$ in a series.

We obtain for $m,n\geq 1$:

\begin{align*} \color{blue}{[x^my^n]}&\color{blue}{\frac{xy}{1-x(1+y+y^2)}}\\ &=[x^{m-1}y^{n-1}]\frac{1}{1-x(1+y+y^2)}\tag{1}\\ &=[x^{m-1}y^{n-1}]\sum_{j=0}^\infty x^j\left(1+y+y^2\right)^j\tag{2}\\ &=[y^{n-1}](1+y+y^2)^{m-1}\tag{3}\\ &=[y^{n-1}]\sum_{j=0}^{m-1}\binom{m-1}{j}y^j(1+y)^j\tag{4}\\ &=\sum_{j=0}^{\min\{m-1,n-1\}}\binom{m-1}{j}[y^{n-1-j}](1+y)^j\tag{5}\\ &\,\,\color{blue}{=\sum_{j=0}^{\min\{m-1,n-1\}}\binom{m-1}{j}\binom{j}{n-1-j}}\tag{6}\\ \end{align*}

Comment:

• In (1) we use the rule $[z^{p-q}]A(z)=[z^p]z^qA(z)$.

• In (2) we do a geometric series expansion.

• In (3) we select the coefficient of $x^{m-1}$.

• In (4) we apply the binomial theorem.

• In (5) we apply the rule from (1) again. We also set the upper limit of the sum accordingly, since the exponent of $y^{n-1-j}$ is non-negative.

• In (6) we select the coefficient of $y^{n-1-j}$.