Сумма (-1)^k*k^m*C(n,k)=0

[forum_user]

Подскажите идею как доказывать.

[Sonic86]

Здесь написано как набирать формулы: topic183.html У вас еще есть время исправить. Исправите - подскажу ;)

[forum_user]

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

[Хорхе]

$m<n$, я полагаю?

Докажите (индукцией по $n$) такое: если $P$ --- многочлен степени $r$, то $\sum_{k=1}^n (-1)^k C_n^k P(x+k)$ --- многочлен степени $r-n$ при $n\le r$ и нуль при $n>r$.

[_hum_]

forum_user в сообщении #501119 писал(а):

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

А, мот, проще напрямую просуммировать по биному, используя параметризацию?

$$\sum_{k=1}^n (-1)^k \cdot k^m \cdot C_n^k= \frac{d^m}{d\alpha^m}\bigg|_{\alpha = 0} \sum_{k=0}^n (-1)^k \cdot e^{\alpha k} \cdot C_n^k$$

[Хорхе]

(Оффтоп)

Возможно, и проще, не исследовал. Но задача-то, как мы понимаем, не о том, чтобы придумать остроумный простой способ доказательства, а о дискретной производной.

[_hum_]

Хорхе

(Оффтоп)

Извиняюсь, а можно ссылочку на понятие дискретной производной?

[Хорхе]

(Оффтоп)

_hum_ в сообщении #501159 писал(а):

Хорхе
Извиняюсь, а можно ссылочку на понятие дискретной производной?

Там есть разные определения. Например, можно так:
$\Delta f(x) = f(x) - f(x-1)$. Посчитайте $\Delta^n f(x)$. Вы будете удивлены.

[_hum_]

Хорхе

(Оффтоп)

А, ну тогда понятно. Да, как-то выше второй никогда не приходилось использовать. Спасибо. Теперь буду иметь в виду.

[mpot]

Помогите, пожалуйста, найти ошибку в решении этой задачи.
Обозначим через искомую сумму через $S_n(m)$.
Примем предположение индукции, что $S_n(m) = 0$, и попробуем доказать $S_{n+1}(m) = 0$.
$S_{n+1} = \sum_{k=1}^{n+1}(-1)^kk^mC_{n+1}^k $

Разложим $C_{n+1}^k$ с помощью треугольника Паскаля и запишем последний член суммы в явном виде.

$\sum_{k=1}^{n}(-1)^kk^m(C_{n}^k + C_{n}^{k-1})+(-1)^{n+1}k^mC_{n+1}^{n+1}$

Разобъем сумму на две части, а $C_{n+1}^{n+1}$ заменим на $C_{n}^{n}$

$\sum_{k=1}^{n}(-1)^kk^mC_{n}^k + \sum_{k=1}^{n}(-1)^kk^mC_{n}^{k-1}+(-1)^{n+1}k^mC_{n}^{n} $

Левая сумма - в чистом виде $S_n(m)$, а в правую внесем $(-1)^{n+1}k^mC_{n}^{n}$ в качестве n+1-го слагаемого.

$S_n(m) + \sum_{k=1}^{n+1}(-1)^kk^mC_{n}^{k-1}$

Вынесем из суммы слагаемое при k=1 и поменяем индекс суммирования на l=k-1.

$S_n(m) + \sum_{l=1}^{n}(-1)^{l+1}(l+1)^mC_{n}^{l} + (-1)^11^mC_{n}^{0}$

Из суммы выносим минус, одновременно замечая, что $(-1)^11^mC_{n}^{0}=-1$.

$S_n(m) - \sum_{l=1}^{n}(-1)^{l}(l+1)^mC_{n}^{l} - 1$

Раскладывая $(l+1)^m$ по биному Ньютона, мы получаем, что сумма распадается на m+1 сумму $S_n(i)$ со множителями в виде соответствующих биномиальных коэффициентов. При этом каждая из этих сумм по предположению индукции равна нулю.
Таким образом, получается что $S_{n+1}(m)=-1$.
Но мы-то хотели, чтобы получился 0:)
В чем проблема, подскажите, пожалуйста.

[mpot]

Пожалуйста, помогите!
Мозг кипит уже.

[nnosipov]

Чему равна сумма

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

при $m=0$? Вы думаете, что нулю, а на самом деле ...

[Null]

Ваша проблема в том что на самом деле правильная формула такая:
$\sum_{k=0}^n (-1)^k \cdot P(x+k) \cdot C_n^k$ (суммирование с 0)

В ней при $P(x)=x^m$ первое слагаемое исчезает. Но только при $m>0$. При $m=0$ оно не исчезает и дает недостающую 1.

В итоге вы пытаетесь доказать неверное утверждение.

Еще замечание

mpot в сообщении #506769 писал(а):

Раскладывая $(l+1)^m$ по биному Ньютона, мы получаем, что сумма распадается на m+1 сумму $S_n(i)$ со множителями в виде соответствующих биномиальных коэффициентов. При этом каждая из этих сумм по предположению индукции равна нулю.

У вас этого нет в предположении индукции.

[Хорхе]

Ну вот к моей подсказке еще подсказка, раз Вы оффтопы не читаете. Для функции $f$ обозначим $f^{(n)}(x) = \sum_{k=0}^n (-1)^k C_n^k f(x+k) $. Докажите, что $f^{(n+1)}(x) = f^{(n)}(x)-f^{(n)}(x+1)$.

[Null]

Хорхе в сообщении #507363 писал(а):

Ну вот к моей подсказке еще подсказка, раз Вы оффтопы не читаете. Для функции $f$ обозначим $f^{(n)}(x) = \sum_{k=1}^n (-1)^k C_n^k f(x+k) $. Докажите, что $f^{(n+1)}(x) = f^{(n)}(x)-f^{(n)}(x+1)$.

Это неправда, суммировать нужно с $k=0$.