Числа C_n^k, многочлены, последовательности

27

Числа $C_n^k$, многочлены, последовательности
(несколько подходов к одной задаче)
В. Н. Вагумен

Напомним одну задачу из «Задачика «Кванта», элементарное решение которого было написано в «Кванте» № 12 за 1972 год.

М138. Докажите, что если $m$ и $n$—члены числа $1 < m < n$, то

$$\sum_{k=1}^{n} (-1)^k k^m C_k^k = 0,$$

его $C_k^k$ — биоминальные коэффициенты.

Разные доказательства этих точек детять послужат нам удачным поводом для того, чтобы познакомить читателя с некоторыми важными математическими понятиями и фактами, не входящими в школьную программу (конечные разности, интерполяционная формула для многочленов, произвольная многочлена, степенной ряд экспоненты). Вслед за определениями и теоремии в каждом параграфе читатель встретиет слова «вернемся теперь к нашей задаче», а за ними — новое решение задачи М138.

Доказательства теorem можно пропустить, но лучше их разобрать, хотя сделать это нелегко, так как они написаны очень коротко.

Введение. Биоминальные коэффициенты и формулировка задачи

Мы перечислим несколько свойств чисел $C_n^k$. Каждый из свойств 0.1—0.3 можно принять за определение этих чисел.

0.1. $C_n^k$ — коэффициенты многочлена

$$(a + x)^n = C_n^0 a^n + C_n^1 a^{n-1} x + \dots + C_n^k a^{n-k} x^k + \dots + C_n^n x^n.$$

0.2. $C_n^0 = 1; C_n^n = 1$; для каждого $k = 1,2, \dots, n - 1$

$$C_n^k = C_{n-1}^{k-1} + C_{n-1}^k.$$

0.3. Для всех $n$ и $k$ ($0 \leqslant k \leqslant n$)

$$C_n^k = \frac{n(n-1)\dots(n-k+1)}{1 \cdot 2 \cdot \dots \cdot k},$$ или $C_n^k = \frac{n!}{k!(n-k)!},$

где $m! = 1 \cdot 2 \cdot 3 \dots m; \quad 0! = 1! = 1$.

Уражение 0. a) Найдите числа $C_n^k$ для всех $n$ от 1 до 10, пользоваться каждым из определений 0.1, 0.2, 0.3. б) Выведите 0.2 из 0.1, пользоваться токдевом $(a + x)^n = (a + x)^{n-1}(a + x)$. b) Выведите 0.3 из 0.2, пользоваться математической индук-

28

цини (то есть проверьте, что если формула (3) верна для $n-1$, то она верна и для $n$).
г) Проверьте, что $C_n^k = C_n^{n-k}$.

Многочлен $a + x$ иногда называют «биномом» (бином — то же, что двуилен), формулу (1) — формулой «бинома Ньютона», а числа $C_n^k$ — «биномальные козффициенты».

Положим в равенстве (1) $a$ равным 1. Получим

$$(1 + x)^n = C_n^0 + C_n^1 x + \dots + C_n^k x^k + \dots + C_n^n x^n.$$

Подставив сюда $x = -1$, получим

$$C_n^0 - C_n^1 + C_n^2 - \dots + (-1)^k C_n^k + \dots + (-1)^n C_n^n = 0.$$

Оказывается, что кроме соответствия (5) для чисел $C_n^k$ верны еще следующие равенства:

$$- C_n^1 + 2 C_n^2 - 3 C_n^3 + \dots + (-1)^n n C_n^n = 0,$$
$$- C_n^1 + 2^2 C_n^2 - 3^2 C_n^3 + \dots + (-1)^n n^2 C_n^n = 0,$$
$$- C_n^1 + 2^{n-1} C_n^2 - 3^{n-1} C_n^3 + \dots + (-1)^n n^{n-1} C_n^n = 0.$$

Именно эти равенства требовалось доказать в задаче М138; о них и будет идти речь в конце каждого параграфа.

В дальнейшем мы будем часто пользоваться короткой записью сумм с помощью значка $\Sigma$. Например, формулу (1) можно коротко записать так:

$$(a + x)^n = \sum_{k=0}^{k=n} C_n^k a^{n-k} x^k,$$
формулу (4) $-(1 + x)^n = \sum_{k=0}^{k=n} C_n^k x^k,$
равенство (5) $-\sum_{k=0}^{k=n} (-1)^k C_n^k = 0$ и, наконец, равенства (6), которые требуются доказать в задаче М138 —

