Let's determine the sum of the following series:

$$
\binom{n}{0}+\binom{n+1}{1}+\binom{n+2}{2}+\ldots+\binom{n+k}{k}
$$

where $n$ and $k$ are natural numbers. (The symbol $\binom{n}{k}$ represents the number of ways to choose $k$ elements from a set of $n$ elements, disregarding the order of the elements. As is known, $\binom{n}{k}=\frac{n(n+1)(n+2) \ldots(n+k-1)}{1 \cdot 2 \cdot 3 \cdot \ldots \cdot k}$, and $\binom{n}{0}=1$. These numbers are the coefficients that appear in the expansion of binomials, hence they are also called "binomial coefficients".)
I. solution: Let us start from the following known identity:

$$
\begin{aligned}
& \binom{n+1}{k-1}+\binom{n+1}{k}=\binom{n+2}{k} \\
& \binom{n+1}{0}+\binom{n+1}{1}=\binom{n+2}{1}
\end{aligned}
$$

For the case $k=1$:

Add $\binom{n+2}{2}-\mathrm{t}$ to both sides:

$$
\binom{n+1}{0}+\binom{n+1}{1}+\binom{n+2}{2}=\binom{n+2}{1}+\binom{n+2}{2}=\binom{n+3}{2}
$$

In both cases, the first term is 1, which can also be written as $\binom{n}{0}$, thus the following identity appears:

$$
\binom{n}{0}+\binom{n+1}{1}+\binom{n+2}{2}+\ldots+\binom{n+k}{k}=\binom{n+k+1}{k}
$$

We have already proven this for $k=1$ and 2. We will prove by induction that this holds for all $k$.

Assume that it is true for some $k$ (2). Add $\binom{n+k+1}{k+1}$ to both sides:

$$
\begin{aligned}
\binom{n}{0}+\binom{n+1}{1} & +\binom{n+2}{2}+\ldots+\binom{n+k}{k}+\binom{n+k+1}{k+1}= \\
& =\binom{n+k+1}{k}+\binom{n+k+1}{k+1}
\end{aligned}
$$

By (1), the right side is $\binom{n+k+2}{k+1}$, so the formula (2) is also true for $(k+1)$, and the sum of the given $S_{k}$ series is thus

$$
S_{k}=\binom{n+k+1}{k}
$$

The solution by the problem setter is the

II. solution: Using the fact that $\binom{m}{k}$ is the number of $k$-class combinations that can be formed from $m$ elements, we will prove

$$
\binom{n+k+1}{k}=\binom{n+k}{k}+\binom{n+k-1}{k-1}+\ldots+\binom{n}{0}
$$

the correctness of the identity. The left side is the number of $(k+1)$-element combinations that can be selected from $n+k+1$ elements, for example, from the numbers $1,2, \ldots, n+k+1$, i.e., the number of $(k+1)$-element groups that can be selected if we do not consider the order of the elements, for example, we always arrange the elements in increasing order. We classify these groups according to how many consecutive numbers they contain from the beginning of the number sequence. The number of combinations in the first group, which do not contain 1, is clearly

$$
\binom{n+k}{k}
$$

Then come the combinations that contain 1 but not 2, followed by those that contain 1 and 2 but not 3, and so on. Generally, in the combinations that contain $1,2, \ldots, i$ but not $i+1$, we need to select $k-i$ elements from the $n+k-i$ elements $i+2, \ldots, n+k+1$ in addition to the already selected $1, \ldots, i$ elements. The number of such combinations is thus

$$
\binom{n+k-i}{k-i}
$$

(This gives the number of combinations that do not contain 1 when $i=0$, and also gives the correct result when $i=k$.) Summing this for $i=0,1, \ldots, k$ indeed gives the number of all $k$-element combinations that can be selected from $n+k+1$ elements. This proves the above identity.[^0]

III. solution: It is known ${ }^{2}$ that $\binom{m}{l}$ is the coefficient of the $a^{m-l} b^{l}$ term in the polynomial form of $(a+b)^{m}$ for $l=0,1, \ldots, m$:

$$
(a+b)^{m}=\binom{m}{0} a^{m}+\binom{m}{1} a^{m-1} b+\ldots+\binom{m}{l} a^{m-l} b^{l}+\ldots+\binom{m}{m} b^{m}
$$

Considering this, the sum in the problem will be the coefficient of the $a^{n}$ term in

$$
1+(a+1)+(a+1)^{2}+\ldots+(a+1)^{n+k}
$$

when this sum is arranged by powers of $a$. This sum is a geometric series with $n+k+1$ terms and a common ratio of $a+1$, and it can be written in the following closed form:

$$
\begin{aligned}
& \frac{(a+1)^{n+k+1}-1}{(a+1)-1}=\frac{1}{a}\left\{\binom{n+k+1}{0} a^{n+k+1}+\binom{n+k+1}{1} a^{n+k}+\ldots+\right. \\
& \left.+\binom{n+k+1}{i} a^{n+k+1-i}+\ldots+\binom{n+k+1}{n+k} a+\binom{n+k+1}{n+k+1}-1\right\}
\end{aligned}
$$

The value of the last positive term in the parentheses is 1, so the division by $a$ can be performed term by term. The $n$-th degree term is obtained by dividing the $(n+1)$-th degree term in the parentheses by $a$; the coefficient of the $(n+1)$-th degree term is $\binom{n+k+1}{k}$. Thus, we arrive at the following identity:

$$
\binom{n}{0}+\binom{n+1}{1}+\ldots+\binom{n+k}{k}=\binom{n+k+1}{k}
$$[^1]


[^0]:    ${ }^{1}$ See Mathematical Competition Problems, Part I, p. 28 or K. M. L. IV, 1952, May-June, p. 121:

[^1]:    ${ }^{2}$ See Mathematical Competition Problems, Part I, p. 64 or K. M. L. IV, 1952, May-June, p. 117.