Математическая индукция (конечные разности)

[Xant0]

Добрый день!

Помогите пожалуйста с доказательством формулы для конечных разностей:
$\triangle^m f_i = \sum\limits_{j=0}^m (-1)^j C_m^j f_{i+m-j}$

Для доказательства используем математическую индукцию.
С базой индукции всё понятно. Делаем переход - пусть при m=k формула верна, докажем, что она верна и для m=k+1.

$\triangle^{k+1} f_i = \triangle^{k} f_{i+1} - \triangle^{k} f_{i} = \sum\limits_{j=0}^k (-1)^j C_k^j f_{i+1+k-j} - \sum\limits_{j=0}^k (-1)^j C_k^j f_{i+k-j}$.
Сгруппируем коэффициенты при одинаковых f, получим
$\sum\limits_{j=1}^{k+1}( (-1)^{j-1} C_k^{j-1} - (-1)^j C_k^j) f_{i+k-j+1} + f_{i+k+1} - (-1)^{k+1}C_k^{k+1}f_i$

Дальше не получается - биномиальные коэффициенты можно было бы сложить, но мешают минус единицы в соответствующих степенях. Да и последнее слагаемое $- (-1)^{k+1}C_k^{k+1}f_i$ оказывается "лишним".

[profrotter]

С использованием Z-преобразования и бинома Ньютона легко доказывается.

[Mikhail Sokolov]

По определению $\triangle^m = (1-L)^m$, где $L$ - оператор сдвига (лаговый оператор). Приведенная вами формула получается раскладыванием $(1-L)^m$ на слагаемые, используя бином Ньютона.

[ewert]

Xant0 в сообщении #695100 писал(а):

мешают минус единицы в соответствующих степенях.

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

[iifat]

Xant0 в сообщении #695100 писал(а):

$ (-1)^{j-1} C_k^{j-1} - (-1)^j C_k^j$

Вот сюда посмотрите внимательно. Попробуйте подставить конкретное j. Вы справитесь.

[Xant0]

Получается, что
$(-1)^{j-1} C_k^{j-1} - (-1)^j C_k^j = (-1)^{j-1}C_k^{j-1} + (-1)^{j+1}C_k^j$

$(-1)^{j-1}$ и $(-1)^{j+1}$ дают одно и то же число, т.е. получаем

$(-1)^{j-1}C_k^{j-1} + (-1)^{j+1}C_k^j = (-1)^{j-1}(C_k^{j-1} + C_k^j) = (-1)^{j-1}C_{k+1}^j.$

Исходное выражение будет иметь вид
$\sum\limits_{j=1}^{k+1} (-1)^{j-1}C_{k+1}^j f_{i+k-j+1} + f_{i+k+1} - (-1)^{k+1}C_k^{k+1}f_i$

Должно получиться $\sum\limits_{j=0}^{k+1} (-1)^{j}C_{k+1}^j f_{i+k-j+1}$
Тут ещё $- (-1)^{k+1}C_k^{k+1}f_i$ - здесь же вообще, если посчитать $C_k^{k+1}$, то получается (-1)! в знаменателе...

[TOTAL]

$Tf_i=f_{i+1}$ - обозначение.

$$\triangle^m f_i =\left( T + (-1)\right)^m f_i = \sum_{j=0}^{m}C^j_m (-1)^j T^{m-j}f_i = \cdots$$

[Xant0]

Спасибо, всё получилось доказать просто с помощью матиндукции, главное здесь было с индексами разобраться.