$$\sum_{k=1}^{k=n} (-1)^k k^m C_n^k = 0$$

при каждом натуральном $m < n$.

§ 1. Последовательности и конечные разности

Пусть на множество целых неотрицательных чисел 0, 1, 2, 3… задана функция $f$. Это значит, что задана последовательность

$$f(0), f(1), f(2), f(3), \dots$$

Если из каждой члена последовательности $f$, разумеется, кроме первого, вычесть предшествующий ему член последовательности, то мы получим новую последовательность — последовательность разностей

$$f(1) - f(0), f(2) - f(1), f(3) - f(2), \dots$$

Обозначим соответствующее ей функцию через $\Delta f$: $\Delta f(0) = f(1) - f(0);$
$\Delta f(1) = f(2) - f(1);$ $\Delta f(2) = f(3) - f(2) \dots$

Если продель эту же операцию — переход от $f$ к $\Delta f$ — с последовательностью $\Delta f$, то мы получим последовательность

$$f(2) - 2f(1) + f(0), f(3) - 2f(2) + f(1), \dots$$

Обозначим ее через $\Delta^2 f$.

29

Эта последовательность называется последовательностью вторых разностей для $f$. Еще раз взявности, получим последовательность третьих разностей — $\Delta^3 f$:

$$f(3) - 3f(2) + 3f(1) - f(0), f(4) - 3f(3) + 3f(2) - f(1), \dots$$

и так далее.

Таким образом, по определению

$$\Delta^{n+1}f(x) = \Delta^n f(x + 1) - \Delta^n f(x).$$

(7)

(Напомним, что аргумент $x$ функций $f$, $\Delta f$, $\Delta^2 f$, … принимает целые неотрицательные значения: $x = 0, 1, 2, \dots$).

Рассмотрим в качестве первого примера постоянную функцию $f$:

$$f(0) = f(1) = f(2) = \dots = a.$$

Для нее последовательность разностей $\Delta f$ будет, очевидно, состоять из одних нуляй. Кратко это запишем так: $\Delta f \equiv 0$ (при всех $x$).

Естественно, что и последовательности $\Delta^2 f$, …, $\Delta^n f$ так же будут состоять из одних нуляй, то есть $\Delta^n f \equiv 0$.

Если $f$ — линейная функция: $f(x) = ax + b$, то есть если последовательность представляется собой арифметической прогрессию $b, a + b, 2a + b, 3a + b, \dots$, то все члены последовательности $\Delta f$ будут равны одному и тому же числу $a$. Отсюда $\Delta^2 f \equiv 0$.

Если $f$ — квадратный трехчлен $f(x) = ax^2 + bx + c$, то $\Delta f$ — линейная функция (от номера $x$):

$$\Delta f(x) = f(x + 1) - f(x) = a(x + 1)^2 + b(x + 1) + c - ax^2 - bx - c = 2ax + b.$$

Тогда $\Delta^2 f$ — постоянная функция: $\Delta^2 f = 2a$. Следовательно, $\Delta^3 f = 0$ и, конечно, $\Delta^n f = 0$ для всех $n > 2$.

У правах не имеем 1. а) Пусть $f(x) = x^3$. Найдите $\Delta f$, $\Delta^2 f$, $\Delta^3 f$, … 6) Тот же вопрос, если $f(x) = 2^x$.

Наши наблюдения обобщаются в следующих двух теоремах.

1.1. Число $\Delta^n f(x)$ выражается через значения функций $f$ по формуле

$$\Delta^n f(x) = C_n^0 f(x + n) - C_n^1 f(x + n - 1) + \dots + (-1)^n C_n^n f(x) =$$

$$= \sum_{k=0}^{k=n} (-1)^k C_n^k f(x + n - k).$$

1.2. Если $f(x)$ — многочлен степени $m < n$, то $\Delta^n f = 0$.

Оба утверждения 1.1 и 1.2 доказываются индукцией по $n$. Для $n = 1, 2, 3$ мы их уже проверили. Предполагается, что они верны для $n$, доказываем для $n+1$.

1.1. Используя (7), (8) и (2), получаем

$$\Delta^{n+1}f(x) = \Delta^n f(x + 1) - \Delta^n f(x) =$$

