Problem 1267

First solution (by Yassine Hamdi) Consider a group of $\mathrm{m}$ girls and $\mathrm{n}$ boys and count in two ways the number of ways to choose a subgroup of $n$ people. On the one hand, this number is clearly $\binom{m+n}{n}$. On the other hand, choosing this subgroup amounts to first choosing the number $k$ of girls who will be in it $(0 \leqslant k \leqslant m)$, then choosing the girls $\left(\binom{m}{k}\right.$ choices), then the boys $\left(\binom{n}{n-k}\right.$ choices). Thus:

$$\binom{m+n}{m}=\sum_{k=0}^{m}\binom{m}{k}\binom{n}{n-k}=\sum_{k=0}^{m}\binom{m}{k}\binom{n}{k}$$

where we used the fact that $\binom{n}{n-k}=\binom{n}{k}$ for the second equality.

Second solution (by Hizir Nuhoglu) Consider a rectangle of length $n$ and width $\mathrm{m}$: We are interested in the paths starting from the bottom left vertex (coordinates $(0,0)$) and

ending at the top right (coordinates $(\mathfrak{n}, \mathfrak{m})$) by making only unit steps to the right or up. According to a TD exercise, their number is $\binom{m+n}{m}$. On the other hand, any of these paths crosses a point with coordinates $(k, m-k)$ with $0 \leqslant k \leqslant m$ (points on the red diagonal in the figure). The number of paths from $(0,0)$ to $(k, m-k)$ is $\binom{m}{k}$, and the number of paths from $(k, m-k)$ to $(n, m)$ is $\binom{n}{n-k}=\binom{n}{k}$. Thus

$$\binom{m+n}{m}=\sum_{k=0}^{m}\binom{m}{k}\binom{n}{k}$$

Third solution and generalization (by Nicolas Heutte) If we consider $m+1$ numbers in a row $a_{0}, a_{1}, \ldots, a_{m}$ and form a "descending" Pascal's triangle from this original row, the $m+1$-th row will contain a single number which is

$$a_{0}\binom{m}{0}+a_{1}\binom{m}{1}+\cdots+\cdots a_{m}\binom{m}{m}$$

We perform this operation starting from the $m+1$ first numbers of the n-th row of Pascal's triangle, which are $\binom{n}{0},\binom{n}{1}, \ldots,\binom{n}{m}$. We obtain that the number on the $n+m-1$-th row in the $m$-th place is

$$\sum_{k=0}^{m}\binom{m}{k}\binom{n}{k}$$

By construction of Pascal's triangle, this number is also $\binom{m+n}{m}$, which concludes.

It is possible to generalize this formula: let $u \geqslant 0$ be an integer such that $u \leqslant n-m+2$. Then, by performing the previous reasoning, but starting from the $m+1$ consecutive numbers from the u-th number of the n-th row of Pascal's triangle, we obtain:

$$\sum_{k=0}^{m}\binom{m}{k}\binom{n}{k+u}=\binom{m+n}{m+u}$$

Fourth solution (by induction) We recall that $\binom{m}{n}=0$ if $n>m$ or if $n<0$. We reason by induction on $m+n$. More precisely, for an integer $j \geqslant 0$, let $P_{j}$ be the property

!

FIGURE 1 - Interlude: the Sierpinski triangle

"For all integers $m, n \geqslant 0$ such that $m+n=j$, we have:

$$\sum_{k \geqslant 0}\binom{n}{k}\binom{m}{k}=\binom{m+n}{m} \quad \text { and } \quad \sum_{k \geqslant 0}\binom{n}{k-1}\binom{m}{k}=\binom{m+n}{m-1}^{\prime \prime}$$

Initialization: $\mathrm{P}_{0}$ is true.

Hereditary: Suppose $P_{j}$ is true and prove $P_{j+1}$. Let $m, n \geqslant 0$ be integers such that $m+n=j+1$. We write, using Pascal's relation many times:

$$\begin{aligned} \sum_{k \geqslant 0}\binom{n}{k}\binom{m}{k} & =\sum_{k \geqslant 0}\left(\binom{n-1}{k}+\binom{n-1}{k-1}\right)\binom{m}{k} \\ & =\sum_{k \geqslant 0}\binom{n-1}{k}\binom{m}{k}+\sum_{k \geqslant 0}\binom{n-1}{k-1}\binom{m}{k} \\ & =\binom{m+n-1}{m}+\binom{m+n-1}{m-1} \\ & =\binom{m+n}{m} \end{aligned}$$

where we used the induction hypothesis to write the penultimate equality (which is valid, as $m+n-1=j)$.

Similarly, we have:

$$\begin{aligned} \sum_{k \geqslant 0}\binom{n}{k-1}\binom{m}{k} & =\sum_{k \geqslant 0}\binom{n}{k-1}\left(\binom{m-1}{k}+\binom{m-1}{k-1}\right) \\ & =\sum_{k \geqslant 0}\binom{n}{k-1}\binom{m-1}{k}+\sum_{k \geqslant 0}\binom{n}{k-1}\binom{m-1}{k-1} \\ & =\binom{m+n-1}{m-2}+\binom{m+n-1}{m-1} \\ & =\binom{m+n}{m-1} \end{aligned}$$

where we used the induction hypothesis to write the penultimate equality (which is valid, as $m+n-1=j)$