Solving a Recurence Relation with 2 parameters

Question

Given the following recurrence relation

$$u(n,1) = 1$$ $$u(1,m) = 1$$ $$u(n,m) = u(n-1, m) + u(n, m-1)$$

with $n > 0, m > 0$,

how can one end up with a closed formula, without using generating functions?

Answer 1

If you compute $u(n,m)$ for e.g. $1\leqslant n,m\leqslant 6$ you should see a pattern. In particular, look at the diagonals where $n+m=k$ for $k=1,2,\ldots$. I came up with

$$\displaystyle u(n,m) = \binom{n+m}n,$$

which clearly satisfies the recurrence, as

$$\displaystyle\binom{n+m}n = \binom{n+m-1}{n-1} + \binom{n+m-1}n.$$