I have a recurrence 


$$f(i,j) = 1+ \frac{N-i}{N} f(i,j-1) + \frac{i}{N} f(i-1, j)$$


$$f(i,0) = 0$$
$$f(0,j) = j$$


I would like to compute $f(N,M)$ in terms of N and M. The system is defined for $0\leq i\leq N$ and $0\leq j\leq M$ where $N$ and $M$ are non-negative integers. 


I am familiar with techniques for solving single variable recurrences but cannot see how to extend them to this situation. Is there some generating function solution one can write down? Is it known how to solve this sort of recurrence?


By a hand wavy argument I believe the solution looks asymptotically roughly like $c\sqrt{NM}$ for some constant $c$, when $N > M$. 


[Fixed typo in question.]



Methods for solving two variable recurrence
You have $f(0,j) = 1 + f(0,j-1)$ so $f(0,j) = j$. I get


$$f(1,j) = j + 1 - \left(\frac{N-1}{N}\right)^j $$


$$ f(2,j) = j + 2 - 2 \frac{(N-1)^{j+1}}{N^{j+1}} - 2 \frac{(N-2)^j}{N^{j+1}}$$


$$ f(3,j) = j + 3 - 3 \frac{(N-1)^{j+2}}{N^{j+2}} - 6 \frac{(N-2)^{j+1}}{N^{j+2}} - 9 \frac{(N-3)^j}{N^{j+2}}$$


$$ f(4,j) = j + 4 - 4 \frac{(N-1)^{j+3}}{N^{j+3}} - 12 \frac{(N-2)^{j+2}}{N^{j+3}} - 36 \frac{(N-3)^{j+1}}{N^{j+3}} - 64 \frac{(N-4)^{j}}{N^{j+3}}$$


It looks like $$f(i,j) = i + j - \sum\_{k=1}^i k^{k-1} {i \choose k} \frac{(N-k)^{i+j-k}}{N^{i+j-1}}$$


