Find a closed form solution of the recurrence f(a, b) = f(a, b-1) + f(a-1, b-1) with base cases f(0, 0) = 1, f(k, 0) = 1, f(0, k) = 0 (k>0).

Question

I made a matrix for the values of a and b and tried to compute $f(a,b)$. I observed that $f(a,b)=2^b$ for b $\le$ a. But for a given value of a($\gt 1$), $f(a,b)$ seems to follow a strange progression for b $\ge$ a. Anyone has any strategy for this problem?

Answer 1

The answer will be the following:

$f(a,b) = 2\sum_{n=0}^{a-1}\binom{b-1}{n}$, where $a,b\ge1$ and $\binom{m}{n}=0$, if $m<n$.

Now one can check this using induction. I got this formula by considering the differences $f(a+1,b)-f(a,b)$ and it was not very hard to find a general formula for them just by guessing and then proving by induction.

And according to the wikipedia page (http://en.wikipedia.org/wiki/Binomial_coefficient) of the binomial coefficients, there is no closed form for this function.