# Generating Function for Recurrence Relation in 2 Variable

I have a recurrence relation with 2 variables similar to $$F(n,m) = n\cdot F(n-1,m) + (n-m)\cdot F(n-1,m-1)$$ I want to know the steps required to get the generating Function for such recurences. I have gone through a similar post : Solving recurrence relation in 2 variables . But how do I solve when there is a multiplication as in the above equations ?

• Related to OEIS A078341, which does not give a generating function. – Henry Feb 22 '14 at 16:09
• @Henry The recurrence relation that I am trying to solve is actually more complex than the one mentioned in my question. Which is why I am looking for the steps I can take to solve similar questions. – Kyuubi Feb 22 '14 at 16:17

## 1 Answer

The strategy is to look for the generating function $$G(x,y)=\sum_{n,m}F(n,m)x^ny^m.$$ To do so:

• Multiply by $x^ny^m$ each term in the identity, getting $$F(n,m)x^ny^m = n\cdot F(n-1,m) x^ny^m+ (n-m)\cdot F(n-1,m-1)x^ny^m.$$
• The LHS terms sum to the generating function $G(x,y)$.
• For the first terms on the RHS, use the identity $$nx^ny^m=\left(x^2\cdot\frac{\partial}{\partial x}+x\right) x^{n-1}y^m.$$
• For the second terms on the RHS, use the identity $$(n-m)x^ny^m=xy\cdot\left(x\frac{\partial}{\partial x}-y\frac{\partial}{\partial y}\right) x^{n-1}y^{m-1}.$$
• Deduce that $$G(x,y)=x^2\cdot\frac{\partial G(x,y)}{\partial x}+xG(x,y)+x^2y\cdot\frac{\partial G(x,y)}{\partial x}-xy^2\frac{\partial G(x,y)}{\partial y}+H(x,y),$$ where $H(x,y)$ is a polynomial correction due to the terms of low degrees in the sums.

Whether this PDE can be solved is another story.

• How would I calculate $H(x,y)$ ? – Kyuubi Feb 22 '14 at 18:50
• Looking at the terms of low degrees. – Did Feb 22 '14 at 19:06