Simplify the following sum:

$$
\begin{gathered}
S=1 \cdot 2 \cdot \ldots \cdot k+2 \cdot 3 \cdot \ldots(k+1)+3 \cdot 4 \cdot \ldots \cdot(k+2)+\ldots \\
+n \cdot(n+1) \cdot \ldots \cdot(n+k-1)
\end{gathered}
$$

(The sum consists of $n$ terms, each term being the product of $k$ factors.)
Let's denote the number of terms in the sum under the summation sign as an index, so the expression for $S_{n} \cdot n$ when $n=2$ and $n=3$ can be transformed as follows:

$$
\begin{gathered}
S_{2}=1 \cdot 2 \cdot \ldots \cdot k+2 \cdot 3 \cdot \ldots \cdot k \cdot(k+1)=2 \cdot 3 \cdot \ldots \cdot k(1+k+1)= \\
\frac{2 \cdot 3 \cdot \ldots \cdot k \cdot(k+1)(k+2)}{k+1} \\
S_{3}=S_{2} 3 \cdot 4 \cdot \ldots \cdot k \cdot(k+1) \cdot(k+2)= \\
3 \cdot 4 \cdot \ldots \cdot(k+2) \cdot\left(\frac{2}{k+1}+1\right)=\frac{3 \cdot 4 \cdot \ldots \cdot(k+2) \cdot(k+3)}{k+1}
\end{gathered}
$$

In the final form, the numerator in both cases is the product of $k+1$ consecutive natural numbers, starting with the number of terms in the sum, and the denominator is $k+1$. From this, we conjecture that

$$
S_{n}=\frac{n \cdot(n+1) \cdot \ldots \cdot(n+k)}{k+1}
$$

(It is easy to see that this is also valid for $n=1$.) We will prove this by mathematical induction. Suppose (1) is true for some value of $n$, say $i$. Then it also holds for $n=i+1$, because

$$
\begin{gathered}
S_{i+1}=S_{i}+(i+1) \cdot(i+2) \cdot \ldots \cdot(i+k)= \\
\frac{i \cdot(i+1) \cdot \ldots \cdot(i+k)}{k+1}+(i+1) \cdot(i+2) \cdot \ldots \cdot(i+k)= \\
(i+1) \cdot(i+2) \cdot \ldots \cdot(i+k)\left(\frac{i}{k+1}+1\right)= \\
\frac{(i+1) \cdot(i+2) \cdot \ldots \cdot(i+k)(i+k+1)}{k+1}
\end{gathered}
$$

Thus, (1) is true for all positive integers $n$. On the other hand, (1) as a one-term expression can be considered simpler than the original given form. This completes the solution of the problem.

Remark. The material for the mathematical exercises in specialized classes includes the basic concepts and problems of combinatorics. Using these, our result can be interpreted as follows. Dividing the found equality by $k!$, we recognize in the terms on the left side the number of $k$-class combinations that can be formed from $k, k+1, \ldots, n+k-1$ (different) elements, and on the right side, the number of $k+1$-class combinations of $n+k$ elements. Thus, we have

$$
C_{k}^{(k)}+C_{k+1}^{(k)}+\ldots+C_{n+k+1}^{(k)}=C_{n+k}^{k+1}
$$

or, using the other common notation,

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

Consider the $(k+1)$-class combinations that can be formed from the numbers $1,2, \ldots, n+k$. Then the left side gives the number of combinations grouped by their smallest number. The consecutive terms give the number of combinations whose smallest number is

$$
n, \quad n-1, \quad \ldots, \quad 1
$$

In this case, the other $k$ numbers are chosen from the larger ones in all possible ways, and their number is respectively

$$
k, \quad k+1, \quad \ldots . \quad n+k-1
$$

$n+1$ cannot be chosen as the smallest number of the $(k+1)$-class combination.

Similarly, we can say that the consecutive terms on the left side represent the number of combinations whose largest number is

$$
k+1, \quad k+2, \quad \ldots . \quad k+n
$$[^0]


[^0]:    ${ }^{1}$ For students in general education classes, we recommend: Kürschák J.-Hajós Gy.-Neukomm Gy.-Surányi J.: Mathematical Competition Problems I., 3rd edition, Tankönyv-kiadó, Budapest, 1965, p. 26.