Комбинаторные тождества

[Berdakh]

Здравствуйте!
Возникла такая задача в решении комбинаторной задачи.
Нужно доказать такую сумму:

$$\sum_{m=1}^{n}C_{n}^{m}(-1)^{m}m^{r}=\cases{-1, \quad\mbox{если} \quad r=0; \cr 0,\quad\mbox{если} \quad r=\overline{1,n-1} \cr}$$

[ИСН]

Это же эта самая, как её, ну.

-- Пн, 2012-02-13, 15:50 --

дискретная производная такого-то порядка, вот.

[Berdakh]

ИСН в сообщении #538227 писал(а):

Это же эта самая, как её, ну.

-- Пн, 2012-02-13, 15:50 --

дискретная производная такого-то порядка, вот.

А точнее?

[ИСН]

Ну Вы в школе журнал "Квант" или что-нибудь в этом роде читали? Вот мы запишем подряд квадраты натуральных чисел. А под ними запишем разности последовательных членов в этом ряду. А ещё под ними запишем разности тех разностей... Тыдыщ! Они все постоянны! Ух ты! А если взять кубы?

[Berdakh]

Какие ссылки можете дать?

[ИСН]

Ссылки? Мне казалось, что это common knowledge, "в воздухе носится". Вот многочлен, вот производная.

[Berdakh]

Если конкретно, то как можно доказать?

[ИСН]

Построить или где-нибудь прочитать теорию дискретных производных. Производная от многочлена - это опять многочлен, степень которого на 1 меньше. Многочлен степени 1 - это константа. Производная от константы - 0.

[Berdakh]

Ну вообще-то как можно доказать такие тождества? Есть ли стандартные пути?

[ИСН]

Это и есть стандартный. Чем он Вам не нравится? Словом "производная"? Ну, не говорите этого слова. Можете говорить "объект X".

[Dave]

Если $P(x)$- многочлен степени $r$, то $Q(x)=P(x+1)-P(x)$ - многочлен степени $r-1$, называемый дискретной производной $P(x)$. Если эту разностную операцию применить $n \leqslant r$ раз, то будет многочлен степени $r-n$, называемый производной $P(x)$ $n$-го порядка.
Что будет, когда $n>r$?
Как $n$-я производная расписывается через исходную функцию в общем случае (когда $P(x)$ не обязательно многочлен)? Начать с малых $n$ и расписать производную в виде суммы.
Что будет, если в полученной сумме взять $P(x) \equiv x^r$, а $x=0$ ?

[Berdakh]

Где можно найти такие тождества?

[ИСН]

взять да доказать по индукции, делов-то.

-- Пн, 2012-02-13, 22:13 --

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

[Dave]

Berdakh в сообщении #538369 писал(а):

Где можно найти такие тождества?

Например, вот. Выучите хотя бы его. Берём $a=x$, $b=1$, $n=r$. Получаем разложение для $(x+1)^r$. Потом нужно вычесть $x^r$ и посмотреть на степень полученного многочлена.