Two-dimensional recurrence $a_{m,k}=a_{m-1,k}+a_{m-1,k-1}$

Question

Can someone using only these conditions

$$a_{m,k}=a_{m-1,k}+a_{m-1,k-1},m>k$$
$$a_{m,k}=1,m=k$$
$$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.

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 04 '11 at 14:27

Did · Accepted Answer · 2011-12-04T15:32:47.930

4

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}$.

edited Dec 04 '11 at 15:32

answered Dec 04 '11 at 14:27

Did

279,727

Two-dimensional recurrence $a_{m,k}=a_{m-1,k}+a_{m-1,k-1}$

1 Answers1