$$= C_n^0 f(x + n + 1) - C_n^1 f(x + n) + \dots + (-1)^n C_n^n f(x) - C_n^0 f(x + n) + \dots + (-1)^n C_n^n f(x) =$$

$$= C_n^0 f(x + n + 1) - C_n^1 f(x + n) + \dots + (-1)^n C_n^n f(x + n) + (-1)^n \times C_n^n f(x).$$

1.2. Пусть $f(x) = a_0 + a_1 x + \dots + a_j x^j + \dots + a_m x^m$. Нашим $m$ равенств (они следуют из (4))

$$(x + 1)^j - x^j = C_j^1 x^{j-1} + C_j^2 x^{j-2} + \dots + C_j^{j-1} x + 1$$

(здесь $j = 1, 2, \dots, m$). Умножим их соответственно на коэффициенты $a_j$ и сложим. Получим: влевой части $\Delta f(x) = f(x + 1) - f(x)$, в правой — неокторый многочлен от $g(x)$ степени не выше $m - 1$. Если $m < n$, то $m - 1 < n - 1$ и по предположению индукции $\Delta^{n-1}g = 0$. Следовательно, $\Delta^n f = \Delta^{n-1} (\Delta f) = \Delta^n g = 0$.

30

Вернемся теперь к нашей задаче.

Равенство (6’), согласно 1.1. в точности ознакомлен, что $\Delta^n f(0) = 0$ для функции $f(x) = x^m$, а это следует пряmo из утверждения 1.2.

Задача 1. Пусть $f(x) = a + a_1x + \dots + a_nx^n$. Найдите $\Delta^n f$. Пользовать этим результатом, вычислите сумму

$$\sum_{k=0}^{k=n} (-1)^k k^n C_n^k.$$

Задача 2. Докажите, что есть $\Delta^{n+1} f(x) = 0$ для всех $x$, то $f(x)$ — многочлен степени не выше $n$.

Задача 3. Найдите все последовательности $f$, для которых $\Delta f(x) = \lambda f(x)$, где $\lambda$ — некоторое число.

§ 2. Многочлены и интерполяционная формула

Мы знаем, что через две точки можно проведити единственную прямую. Другими словами, если заданы две пары чисел $(\alpha_0, \beta_0), (\alpha_1, \beta_1)$, причем $\alpha_0 \neq \alpha_1$, то существует единственный многочлен степени не выше первой $P(x) = ax + b$ такой, что $P(\alpha_0) = \beta_0$ и $P(\alpha_1) = \beta_1$.

Этот факт обобщается следующим образом.

Пусть заданы $n + 1$ различных чисел $\alpha_0, \alpha_1, \dots, \alpha_n$ и $n + 1$ чисел $\beta_0, \beta_1, \dots, \beta_n$. Тогда справедливые следующие утверждения.

2.1. Существует многочлен $P$ степени не выше $n$ макой, что

$$P(\alpha_i) = \beta_i \quad (\text{для всех } i = 0,1,\dots,n).$$

2.2. Многочлен $P$ определяется единственным образом.

Для доказательства 2.1 достаточно представить такой многочлен. Для этого рассмотрим сначала многочлены

$$D_k(x) = \frac{(x - \alpha_0)(x - \alpha_1)\dots(x - \alpha_{k-1})(x - \alpha_{k+1})\dots(x - \alpha_n)}{(\alpha_k - \alpha_0)(\alpha_k - \alpha_1)\dots(\alpha_k - \alpha_{k-1})(\alpha_k - \alpha_{k+1})\dots(\alpha_k - \alpha_n)}$$

(в числитель и знаменатель по $n$ многочленей). Ясно, что

$$D_k(\alpha_i) = \begin{cases} 1, \text{ если } i = k; \\ 0, \text{ если } i \neq k. \end{cases}$$

Умножим теперь $D_k(x)$ на число $\beta_k$ и сложим все эти многочлены. Для получения многочлена

$$P(x) = \sum_{k=0}^{k=n} \beta_k D_k(x)$$

выполнены все равенства (9).

Для доказательства 2.2 нам понадобится две важные теоремы о корнях многочленов.

2.3. Если многочлен

$$f(x) = a_0 + a_1x + \dots + a_nx^n$$

степени не выше $n + 1$ различных корней, то этом многочлен равен 0, то есть $a_0 = a_1 = a_2 = \dots = a_n = 0$.

2.4. («Теорема Безу».) Если $\alpha$ — корень многочлена $f(x)$, то многочлен $f(x)$ делится на $x - \alpha$, то есть

