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).

  • $\begingroup$ I'm guessing that $f(n,m)=0$ for $m>n$. Is it right? $\endgroup$ – Bill O'Haran May 9 '18 at 12:05
  • 1
    $\begingroup$ IMO it is not well-defined: By the first equation $f(0,0)=1$ and by the second $f(0,0)=0$. $\endgroup$ – gammatester May 9 '18 at 12:46
  • $\begingroup$ Assume that we care only about values n > m. We definitely don't care about f(0,0) $\endgroup$ – peter.petrov May 9 '18 at 12:51
  • $\begingroup$ Can you edit the question then, as the recurrence is now meaningless $\endgroup$ – ancientmathematician May 9 '18 at 12:53
  • $\begingroup$ @gammatester First formula takes priority then second then third. $\endgroup$ – peter.petrov May 9 '18 at 12:55

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).

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.