Сумма степеней чисел

В разработке!
В разработке!
Эта тема находится в разработке! В любой момент может добавлен новый материал или изменен уже имеющийся!
Продвинутый уровень
Продвинутый уровень
Материал в этой теме предназначен для тех, кто полностью разобрался с базой и хочет «копнуть глубже».
Зависимости
Зависимости
Царского пути в эту тему нет! Вы сможете разобраться только если знаете следующие темы:

В РАЗРАБОТКЕ!

Согласно легенде, 8-летний Карл Гаусс плохо себя вел на уроке. Чтобы чем-то надолго занять непослушного мальчишку, учитель дал ему сложную задачу — найти сумму первых 100 натуральных чисел:

1+2+3+4++100= ?1 + 2 + 3 + 4 + \ldots + 100 = \ ?
Картина Н.П. Богданова-Бельского

К сожалению для несчастного учителя, маленький гений решил эту задачу меньше чем за минуту и озвучил правильный ответ — 5050. ЗДЕСЬ ЧЕРЕЗ СПОЙЛЕР РАСПИСАТЬ, КАК ОН ЭТО СДЕЛАЛ!

Обобщим эту задачу и попытаемся понять, как найти сумму степеней чисел. Введем обозначение SknS_k^n, обозначающее сумму n-ых степеней первых k натуральных чисел:

Skn=1n+2n+3n++knS^n_k = 1^n + 2^n + 3^n + \ldots + k^n

Задача о суммах степеней является типичным примером «мостика» между суммами и их общими формулами. Посмотрим, сможет ли нам в этом вопросе помочь сертифицированный эксперт по «мостикам» — бином Ньютона.

Рассмотрим разложение следующей степени бинома:

(k+1)n+1=Cn+10k0+Cn+11k1+Cn+12k2++Cn+1n+1kn+1(k+1)^{n+1} = C_{n+1}^0 k^0 + C_{n+1}^1k^1 + C_{n+1}^2k^2 + \ldots + C_{n+1}^{n+1}k^{n+1}

Обратите внимание, что в разложении справа встречаются все степени числа k от нулевой, до n+1n+1-ой. Выпишем все возможные разложения для всех чисел от 0 до k:

(0+1)n+1=1(1+1)n+1=Cn+1010+Cn+1111++Cn+1n+11n+1(2+1)n+1=Cn+1020+Cn+1121++Cn+1n+12n+1(k+1)n+1=Cn+10k0+Cn+11k1++Cn+1n+1kn+1 (0+1)^{n+1} = 1 \\ (1 + 1)^{n+1} = C_{n+1}^0 1^0 + C_{n+1}^11^1 + \ldots + C_{n+1}^{n+1}1^{n+1} \\ (2 + 1)^{n+1} = C_{n+1}^0 2^0 + C_{n+1}^12^1 + \ldots + C_{n+1}^{n+1}2^{n+1} \\ \cdots \\ (k+1)^{n+1} = C_{n+1}^0 k^0 + C_{n+1}^1k^1 + \ldots + C_{n+1}^{n+1}k^{n+1}

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

1n+1++(k+1)k+1==Cn+10(10++k0)+Cn+11(11++k1)++Cn+1n+1(1n+1++kn+1) 1^{n+1} + \ldots + (k+1)^{k+1} = \\ = C_{n+1}^0(1^0 + \ldots + k^0) + C_{n+1}^1(1^1 + \ldots + k^1) + \ldots + C_{n+1}^{n+1}(1^{n+1} + \ldots + k^{n+1})

Теперь заменим сумму в левой части равенства и суммы в скобках в правой части на введенное обозначение сумм степеней чисел:

Sk+1n+1=Cn+10Sk0+Cn+11Sk1++Cn+1n+1Skn+1+1S^{n+1}_{k+1} = C_{n+1}^0 S^0_k + C_{n+1}^1 S^1_k + \ldots + C_{n+1}^{n+1} S^{n+1}_k + 1

Невероятно! Всего парой простых действий с биномами Ньютона мы получили единую формулу, в которую «впечатаны» все суммы всех степеней (от 0 до n+1n+1) чисел!

Но нам все же нужна степень n и k чисел, а не n+1n+1 и k+1k+1. Поэтому, немного преобразуем равенство, пользуясь тем, что Cn+10=Cn+1n+1=1C_{n+1}^0 = C_{n+1}^{n+1} = 1, а так же Sk0=kS^0_k = k, в чем вы можете самостоятельно убедиться:

Skn+1+(k+1)n+1=(k+1)+Cn+11Sk1++Cn+1nSkn+Skn+1\cancel{S^{n+1}_k} + (k+1)^{n+1} = (k+1) + C_{n+1}^1 S^1_k + \ldots + C_{n+1}^n S^n_k + \cancel{S^{n+1}_k}
(k+1)n+1(k+1)=Cn+11Sk1++Cn+1nSkn(k+1)^{n+1} - (k+1) = C_{n+1}^1 S^1_k + \ldots + C^n_{n+1} S^n_k
(k+1)n+1(k+1)=i=1nCn+1iSki(k+1)^{n+1} - (k+1) = \sum\limits_{i=1}^{n} C_{n+1}^i S^i_k

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

Кстати, подобный «финт» с суммой степеней можно провернуть не только с натуральными числами, но и с любыми другими числами или даже математическими объектами!

Задача -- Найти сумму степеней биномиальных коэффициентов
(Cn0)k+(Cn1)k++(Cnn)k= ?(C_n^0)^k + (C_n^1)^k + \ldots + (C_n^n)^k = \ ?
Написать отдельную статью про сумму степеней чисел!

https://scask.ru/o_book_ela.php?id=29

https://www.youtube.com/watch?v=2bcNgXHgcqM

https://dev.mccme.ru/~merzon/pscache/bernoulli-howto-pre.pdf

Взять упражнения отсюда:

https://kvant.mccme.ru/1973/05/summy_odinakovyh_stepenej_natu.htm

Превью