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 ?

  • $\begingroup$ Related to OEIS A078341, which does not give a generating function. $\endgroup$ – Henry Feb 22 '14 at 16:09
  • $\begingroup$ @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. $\endgroup$ – Kyuubi Feb 22 '14 at 16:17

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.

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

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.