# two-dimensional recurrence

Can someone using only these conditions

1. $$a_{m,k}=a_{m-1,k}+a_{m-1,k-1},m>k$$

2. $$a_{m,k}=1,m=k$$

3. $$a_{m,k}=0,m<k$$

prove that

$$a_{m,k}=\frac{m!}{k!(m-k)!}$$

here is way to construct Pascal triangle. I am interested to view direct proof. I read many books on combinatorics and nowhere such proof is done yet.

-
Hint: use induction on $m$. – Levon Haykazyan Dec 4 '11 at 14:23
Let $b_{m,k}=\frac{m!}{k!(m-k)!}$. We need to verify that $b_{m,k}$ satisfies same recurrence, initial conditions as $a_{m,k}$. This is a calculation. – André Nicolas Dec 4 '11 at 14:27

Hints: consider the formal series $a_m(x)=\sum\limits_{k}a_{m,k}x^k$. Show that $a_m(x)=\sum\limits_{k=0}^ma_{m,k}x^k$ for every $m\geqslant0$. Show that $a_0(x)=1$ and $a_m(x)=(1+x)a_{m-1}(x)$ for every $m\geqslant1$. Deduce that, for every $m\geqslant0$, the relation $a_m(x)=(1+x)^m$ holds, and finally, the value of every $a_{m,k}$.