58. Apply the factorial binomial theorem to finding the values of the following sums:

a) $C_{n}^{0} C_{m}^{k}+C_{n}^{1} C_{m}^{k-1}+C_{n}^{2} C_{m}^{k-2}+\ldots+C_{n}^{k} C_{m}^{0}$;

b) $C_{m}^{0} C_{n}^{k}-C_{m+1}^{1} C_{n}^{k-1}+C_{m+2}^{2} C_{n}^{k-2}-\cdots+(-1)^{k} C_{m+k}^{k} C_{n}^{0}$.

Sometimes when deriving relations involving binomial coefficients, it is very useful to use the fact that $C_{n}^{k}$ equals the number of combinations of $n$ elements taken $k$ at a time. To make such derivations more intuitive, it is convenient to use the following geometric scheme. Suppose we live in a city where the streets run in two mutually perpendicular directions (see Fig. 4, where all the streets of our city are represented by horizontal and vertical lines). We will number the parallel streets with the numbers $0,1,2,3$, etc., and we will denote the intersections by a pair of "coordinates" ($m, n$), where $m$ is the number of the "vertical" street passing through this intersection, and $n$ is the number of the "horizontal" street (in Fig. 4, the intersections are marked with dots). Now suppose we need to walk from a house located at the intersection $(0,0)$ to a house located at the intersection ($m, n$). In this case, we will have $C_{m+n}^{n}$ completely equal shortest paths connecting these two houses. Indeed, each of these shortest paths contains $m+n$ blocks, and $n$ of these blocks are "vertical". These $n$ "vertical" blocks can be placed among all $m+n$ blocks in $C_{m+n}^{n}$ ways. By further dividing the set of shortest paths into a series of classes based on some criteria, we can use this scheme to obtain some interesting relations involving binomial coefficients.

![](https://cdn.mathpix.com/cropped/2024_05_21_68334347b64402497ba5g-028.jpg?height=259&width=470&top_left_y=1064&top_left_x=555)

Fig. 4. The intersections of our city are depicted as horizontal and vertical lines. The intersections are marked with dots.
58. a) Using the fact that

$$
C_{n}^{i}=\frac{n(n-1) \ldots(n-i+1)}{i!}=\frac{n^{i \mu}}{i!}
$$

we get:

$$
C_{n}^{i} C_{m}^{k-i}=
$$

$$
=\frac{n^{i / 1} m^{k-i \mid 1}}{i!} \frac{\left.m^{k-i}\right)!}{(k-i)!} \frac{k!}{i!(k-i)!} n^{i \mid 1} m^{k-i \mid 1}=
$$

$$
=\frac{1}{k!} C_{k}^{i} n^{i \mid 1} m^{k-i \mid 1}
$$

Therefore, the desired sum is

$$
\begin{aligned}
\frac{1}{k!}\left\{C_{k}^{0} m^{k \mid 1}+C_{k}^{1} m^{k-11_{1}} n+C_{k}^{2} m^{k-2 \mid 1} n^{2 \mid 1}\right. & \left.+\ldots+C_{k}^{k} n^{k_{11}}\right\}= \\
& =\frac{(m+n)^{k \mid 1}}{k!}=C_{n n+n}^{k}
\end{aligned}
$$

This relation was previously obtained by us in a different way (see the solution to problem $55 m)$ ).

b) The $i$-th term of the sum can be transformed as follows:

$$
\begin{aligned}
& (-1)^{i} C_{m+i}^{i} C_{n}^{k-i}=(-1)^{i} \frac{\left.(m+i)^{i}\right)^{1}}{i!} \frac{n^{k-i} i_{11}}{(k-i)!}= \\
& =\frac{1}{k!} C_{k}^{i}(-1)^{i}(m+i)^{i_{1}} n^{k-t_{11}}
\end{aligned}
$$

But, as it is easy to see,

$$
\begin{aligned}
& (-1)^{i}(m+i-i)^{i / 1}=(-1)^{i}(m+i)(m+i-1) \ldots(m+1)= \\
& =(-m-1)(-m-2) \ldots(-m-i+1)(-m-i)=(-m-1)^{i / 1}
\end{aligned}
$$

Therefore,

$$
(-1)^{i} C_{m+i}^{i} C_{n}^{k-i}=\frac{1}{k!} C_{k}^{i}(-m-1)^{i \mid 1} n^{k-i \mid 1}
$$

Thus, our sum is

$$
\begin{aligned}
& \frac{1}{k l}\left\{C_{k}^{0} n^{k_{11}}+C_{k}^{1} n^{k-1 \mid 1}(-m-1)+\right. \\
& \left.\quad+C_{k}^{2} n^{k-2 \mid 1}(-m-1)^{2 / 1}+\ldots+C_{k}^{k}(-m-1)^{k \mid 1}\right\}= \\
& \quad=\frac{(n-m-1)^{k \mid 1}}{k!}=\frac{(n-m-1)(n-m-2) \ldots(n-m-k)}{k!}
\end{aligned}
$$

For $n-m-1 \geqslant k$, this expression is obviously equal to $C_{n-m-1}^{k}$.

Note also that, using the equality $C_{m+i}^{i}=C_{m+i}^{m}$, we can rewrite the obtained relation (for $n-m-1 \geqslant k$) as

$$
C_{m n}^{m} C_{n}^{k}-C_{m+1}^{m} C_{n}^{k-1}+C_{m+2}^{m} C_{n}^{k-2}-\ldots+(-1)^{k} C_{m+k}^{m} C_{n}^{0}=C_{n-m-1}^{k}
$$