Неожиданное разложение числа в степени

[ischenko]

Разбираясь с одной задачей, случайно получил следующее: натуральное число $n$ возведенное в натуральную степень $a$ можно представить в виде суммы $m \geq a + 1$ слагаемых следующего вида:

$$n^a = \sum_{k=0}^{m-1}{(-1)^{m+k-1} \binom{m}{k} (n-m+k)^a}$$

Например:

$$ 6^3 = -1 \cdot 2^3 + 4 \cdot 3^3 - 6 \cdot 4^3 + 4 \cdot 5^3$$

$$ 6^3 = 1 \cdot 1^3 - 5 \cdot 2^3 + 10 \cdot 3^3 - 10 \cdot 4^3 + 5 \cdot 5^3$$

$$ 6^3 = -1 \cdot 0^3 + 6 \cdot 1^3 - 15 \cdot 2^3 + 20 \cdot 3^3 - 15 \cdot 4^3 + 6 \cdot 5^3$$

Пока проверил вычислительно. Как это можно просто доказать и где можно про это почитать?

-- 27.05.2016, 02:33 --

Достаточно доказать, что для любых $n$ и $a$ и $m > a$:

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

[grizzly]

ischenko
Красивые тождества, не уверен, что встречал их раньше.

ischenko в сообщении #1126401 писал(а):

Как это можно просто доказать и где можно про это почитать?

Тоже не уверен, что есть совсем простое доказательство, но можно надеяться. Вы знакомы с техникой производящих функций? Можете посмотреть пару примеров в книге Дж. Риордана "Комбинаторные тождества" (гуглится в свободном доступе), п.п.1.1 и 1.2 Ведения -- это в любом случае не повредит -- (заодно полистайте всю книгу на предмет нет ли там этих тождеств в каком-нибудь суперобобщённом виде).

[ischenko]

grizzly
Cпасибо, полистаю. Обычно везде выскакивает переменный показатель степени с постоянным основанием, а здесь наоборот.

[grizzly]

ischenko в сообщении #1126455 писал(а):

Обычно везде выскакивает переменный показатель степени с постоянным основанием, а здесь наоборот.

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

$$ \sum_{j=0}^{k}(-1)^{k-j}\binom{k}{j}(j+n)^k = k! $$

А ещё вот такое совсем простенькое (может что-то подобное можно будет и здесь использовать):

$$ \binom{n}{k}(n-k) = \binom{n-1}{k}n $$

[grizzly]

ischenko
Ещё 5 минут поиска дали результат. Найдите здесь Ваш формулу под номером 10.5. Теперь стало понятнее, какой дорогой нужно идти, но идти всё равно лень

Если что, спросите доказательство на MathStackExchange, там народ потрудолюбивее будет :) Да и обидно немного, что такие красивые тождества, а на дороге не валяются.

(Оффтоп)

Оставлю здесь ключевые слова "Комбинаторное тождество для степеней" и "Теорема Эйлера для конечных разностей" для будущих посетителей с Гугла :)

[12d3]

Придумал комбинаторное доказательство.
Пусть у нас есть $a$ пронумерованных шаров и $n$ пронумерованных ящиков, $n \ge m$. Шары раскладываем по ящикам, в ящик можно класть сколько угодно шаров.
Подсчитаем количество способов раскидать шары так, что первые $m$ ящиков будут непустыми. Используем формулу включений-исключений. Свойство $a_i $ - это ящик с номером $i$ пуст.(обозначения см. тут) Тогда $N(a_{i_1},...,a_{i_k}) = (n-k)^a$. Мы выбираем $k$ пустых ящиков из первых $m$, а шары раскладываем по оставшимся $n-k$ ящикам. Итого, в формуле включений-исключений $k$-е слагаемое равно $(-1)^k\binom{m}{k}(n-k)^a$, т.е. выписанная ТСом сумма есть количество способов раскидать шары так, что первые $m$ ящиков будут непустыми. При $m > a$ оно равно 0, так как $a$ шаров не хватит на $m$ ящиков.
UPD. Это мы доказали только для $n>m$. Но сумму можно рассматривать как многочлен от $n$, имеющий бесконечное количество корней, следовательно, он тождественно равен нулю, и равенство справедливо при любых $n$.

[grizzly]

12d3
Круто! даже не знаю, красивее это чем проще, или наоборот :)
и сразу же очевидно, что при $m=a$ получим нужные $m!$.

[ischenko]

12d3
Очень здорово!

grizzly
Да, с этими $\binom{n}{k}$ какое-то гигантское число красивых тождеств :)

[Sonic86]

Еще из литературы можно посмотреть Грэхем, Кнут, Паташник Конкретная математика.

Конечные разности здесь реально ключевые:

Конкретная математика писал(а):

В общем случае $n$-я разность есть

$$\Delta^n f(x)=\sum\limits_k \binom{n}{k}(-1)^{n-k}f(x+k)$$

...
Пусть $f(x)$ - некоторый многочлен степени $d$.... Тогда

$$f(x)=\sum\limits_{k=0}^d c_k\binom{x}{k}$$

...
В частности можно получить важное тождество

$$\sum\limits_k \binom{n}{k}(-1)^k(a_0+a_1k+...+a_nk^n)=(-1)^na_nn!$$

А следующая конечная разность - это 0.
Получается, что $m>a$ необходимо, а вот $n\leqslant m$ - нет.

[DeBill]

"Геометрическое" решение:
Плоскость $x_1+ ...+ x_n = m$ отсекает от положительного "октанта" "тетраэдр" с ребром $m$. Его объем равен $\frac{m^n}{n!}$. Посмотрим, чему равен объем части единичного куба, лежащей ниже этой плоскости. По формуле включений-исключений получим (при m$\geqslant n$):
$1=\sum\limits_{j=0}^{n} (-1)^j C^j_{n}\cdot \frac{(m-j)^n}{n!}$.
Так что условие $m\geqslant n$ важно, но $m$ может быть и не целым - как и уSonic86

Впрочем, при $m=\frac{n}{2}$, будет половина кубика, и тоже красивая формула получится.

[maxal]

ischenko в сообщении #1126401 писал(а):

Достаточно доказать, что для любых $n$ и $a$ и $m > a$:

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

Разлагая

$$(n-k)^{a} = \sum_{i=0}^a \binom{a}{i} (m-k)^i (n-m)^{a-i},$$

и используя формулу (10), получаем

$$\sum_{k=0}^{m}{ (-1)^{k} \binom{m}{k} (n-k)^{a}} = \sum_{i=0}^a \binom{a}{i} (n-m)^{a-i} S(i,m).$$

Остаётся заметить, что при $m>a$, мы имеем $m>i$ для всех $i$, что по определению зануляет все числа Стирлинга второго рода $S(i,m)$.