Тождество

[Sasha2]

А вот еще такой вопрос, уважаемый ewert,
Почему, например, нельзя основать решение данной задачи на доказательстве этих тождеств

$\sum\limits_{p=0}^{n}{(-1)^pC_n^p{p^k}}=0$

Ведь это тождество при конкретном k от 0 до n есть не что иное, как коэффициент при $x^k$ у многочлена, который уважаемый Кудрявцев, предлагает показать равным нулю.
И так как Вы тоже согласны с тем, что многослен равен нулю для всех $k \le n$, то значит по одной из теорем алгебры все коэффиуиенты этого многочлена должны быть равны нулю тождественно.
Но тогда это тождество должно быть ну уж достаточно известным, хотя вот не получается доказать его, кроме как для трифиального случая $k=0$.

[ewert]

Sasha2 в сообщении #297421 писал(а):

Почему, например, нельзя основать решение данной задачи на доказательстве этих тождеств

$\sum\limits_{p=0}^{n}{(-1)^pC_n^p{p^k}}=0$

Можно, только это невыгодно. Во всяком случае, я не знаю, как можно доказать эти тождества сами по себе более-менее просто. Это одна из довольно распространённых ситуаций, когда более общая задача решается проще, чем её частный случай.

Sasha2 в сообщении #297421 писал(а):

И так как Вы тоже согласны с тем, что многослен равен нулю для всех $k \le n$,

Как раз не согласен. Многочлен равен нулю только при $k$ строго меньших $n$. При $k$ равном $n$ будет ненулевая константа.

[Sasha2]

Ну тогда для меня ничего удивительного нет.
Ну если уж у Вас не получается так просто доказать это тождество (хотя вертится в голове что-то типа есть какой-то определитель составляемый из катых степеней чисел, но пока не то все это), то у меня уж точно не получится. Ладно, оставим это тождество на потом.

[ewert]

