2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Неожиданное разложение числа в степени
Сообщение27.05.2016, 00:54 


27/05/16
3
Разбираясь с одной задачей, случайно получил следующее: натуральное число $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$$

 Профиль  
                  
 
 Re: Неожиданное разложение числа в степени
Сообщение27.05.2016, 11:52 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Неожиданное разложение числа в степени
Сообщение27.05.2016, 12:54 


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

 Профиль  
                  
 
 Re: Неожиданное разложение числа в степени
Сообщение27.05.2016, 13:18 
Заслуженный участник
Аватара пользователя


09/09/14
6328
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
$$

 Профиль  
                  
 
 Re: Неожиданное разложение числа в степени
Сообщение27.05.2016, 14:21 
Заслуженный участник
Аватара пользователя


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

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

(Оффтоп)

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

 Профиль  
                  
 
 Re: Неожиданное разложение числа в степени
Сообщение27.05.2016, 15:00 
Заслуженный участник


04/03/09
906
Придумал комбинаторное доказательство.
Пусть у нас есть $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$.

 Профиль  
                  
 
 Re: Неожиданное разложение числа в степени
Сообщение27.05.2016, 15:30 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Неожиданное разложение числа в степени
Сообщение27.05.2016, 15:49 


27/05/16
3
12d3
Очень здорово!

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

 Профиль  
                  
 
 Re: Неожиданное разложение числа в степени
Сообщение27.05.2016, 17:23 
Заслуженный участник


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

Конечные разности здесь реально ключевые:
Конкретная математика писал(а):
В общем случае $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$ - нет.

 Профиль  
                  
 
 Re: Неожиданное разложение числа в степени
Сообщение28.05.2016, 14:27 
Заслуженный участник


10/01/16
2315
"Геометрическое" решение:
Плоскость $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}$, будет половина кубика, и тоже красивая формула получится.

 Профиль  
                  
 
 Re: Неожиданное разложение числа в степени
Сообщение14.10.2017, 20:11 
Модератор
Аватара пользователя


11/01/06
5660
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)$.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 11 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group