How to obtain generating function and an analytic solution

Question

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.

score 1 · Answer 1 · answered Jul 04 '13 at 08:39

1

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

answered Jul 04 '13 at 08:39

Boris Novikov

17,470

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

How to obtain generating function and an analytic solution

1 Answers1