Задача М138‍‍

Десять читателей прислали элементарные решения этой задачи (с помощью метода математической индукции). Приведём одно из наиболее коротких доказательств, присланное Б. Фришлингом (Тбилиси).

Нетрудно проверить, что доказываемые равенства верны при $n=2$‍,‍ 3, 4 (см. пример в тексте задачи). Допустим, что при $l\lt n-1$‍‍ равенства $\sum\limits_{j=0}^{n-1}{}(-1)^jj^lC_{n-1}^l=0$‍‍ верны. Воспользовавшись равенством $$ C_n^k=\dfrac{n!}{k!\,(n-k)!}=\dfrac nk\cdot\dfrac{(n-1)!}{(k-1)!\,(n-k)!}=\dfrac nkC_{n-1}^{k-1}, $$ получаем $$ \begin{gather*} \sum\limits_{k=1}^n{}(-1)^kk^mC_n^k= n\sum\limits_{k=1}^n{}(-1)^kk^{m-1}C_{n-1}^{k-1}= n\sum\limits_{j=0}^{n-1}{}(-1)^{j+1}(j+1)^{m-1}C_{n-1}^j=\\= -n\sum\limits_{j=0}^{n-1}\left[(-1)^j\left(\sum\limits_{l=0}^{m-1}C_{m-1}^lj^l\right)C_{n-1}^j\right]= -n\sum\limits_{l=0}^{m-1}\left[C_{m-1}^l\left(\sum\limits_{\smash{j}=0}^{n-1}{}(-1)^jj^lC_{n-1}^j\right)\right]. \end{gather*} $$ Если $m\lt n$‍,‍ то в последнем выражении каждая круглая скобка равна нулю по предположению индукции (поскольку $l\le m-1\lt n-1$‍),‍ и поэтому вся сумма равна нулю. Доказательство закончено.

Ряд присланных решений основан на некоторых тождествах между многочленами (одно из таких решений см., например, в «Задачнике по алгебре» В. А. Кречмара, где содержится задача 55, эквивалентная М138). Несколько решений, не требующих, в отличие от элементарных, почти никаких выкладок, прислали шестиклассник Ю. Соркин (его решение использует понятие производной многочлена), Э. Туркевич (он пользуется понятием степенного ряда) и др. В заметке десятиклассников А. Бочарова и А. Шерстюка (Николаев), В. Янкелевича (Кустанай) и в решениях, присланных некоторыми другими читателями, с решением задачи М138 связывается общий вопрос о разностях (1-го, 2-го, $\ldots$‍,‍ $n$‍‍-го порядка) для последовательности значений многочленов в точках, составляющих арифметическую прогрессию. Обо всех этих и ещё о некоторых других понятиях «высшей математики», позволяющих посмотреть на равенства задачи М138 с разных точек зрения, мы расскажем в специальной статье‍ в следующем номере «Кванта».

Семь читателей указывают в своих письмах на очень красивое комбинаторное доказательство тех же равенств, использующее «формулу включений и исключений» (оно приводится в книге Н. Я. Виленкина «Комбинаторика», стр. 24⁠—⁠26, 61⁠—⁠62). Эта замечательная формула (с её частным случаем мы сталкивались в решении задачи М92 про Петины каникулы — см. «Квант» № 3 за 1972 год, стр. 41⁠—⁠42) заслуживает специального знакомства, которое мы отложим до другого раза.