How to obtain generating function and an analytic solution

I have the following recurrence relation, and I need to obtain generating function and an analytic solution. How to go about with it?

$$f(N,M) = 0, N < M\\ f(N+1,M+1) = 2f(N,M) + (N-1)f(N,M+1), N > 0, M > 0\\ f(1,1) = 1\\ f(N,1) = 0, N > 1\\$$

PS: this is not homework. A problem I encountered during a discussion.

Thanks.

-

1 Answer

Hint: Denote $F(x,y)=\sum_{N,M\ge 1}f_{N,M}x^Ny^M$. If I'm not mistaken in calculations, then $$F=1+2xyF-xF+ x^2\frac{\partial F}{\partial x}.$$

-
+1. Thank you, Boris. Any further simplification please? –  Qiang Li Jul 4 '13 at 16:30
No proposals. I think one should decide this differential equation for fixed $y$. –  Boris Novikov Jul 4 '13 at 16:44