Sasha2, ну сколько ж раз можно доказывать одно и то же (последний раз это делалось в http://dxdy.ru/post297281.html#p297281)?

Или Вам рекуррентное соотношение не доказывается? Ну пожалуйста:

$$\displaystyle S_{n+1}(x)\equiv\sum\limits_{j=0}^{n+1}(-1)^kC_{n+1}^{j}\cdot(j+x)^k=x^k+\sum\limits_{j=1}^{n}(-1)^k(C_{n}^{j}+C_{n}^{j-1})\cdot(j+x)^k+(-1)^{n+1}(n+1+x)^k=$$

$$\displaystyle =\left(x^k+\sum\limits_{j=1}^{n}(-1)^kC_{n}^{j}\cdot(j+x)^k\right)+\left(\sum\limits_{j=1}^{n}(-1)^kC_{n}^{j-1}\cdot(j+x)^k+(-1)^{n+1}(n+1+x)^k\right)=$$

$$\displaystyle =\sum\limits_{j=0}^{n}(-1)^kC_{n}^{j}\cdot(j+x)^k-\left(\sum\limits_{l=0}^{n-1}(-1)^lC_{n}^{l}\cdot(l+1+x)^k+(-1)^{n}(n+1+x)^k\right)=$$

$$=S_n(x)-S_n(1+x).$$

Что может быть проще. При каждом вычитании степень многочлена уменьшается на единицу. И поскольку вначале многочлен $S_0(x)=x^k$ был степени $k$ -- после $k$-кратного вычитания получим $S_k(x)=\mathrm{const}$ (причём константа, между прочим, ненулевая). И, следовательно, далее при всех $n>k$ будет $S_n(x)\equiv0$. И ограничений на $k$ здесь никаких нет (кроме, естественно, целочисленности и неотрицательности).

А Ваши любимые тождества -- это просто частный случай при $x=0$.

(определитель -- он Вандермонда, и прямого отношения к делу не имеет)

[Sasha2]

Ну Вы извините. Я же все таки про свое тождество речь веду.
А вот если воспользоваться такой штуковиной:
Рассмотрим функцию $(1-e^t)^n$.
Шпарим ее, как обычно по биномк Ньютона. Тогда она равна $\sum\limits_{p=0}^{p=n}(-1)^pC_n^pe^{pt}$.
Дифференцируем ее k раз и получаем, что ее производная порядка $k$ записывается так:
$\sum\limits_{p=0}^{p=n}(-1)^pC_n^pp^ke^{pt}$
Следовательно наше выражение (мое тождество) - это производная k-го порядка от функции $(1-e^t)^n$ в точке 0.
Да тоже ничего хорошего исскать эти производные до k-го порядка.

А вообще можно эту производную как-то посчитать. Не знаю, но зато уже отчетливо вижу, что при k=1 - это тоже тождество.

[Профессор Снэйп]

Sasha2 в сообщении #297861 писал(а):

Да тоже ничего хорошего исскать эти производные до k-го порядка.

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

Имеем $(1-e^t)^n = (-t + o(t))^n = (-t)^n + o(t^n)$ и все нужные производные равны $0$ из аналитичности функции.

[Sasha2]

Да что это Вы товарищи взялись. Ну нет у меня Вашей техники, не вижу я то что Вам видно легко. А впопроще можно с формулой и вообще правильно ли я наткнулся на эту функцию, ну в смысле нет ли тут ошибки в таком рассуждении.

[Профессор Снэйп]

Естественно, $k$ должно быть строго меньше $n$; требование же $n \geqslant 3$ совершенно лишнее.

Цитата:

нет ли тут ошибки в таком рассуждении.

Нет, ошибки в таком рассуждении нет.

[ewert]

Ну раз уж пошла такая пьянка -- поясню, почему я назвал утверждение в этой задачке "очевидным".

Пусть задан набор равноотстоящих узлов $x_j=x_0+k\cdot h$, $j=0,1,\ldots,n$ (или, что эквивалентно, членов некоторой арифметической прогрессии). Конечные разности порядка $m$ для функции $f(x)$ определяются рекуррентно:

$\Delta^mf_j\equiv\Delta^{m-1}f_{j+1}-\Delta^{m-1}f_j$;
$\Delta^0f_j\equiv f(x_j)$.

С другой стороны, для них есть явная формула:

$\Delta^mf_j=\sum\limits_{j=0}^m(-1)^{m-j}C_m^j\,f(x_j)$

(между прочим, довольно очевидная: биномиальные коэффициенты, т.е. элементы треугольника Паскаля, подчиняются как раз примерно аналогичным рекуррентным соотношениям).

Так вот, есть такая теоремка: существует такая точка $c\in(x_0;x_n)$, что $\dfrac{\Delta^nf_0}{h^n}=f^{(n)}(c)$ (при условии достаточной гладкости функции, естественно).

А сумма, предложенная в задаче -- это не что иное, как разделённая разность для функции $f(x)=x^k$ (с точностью до знака). Откуда моментально и ответ: эта сумма не равна нулю при всех $n\leqslant k$ (кроме исключительных случаев) и равна нулю при всех $n>k$.

Несколько из пушки по воробьям, конечно. Зато очевидно.

-- Пн мар 15, 2010 09:52:22 --

Sasha2 в сообщении #297861 писал(а):

Дифференцируем ее k раз и получаем, что ее производная порядка $k$ записывается так:
$\sum\limits_{p=0}^{p=n}(-1)^pC_n^pp^ke^{pt}$
Следовательно наше выражение (мое тождество) - это производная k-го порядка от функции $(1-e^t)^n$ в точке 0.

Весьма разумно (с точностью до выбора буковки $p$ в качестве индекса).

[Sasha2]

Да в общем видно, что k-я производная данной функции будет состоять из суммы двух слагаемых:
1) Произведение $(1-e^t)$ на еще какую-то функцию
2) Произведение $(1-e^t)^{n-k}$ на еще что-то

Отсюда уже выводим, что во всяком случае для k=0,1,...,n-1
тождество $\sum\limits_{p=0}^{n}{(-1)^pC_n^p{p^k}}=0$ верно.

[ewert]

Sasha2 в сообщении #297883 писал(а):

Да в общем видно, что k-я производная данной функции будет состоять из суммы двух слагаемых:
1) Произведение $(1-e^t)$ на еще какую-то функцию
2) Произведение $(1-e^t)^{n-k}$ на еще что-то

Это всё не нужно (а первый пункт, кстати, ещё и лишний). Какой бы "техники" Вам ни не хватало, но уж формула-то Тейлора точно была. А это:

Профессор Снэйп в сообщении #297865 писал(а):

Имеем $(1-e^t)^n = (-t + o(t))^n = (-t)^n + o(t^n)$ и все нужные производные равны $0$ из аналитичности функции.

-- не более чем формула Тейлора. Кстати, аналитичность тут вовсе не нужна, достаточно бесконечной дифференцируемости (если Вас испугало именно слово "аналитичность").