1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you for this beautiful derivation! I have a quick question: what would happen in step (2) if the rule $[z^{p-q}]A(z) = [z^p]z^q A(z)$ had been applied to $x$? Would this change the result since the expression becomes $[y^{n-1}]\sum_{j=0}^{\infty} [x^{m-1-j}] (1+y+y^2)^j$? $\endgroup$ – MrABBA Apr 19 at 14:34
  • 1
    $\begingroup$ @MrABBA: You're welcome. In (2) there is only $j=m-1$ to consider, since other values of $j$ do not contribute to $x^{m-1}$. This situation is different to (5) where we additionally have $(1+y)^j$ which also do contribute. In (2) we have accordingly to the rule (1) the situation $[x^{m-1}]x^{m-1}=[x^0]$ which is the constant part and needs not be explicitly written. $\endgroup$ – Markus Scheuer Apr 19 at 14:43
  • 1
    $\begingroup$ @MrABBA: We can write your example in the comment as $[y^{n-1}]\sum_{j=0}^{\infty}[x^{m-1-j}]x^0(1+y+y^2)^j=[y^{n-1}](1+y+y^2)^{m-1}$ since $j$ has to be $m-1$ whereas terms with other values of $j$ do not contribute. $\endgroup$ – Markus Scheuer Apr 19 at 14:51

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.