Чтобы найти сумму Sk(n)=1k+2k+⋯+nk, запишем бином для (m+1)k+1 при m=1,2,…,n и сложим все равенства: слагаемые mk+1 встречаются и слева, и справа, поэтому почти все сократятся. Получится равенство, в котором Sk(n) выражается через уже известные S0(n),…,Sk−1(n).
Что пригодится из прошлого:бином Ньютона — раскрытие (m+1)k+1; рекуррентные соотношения — идея «сложить цепочку равенств, чтобы промежуточное сократилось»; сумма 1+2+⋯+n. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.
Задача
Задача. Найти формулу для суммы
Sk(n)=1k+2k+3k+⋯+nk,k∈Z≥0,n∈N.
Для малых k ответ известен: S0(n)=n1+1+⋯+1=n и S1(n)=2n(n+1). Предположим, что формулы для S0(n),S1(n),…,Sk−1(n) уже найдены. Как получить Sk(n)?
Маленький пример: k=1, n=4
Для m=1,2,3,4 раскроем (m+1)2=1+2m+m2 и сложим:
m
(m+1)2
1
2m
m2
1
4
1
2
1
2
9
1
4
4
3
16
1
6
9
4
25
1
8
16
сумма
54
4
20
30
Сумма левого столбца 54 равна сумме остальных: 54=4+20+30. Теперь заметим: слева стоят квадраты 22,32,42,52, а справа в последнем столбце — квадраты 12,22,32,42. Квадраты 22,32,42 есть и там, и там: вычтем их сумму 4+9+16=29 из обеих частей. Слева останется 52=25. Справа от последнего столбца останется 12=1, а два других столбца дают 4 (четыре единицы) и 20=2⋅(1+2+3+4): получилось 25=4+20+1. Перенесём 1 влево:
25−1=4+20,24=4+2⋅(1+2+3+4).
Отсюда 1+2+3+4=224−4=10. Так, не зная формулы 2n(n+1), мы получили сумму из бинома.
Сложим все n равенств. Слева получится сумма степеней 2k+1+3k+1+⋯+(n+1)k+1 (по одному слагаемому от каждого равенства), справа — ∑i=0k(ik+1)Si(n) и отдельно сумма степеней 1k+1+2k+1+⋯+nk+1. Сравним степени k+1 в левой и правой частях:
Слагаемые 2k+1,3k+1,…,nk+1 есть и слева, и справа — они сокращаются. Такое сокращение называют телескопическим: так же сокращались промежуточные члены в «лесенке» равенств из главы про рекуррентные соотношения. Слева остаётся (n+1)k+1; справа остаётся лишнее слагаемое 1k+1=1, которое мы переносим влево со знаком «минус». Остальные слагаемые справа — суммы по m от 1 до n степеней mi, то есть Si(n):
(n+1)k+1−1=i=0∑k(ik+1)Si(n).
Выделим слагаемое с i=k: (kk+1)Sk(n)=(k+1)Sk(n):
(n+1)k+1−1=i=0∑k−1(ik+1)Si(n)+(k+1)Sk(n).
Отсюда
Sk(n)=k+1(n+1)k+1−1−∑i=0k−1(ik+1)Si(n).
Как читать. Числитель начинается с (n+1)k+1−1 — это то, что осталось после сокращения. Из него вычитаем вклад меньших степеней S0,…,Sk−1 (с биномиальными коэффициентами) и делим на k+1 — коэффициент при искомой сумме.
Упростим числитель. Сначала (n+1)3−1=n3+3n2+3n. Вычитаем n: n3+3n2+2n=n(n+1)(n+2). Вычитаем 23n(n+1): n(n+1)(n+2−23)=2n(n+1)(2n+1). Делим на 3:
S2(n)=6n(n+1)(2n+1).
Проверка: n=3: 63⋅4⋅7=14=1+4+9 ✓.
Таблица значений
n
1
2
3
4
5
6
7
8
9
10
S0(n)
1
2
3
4
5
6
7
8
9
10
S1(n)
1
3
6
10
15
21
28
36
45
55
S2(n)
1
5
14
30
55
91
140
204
285
385
S3(n)
1
9
36
100
225
441
784
1296
2025
3025
Обратите внимание: S3(n)=(2n(n+1))2=S1(n)2: 3025=552, 2025=452. Сумма кубиков первых n чисел равна квадрату суммы самих чисел. Выведем эту формулу сами (задача 3 ниже).
Частые ошибки
Взять S0(n)=1. Сумма n единиц равна n.
Суммировать до i=k в числителе. В числителе вычитается сумма по i=0,…,k−1; слагаемое с i=k уже стоит слева как (k+1)Sk(n).
Забыть деление на k+1. Искомая сумма входит в равенство с коэффициентом k+1.
Потерять «−1». Вычитается единица: она появилась как 1k+1 при сокращении.
Проверь себя
1. Найдите 12+22+⋯+202.
Решение
S2(20)=620⋅21⋅41=2870.
2. Найдите 13+23+⋯+103 и сравните с (1+2+⋯+10)2.
Решение
По таблице S3(10)=3025. Сумма 1+2+⋯+10=55, 552=3025. Равенство верно.
3. Выведите формулу для S3(n) из рекуррентного равенства с k=3.
Решение
Равенство: (n+1)4−1=(04)S0+(14)S1+(24)S2+4S3. Левая часть: n4+4n3+6n2+4n. Вычтем S0=n: n4+4n3+6n2+3n. Вычтем 4S1=2n(n+1)=2n2+2n: n4+4n3+4n2+n. Вычтем 6S2=n(n+1)(2n+1)=2n3+3n2+n: n4+2n3+n2=n2(n+1)2. Остаётся 4S3=n2(n+1)2, то есть S3(n)=(2n(n+1))2.