bulgakov

42. Суммы степеней 1ᵏ+2ᵏ+…+nᵏ

Чтобы найти сумму Sk(n)=1k+2k+⋯+nkS_k(n)=1^k+2^k+\dots+n^k, запишем бином для (m+1)k+1(m+1)^{k+1} при m=1,2,…,nm=1,2,\dots,n и сложим все равенства: слагаемые mk+1m^{k+1} встречаются и слева, и справа, поэтому почти все сократятся. Получится равенство, в котором Sk(n)S_k(n) выражается через уже известные S0(n),…,Sk−1(n)S_0(n),\dots,S_{k-1}(n).

Что пригодится из прошлого: бином Ньютона — раскрытие (m+1)k+1(m+1)^{k+1}; рекуррентные соотношения — идея «сложить цепочку равенств, чтобы промежуточное сократилось»; сумма 1+2+⋯+n1+2+\dots+n. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.

Задача

Задача. Найти формулу для суммы

Sk(n)=1k+2k+3k+⋯+nk,k∈Z≥0, n∈N.S_k(n)=1^k+2^k+3^k+\dots+n^k,\qquad k\in\mathbb Z_{\ge0},\ n\in\mathbb N.

Для малых kk ответ известен: S0(n)=1+1+⋯+1⏟n=nS_0(n)=\underbrace{1+1+\dots+1}_{n}=n и S1(n)=n(n+1)2S_1(n)=\dfrac{n(n+1)}2. Предположим, что формулы для S0(n),S1(n),…,Sk−1(n)S_0(n),S_1(n),\dots,S_{k-1}(n) уже найдены. Как получить Sk(n)S_k(n)?

Маленький пример: k=1k=1, n=4n=4

Для m=1,2,3,4m=1,2,3,4 раскроем (m+1)2=1+2m+m2(m+1)^2=1+2m+m^2 и сложим:

mm (m+1)2(m+1)^2 11 2m2m m2m^2
1 4 1 2 1
2 9 1 4 4
3 16 1 6 9
4 25 1 8 16
сумма 54 4 20 30

Сумма левого столбца 5454 равна сумме остальных: 54=4+20+3054=4+20+30. Теперь заметим: слева стоят квадраты 22,32,42,522^2,3^2,4^2,5^2, а справа в последнем столбце — квадраты 12,22,32,421^2,2^2,3^2,4^2. Квадраты 22,32,422^2,3^2,4^2 есть и там, и там: вычтем их сумму 4+9+16=294+9+16=29 из обеих частей. Слева останется 52=255^2=25. Справа от последнего столбца останется 12=11^2=1, а два других столбца дают 44 (четыре единицы) и 20=2⋅(1+2+3+4)20=2\cdot(1+2+3+4): получилось 25=4+20+125=4+20+1. Перенесём 11 влево:

25−1=4+20,24=4+2⋅(1+2+3+4).25-1=4+20,\qquad 24=4+2\cdot(1+2+3+4).

Отсюда 1+2+3+4=24−42=101+2+3+4=\dfrac{24-4}2=10. Так, не зная формулы n(n+1)2\dfrac{n(n+1)}2, мы получили сумму из бинома.

Общий вывод

Для каждого m=1,2,…,nm=1,2,\dots,n по формуле бинома

(m+1)k+1=∑i=0k+1(k+1i)mi=∑i=0k(k+1i)mi+mk+1.(m+1)^{k+1}=\sum_{i=0}^{k+1}\binom{k+1}{i}m^i=\sum_{i=0}^{k}\binom{k+1}{i}m^i+m^{k+1}.

Запишем это равенство для всех mm:

2k+1=∑i=0k(k+1i)1i+1k+1,3k+1=∑i=0k(k+1i)2i+2k+1,  ⋮(n+1)k+1=∑i=0k(k+1i)ni+nk+1.\begin{aligned} 2^{k+1}&=\sum_{i=0}^{k}\binom{k+1}{i}1^i+1^{k+1},\\ 3^{k+1}&=\sum_{i=0}^{k}\binom{k+1}{i}2^i+2^{k+1},\\ &\ \ \vdots\\ (n+1)^{k+1}&=\sum_{i=0}^{k}\binom{k+1}{i}n^i+n^{k+1}. \end{aligned}

