Methods for solving two variable recurrence 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.]
 A: This problem has a probabilistic interpretation. Namely, if one considers the Markov chain on the integer points in the rectangle $[0,N]\times [0,M]$ with the transition probabilities
$$
p\bigl((i,j),(i,j-1)\bigr) = \frac{N-i}{N} \;, \qquad p\bigl((i,j),(i-1,j)\bigr) = \frac{i}{N} \;,
$$
then $f(i,j)$ is the expected number of steps until the chain attains the horizontal line $\{j=0\}$ where it is absorbed. Now, the $i$ component of this chain is the Markov chain on $[0,N]$ with the transition probabilities
$$
p(i,i) = \frac{N-i}{N} = p_i \;, \qquad p(i,i-1) = \frac{i}{N} = 1-p_i\;,
$$
which can be interpreted as the deterministic chain $i\to i-1$ with additional "holding" at each state. The distribution of this holding time at a point $i$ is geometric with the parameter $1-p_i$, i.e., the holding time is 0 with probability $1-p_i$, is 1 with probability $p_i(1-p_i)$, etc. Thus, the expectation of the holding time at point $i$ is $p_i/(1-p_i)$, and the expected vertical displacement of the original chain provided its horizontal component attains a point $t\in [0,n]$ is
$$
M_t=\frac{p_N}{1-p_N} + \dots + \frac{p_t}{1-p_t} = \frac{1}{N-1} + \dots + \frac{t}{N-t} \sim \int_0^t \frac{x}{N-x}dx = N\log\frac{N}{N-t}-t \;.
$$ 
In particular, if $t$ is close to $N$, then $M_t\gg N>M$, which means that our chain most likely becomes absorbed before it attains the vertical segment $\{i=0\}$. [More rigorously here one should also estimate the variance of the vertical displacement to make sure it does not differ much from $M_t$.]
Now the equation
$$
M = N\log\frac{N}{N-t}-t
$$
will give us the likely number of horizontal steps $t$ necessary to have vertical displacement $M$, i.e., to be absorbed. The total expected time before absorption will be therefore
$$
f(N,M)=M + t = N\log\frac{N}{N-t} \;.
$$ 
The above equation can be rewritten as
$$
\frac{M}{N} = -\log (1-t/N) - t/N \;.
$$
Under the assumption that $M \ll N$ (i.e., $t \ll N$) one can expand the log in the RHS, which gives
$$
\frac{M}{N} \approx \frac{t^2}{2N^2} \;, 
$$ 
whence $t\approx\sqrt{2MN}$ and $f(N,M)\approx\sqrt{2MN}$.
A: 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}}$$