$$f(x) = (x - \alpha)g(x),$$

еде $g(x)$ — некоторый многочлен.

31

Доказательство 2.4. Напишем $n$ точекств $(x^j - \alpha^j) = (x - \alpha)(x^{j-1} + x^{j-2}\alpha + \ldots + \alpha^{j-2}x + \alpha^{j-1})$, $(j=1, 2, \ldots, n)$, умножим их соответственно на коэффициенты $a_j$ и сложим все эти точекств. Получим формулу, справедливую для любого многочлена (12) и любого числа $\alpha$:

$$f(x) - f(\alpha) = (x - \alpha)g(x),$$

где $g(x)$ — неокоторый многочлен. В частности, если $f(\alpha)=0$, получаем (13).

Доказательство 2.3. проведем индукцией по $n$. Для $n=1$ утверждение 2.3 очевидно. Докажем, что если оно верно для $n-1$, то верно и для $n$. Пусть $\alpha_0, \alpha_1, \ldots, \alpha_n$ — корни многочлена (12). Тогда, согласно 2.4:

$$f(x) = (x - \alpha_n)g(x),$$

причем многочлен $g(x)$ имеет степень не выше $n-1$ и имеет $n$ различных корней $\alpha_0, \alpha_1, \ldots, \alpha_{n-1}$. По предположению индукции, $g(x)$ равен нулю; из (14) следует, что $f(x)$ тоже равен нулю.

Доказательство 2.2. Пусть $p_1$ и $p_2$ — два многочлена, для каждой из которых верны равенства (9). Тогда их разность удовлетворяет условиям теоремы 2.3 ( многочлен $f(x) = p_1(x) - p_2(x)$) степени не выше $n+1$ корней $\alpha_0, \alpha_1, \ldots, \alpha_n$ и поэтому равна нулю, то есть $p_1(x) = p_2(x)$.

Итак, мы доказали, что через $n+1$ точку $(\alpha_0, \beta_0), (\alpha_1, \beta_1), \ldots, (\alpha_n, \beta_n)$ можно proveсти единственную кривую вида

$$y = f(x) = a_0 + a_1x + \ldots + a_nx^n,$$

и даже привели формулу, позволяющего сразу написать нужный многочлен. Эта формула (11) называется интегриционной формулой Лаэранжа.

Упражнение 2. a) Найдите квадратный треугольник, который в точках 2, 3, 5 принадлежит значения соответствующего 7, 11, 13. 6) Найдите многочлен степени не выше 4, график которого проходит через точки $(-2, -7), (-1, 0), (0, 1), (1, 2), (2, 9)$.

Вернемся к нашей задаче. Построим многочлен степени не выше $n$, который в точках $\alpha_k = k(k=0, 1, 2, \ldots, n)$ принадлежит значения соответствующего $\beta_k = k^m$. Из формулы (11) следует, что этот многочлен равен $\sum_{k=0}^{k=n} k^mD_k(x)$, где

$$D_k(x) = \frac{x(x-1)\ldots(x-k+1)(x-k-1)\ldots(x-n)}{k(k-1)\ldots1(-1)(-2)\ldots(k-n)}.$$

Ясно, что коэффициент при $x^n$ у многочлена (15) равен

$$\frac{1}{k(k-1)\ldots1(-1)(-2)\ldots(k-n)} = (-1)^{k-n} \frac{1}{k!(n-k)!} = \frac{(-1)^n}{n!} (-1)^k C_n^k,$$

позному коэффициент при $x^n$ у многочлена $P(x)$ равен

$$(1/n!) (-1)^n \sum_{k=0}^{k=n} (-1)^k k^m C_n^k.$$

С другой стороны, ясно, что многочлен $P(x)$ есть просто $x^m$, ведь $m < n$. Поэтому коэффициент при $x^n$ у $P(x)$ равен нулю.

Задание 4. Докажите, что набор чисел $y_0, y_1, \ldots, y_n$ удовлетворяет условиям: «для любого многочлена $f(x)$ степени не выше $n-1$ справедливо равенство

$$\sum_{k=0}^{k=n} f(k)y_k = 0»,$$

в том и только том случае, если $y_k = t(-1)^k C_n^k$, где $t$ — неокоторе число.

32

Задание 5 (обобщение). Докажите, что если числа $\alpha_0, \alpha_1, \dots, \alpha_n$ попарно различны, то система уравнения