Сложим все nn равенств. Слева получится сумма степеней 2k+1+3k+1+⋯+(n+1)k+12^{k+1}+3^{k+1}+\dots+(n+1)^{k+1} (по одному слагаемому от каждого равенства), справа — ∑i=0k(k+1i)Si(n)\sum_{i=0}^{k}\binom{k+1}{i}S_i(n) и отдельно сумма степеней 1k+1+2k+1+⋯+nk+11^{k+1}+2^{k+1}+\dots+n^{k+1}. Сравним степени k+1k+1 в левой и правой частях:

слева:
  2^(k+1) + 3^(k+1) + …
  … + n^(k+1) + (n+1)^(k+1)
справа:
  1^(k+1) + 2^(k+1) + 3^(k+1)
  + … + n^(k+1)
  (плюс суммы S_i)

Слагаемые 2k+1,3k+1,…,nk+12^{k+1},3^{k+1},\dots,n^{k+1} есть и слева, и справа — они сокращаются. Такое сокращение называют телескопическим: так же сокращались промежуточные члены в «лесенке» равенств из главы про рекуррентные соотношения. Слева остаётся (n+1)k+1(n+1)^{k+1}; справа остаётся лишнее слагаемое 1k+1=11^{k+1}=1, которое мы переносим влево со знаком «минус». Остальные слагаемые справа — суммы по mm от 11 до nn степеней mim^i, то есть Si(n)S_i(n):

(n+1)k+1−1=∑i=0k(k+1i)Si(n).(n+1)^{k+1}-1=\sum_{i=0}^{k}\binom{k+1}{i}S_i(n).

Выделим слагаемое с i=ki=k: (k+1k)Sk(n)=(k+1)Sk(n)\dbinom{k+1}{k}S_k(n)=(k+1)S_k(n):

(n+1)k+1−1=∑i=0k−1(k+1i)Si(n)+(k+1)Sk(n).(n+1)^{k+1}-1=\sum_{i=0}^{k-1}\binom{k+1}{i}S_i(n)+(k+1)S_k(n).

Отсюда

Sk(n)=(n+1)k+1−1−∑i=0k−1(k+1i)Si(n)k+1.\boxed{S_k(n)=\frac{(n+1)^{k+1}-1-\sum_{i=0}^{k-1}\binom{k+1}{i}S_i(n)}{k+1}}.

Как читать. Числитель начинается с (n+1)k+1−1(n+1)^{k+1}-1 — это то, что осталось после сокращения. Из него вычитаем вклад меньших степеней S0,…,Sk−1S_0,\dots,S_{k-1} (с биномиальными коэффициентами) и делим на k+1k+1 — коэффициент при искомой сумме.

Проверим на малых kk

k=1k=1. S1(n)=(n+1)2−1−(20)S0(n)2=n2+2n−n2=n(n+1)2S_1(n)=\dfrac{(n+1)^2-1-\binom20S_0(n)}2=\dfrac{n^2+2n-n}2=\dfrac{n(n+1)}2 ✓.

k=2k=2. Нужны S0=nS_0=n и S1=n(n+1)2S_1=\dfrac{n(n+1)}2:

S2(n)=(n+1)3−1−(30)S0(n)−(31)S1(n)3=(n+1)3−1−n−3n(n+1)23.S_2(n)=\frac{(n+1)^3-1-\binom30S_0(n)-\binom31S_1(n)}3=\frac{(n+1)^3-1-n-\dfrac{3n(n+1)}2}3.

Упростим числитель. Сначала (n+1)3−1=n3+3n2+3n(n+1)^3-1=n^3+3n^2+3n. Вычитаем nn: n3+3n2+2n=n(n+1)(n+2)n^3+3n^2+2n=n(n+1)(n+2). Вычитаем 3n(n+1)2\dfrac{3n(n+1)}2: n(n+1)(n+2−32)=n(n+1)(2n+1)2n(n+1)\left(n+2-\dfrac32\right)=\dfrac{n(n+1)(2n+1)}2. Делим на 33:

S2(n)=n(n+1)(2n+1)6.\boxed{S_2(n)=\frac{n(n+1)(2n+1)}6}.

Проверка: n=3n=3: 3⋅4⋅76=14=1+4+9\dfrac{3\cdot4\cdot7}6=14=1+4+9 ✓.

Таблица значений

