While doing some combinatorial counting I found this
recurrence which I do not know how to solve.
$f(n, 0)=1, n \ge 0 $
$f(n, n)=0, n \gt 0 $
$f(n,m) = f(n-1, m) + f(n, m-1), for \ n \gt m \gt 0 $
I did all sorts of things I could think of.
I think it can be expressed with some binomial coefficients
(of $n$ and $m$ of course).
OK... thanks for all the hints posted as comments.
After reading the Wikipedia article on "Bertrand's ballot theorem" (and especially Andre's proof), I finally found what the closed formula is and I was able to verify that it satisfies my recurrence equations. It is this one.
So turns out I was on the right track with these recurrence equations after all.
But yeah... there's no way I could have inferred this closed formula from them by myself.
${n+m \choose m} - 2 \cdot {n+m-1\choose m-1} $
Now I am just side thinking... I wonder if in general there's any way of finding/inferring such closed formulas just from the recurrence equations (i.e. without any combinatorial thoughts/arguments).