$$y_0 + y_1 + \dots + y_n = 0,$$
$$\alpha_0 y_0 + \alpha_1 y_1 + \dots + \alpha_n y_n = 0,$$
$$\alpha_0^2 y_0 + \alpha_1^2 y_1 + \dots + \alpha_n^2 y_n = 0,$$
$$\alpha_0^{n-1} y_0 + \alpha_1^{n-1} y_1 + \dots + \alpha_n^{n-1} y_n = 0$$

имеет решение набор чисел

$$y_k = \frac{t}{(\alpha_k - \alpha_1)(\alpha_h - \alpha_2) \dots (\alpha_k - \alpha_{k-1})(\alpha_h - \alpha_{k+1}) \dots (\alpha_h - \alpha_n)}$$

($k=0, 1, \dots, n+1$), где $t$ — произвольное число, и не имеет других решений.

§ 3. Производная многочлен и кратные корни

Пусть $f(x)$ — многочлен степени $n$:

$$f(x) = a_0 + a_1 x + a_2 x^2 + \dots + a_{n-1} x^{n-1} + a_n x^n = \sum_{k=0}^{k=n} a_k x^k.$$

Тогда по определению многочлен степени $n-1$

$$f'(x) = a_1 + 2 a_2 x + \dots + (n-1) a_{n-1} x^{n-2} + n a_n x^{n-1} = \sum_{k=1}^{k=n} ka_k x^{k-1}$$

называется произвольной многочлен $f(x)$. Оказывается верным следующее утверждение.

3.1. Если многочлен $f(x)$ делится на $(x - \alpha)^{m+1}$, то многочлен $f'(x)$ делится на $(x - \alpha)^m$. Другими словами, если число $\alpha$ является корнем кратности $m+1$ многочлен $f(x)$, то $\alpha$ является корнем кратности не менее $m$ многочлен $f'(x)$.

Для доказательства 3.1. мы используем такую лемму.

3.2. Если $f(x) = (x - \alpha)g(x)$, то

$$f'(x) = g(x) + (x - \alpha)g'(x).$$

(16)

Доказательство 3.2. Если $g(x) = b_{n-1} x^{n-1} + \dots + b_1 x + b_0$, то, как не трудно проверить, пользоваться определением произвольной многочлена, и правая, и левая часть равенства (16) равна

$$(b_0 - b_1 \alpha) + 2 (b_1 - b_2 \alpha) x + \dots + (n-1) (b_{n-2} - b_{n-1} \alpha) x^{n-2} + n b_{n-1} x^{n-1}.$$

Доказательство 3.1 проверен indykцией по $m$. Проверим 3.1 при $m=1$. Если $f(x)$ делится на $(x - \alpha)^2$, то $f(x) = (x - \alpha) g(x)$, где $g(x)$ делится на $(x - \alpha)$, и, как видно из (16), $f'(x)$ тоже делится на $(x - \alpha)$.

Доказательство 3.1 верно для $m-1$, то оно верно и для $m$. Пусть $f(x)$ делится на $(x - \alpha)^{m+1}$. Тогда $f(x) = (x - \alpha) g(x)$, где $g(x)$ делится на $(x - \alpha)^m$, и из (16) следует, что $f'(x)$ делится на $(x - \alpha)^m$ ($g'(x)$ делится на $(x - \alpha)^{m-1}$ по предложению indykции).

У практике 3. a) Имеет ли многочлен $x^3 - x^2 - 8x + 12$ кратные корни?

6. Найдите $a, b$ и $c$ такие, что многочлен $x^3 + ax^2 + bx + c$ делится на $(x+1)^2$.

Вернемся теперь к нашей задаче. Равенство (6’) означает в точности, что многочлен $f_m(x) = \sum_{k=0}^{k=n} k^m C_k^n x^{k-1}$ имеет число $x = -1$ своим корнем.

Доказем более сильное утверждение: многочлен $x f_m(x)$ имеет число $(-1)$ корнем кратности $n-m$, то есть делится на $(x+1)^{n-m}$ (если $m < n$).

Для $xf_0(x) = \sum_{k=0}^{k=n} C_k^n x^k = (1+x)^n$ это очень удобно. Для $0 < m < n$ проведем indykцию по $m$. Пусть $xf_{m-1}(x)$ имеет число $(-1)$ корнем крат-