nn 1 2 3 4 5 6 7 8 9 10
S0(n)S_0(n) 1 2 3 4 5 6 7 8 9 10
S1(n)S_1(n) 1 3 6 10 15 21 28 36 45 55
S2(n)S_2(n) 1 5 14 30 55 91 140 204 285 385
S3(n)S_3(n) 1 9 36 100 225 441 784 1296 2025 3025

Обратите внимание: S3(n)=(n(n+1)2)2=S1(n)2S_3(n)=\left(\dfrac{n(n+1)}2\right)^2=S_1(n)^2: 3025=5523025=55^2, 2025=4522025=45^2. Сумма кубиков первых nn чисел равна квадрату суммы самих чисел. Выведем эту формулу сами (задача 3 ниже).

Частые ошибки

  • Взять S0(n)=1S_0(n)=1. Сумма nn единиц равна nn.
  • Суммировать до i=ki=k в числителе. В числителе вычитается сумма по i=0,…,k−1i=0,\dots,k-1; слагаемое с i=ki=k уже стоит слева как (k+1)Sk(n)(k+1)S_k(n).
  • Забыть деление на k+1k+1. Искомая сумма входит в равенство с коэффициентом k+1k+1.
  • Потерять «−1-1». Вычитается единица: она появилась как 1k+11^{k+1} при сокращении.

Проверь себя

1. Найдите 12+22+⋯+2021^2+2^2+\dots+20^2.

Решение

S2(20)=20⋅21⋅416=2870S_2(20)=\dfrac{20\cdot21\cdot41}6=2870.

2. Найдите 13+23+⋯+1031^3+2^3+\dots+10^3 и сравните с (1+2+⋯+10)2(1+2+\dots+10)^2.

Решение

По таблице S3(10)=3025S_3(10)=3025. Сумма 1+2+⋯+10=551+2+\dots+10=55, 552=302555^2=3025. Равенство верно.

3. Выведите формулу для S3(n)S_3(n) из рекуррентного равенства с k=3k=3.

Решение

Равенство: (n+1)4−1=(40)S0+(41)S1+(42)S2+4S3(n+1)^4-1=\binom{4}{0}S_0+\binom{4}{1}S_1+\binom{4}{2}S_2+4S_3. Левая часть: n4+4n3+6n2+4nn^4+4n^3+6n^2+4n. Вычтем S0=nS_0=n: n4+4n3+6n2+3nn^4+4n^3+6n^2+3n. Вычтем 4S1=2n(n+1)=2n2+2n4S_1=2n(n+1)=2n^2+2n: n4+4n3+4n2+nn^4+4n^3+4n^2+n. Вычтем 6S2=n(n+1)(2n+1)=2n3+3n2+n6S_2=n(n+1)(2n+1)=2n^3+3n^2+n: n4+2n3+n2=n2(n+1)2n^4+2n^3+n^2=n^2(n+1)^2. Остаётся 4S3=n2(n+1)24S_3=n^2(n+1)^2, то есть S3(n)=(n(n+1)2)2S_3(n)=\left(\dfrac{n(n+1)}2\right)^2.

4. Найдите 1+2+⋯+1001+2+\dots+100 и 12+22+⋯+10021^2+2^2+\dots+100^2.

Решение

S1(100)=100⋅1012=5050S_1(100)=\dfrac{100\cdot101}2=5050. S2(100)=100⋅101⋅2016=338350S_2(100)=\dfrac{100\cdot101\cdot201}6=338350.

Итог

  • Sk(n)=1k+⋯+nkS_k(n)=1^k+\dots+n^k; складываем бином (m+1)k+1(m+1)^{k+1} по m=1,…,nm=1,\dots,n: сумма (m+1)k+1−mk+1(m+1)^{k+1}-m^{k+1} сокращается до (n+1)k+1−1(n+1)^{k+1}-1.
  • (n+1)k+1−1=∑i=0k(k+1i)Si(n)(n+1)^{k+1}-1=\sum_{i=0}^{k}\binom{k+1}{i}S_i(n), откуда Sk(n)S_k(n) находится через S0,…,Sk−1S_0,\dots,S_{k-1}.
  • S1(n)=n(n+1)2S_1(n)=\dfrac{n(n+1)}2, S2(n)=n(n+1)(2n+1)6S_2(n)=\dfrac{n(n+1)(2n+1)}6, S3(n)=(n(n+1)2)2S_3(n)=\left(\dfrac{n(n+1)}2\right)^2.
ПрактикаЗагружаем тест…