How to solve for the analytic solution of a recurrence relation in mathematica -

i have recurrence such following:

rsolve[{f[m, n] == f[m, n - 1] + f[m - 1, n],          f[0, n] == 1, f[m, 0] == 1},          f[m, n], {n}] 

i tried use rsolve, got error:

rsolve::deqx: supplied equations not difference equations                of given functions. 

appreciate help!

the difference equation , initial conditions

mathematica (7 , 8) not solving it... both , without initial conditions. rsolve expressions left unevaluated

in[1]:= rsolve[{f[m,n]==f[m,n-1]+f[m-1,n],f[0,n]==f[m,0]==1},f[m,n],{m,n}]         rsolve[{f[m,n]==f[m,n-1]+f[m-1,n]},f[m,n],{m,n}] out[1]= rsolve[{f[m,n]==f[-1+m,n]+f[m,-1+n],f[0,n]==f[m,0]==1},f[m,n],{m,n}] out[2]= rsolve[{f[m,n]==f[-1+m,n]+f[m,-1+n]},f[m,n],{m,n}] 

i know mathematica uses generating functional methods (probably among other things) solve such recurrences, don't know why fails in such simple case.

so let's hand.

let g(x,n) generating function f(m,n)

now examine sum of f(m+1,n) x^m

now solve simple algebraic-difference equation:

which can done rsolve

in[3]:= rsolve[g[x,n]-x g[x,n]==g[x,n-1]&&g[x,0]==1/(1-x),g[x,n],n];         simplify[%,element[n,integers]] out[4]= {{g[x,n]->(1-x)^(-1-n)}} 

now extract coefficient of x^m:

in[5]:= seriescoefficient[(1 - x)^(-1 - n), {x, 0, m}] out[5]= piecewise[{{(-1)^m*binomial[-1 - n, m], m >= 0}}, 0] 

the binomial simplified using

in[6]:= fullsimplify[(-1)^m*binomial[-n - 1, m] == binomial[m + n, m], element[{n,m}, integers]&&m>0&&n>0 ] out[6]= true 

so

this can checked using symbolic , numeric means

in[7]:= ff[m_,n_]:=ff[m,n]=ff[m-1,n]+ff[m,n-1]         ff[0,_]:=1;ff[_,0]:=1 in[9]:= and@@flatten[table[ff[m,n]==binomial[n+m,m],{n,0,20},{m,0,20}]] out[9]= true  in[10]:= {f[m,n]==f[m,n-1]+f[m-1,n],f[0,n]==f[m,0]==1}/.f->(binomial[#1+#2,#1]&)//fullsimplify out[10]= {true,true}