На вопрос: «Умеете ли вы складывать одинаковые степени последовательных натуральных чисел?», многие недоумённо пожмут плечами: кто же не умеет ... складывать? Однако складывать можно по-разному. Всем, наверное, известна небольшая история — легенда о 8-летнем Гауссе. В то время как его одноклассники трудились над вычислением суммы $1+2+3+\ldots+20$, Гаусс увидел простую закономерность
$$
1+20=\ldots=10+11=21
$$
и сразу получил ответ: 210.
Конечно, найти суммы при сложении вторых, третьих, четвёртых, ... степеней натуральных чисел уже значительно сложнее. В этой статье рассказывается о трёх простых способах построения формул суммирования, с помощью которых вы легко вычислите любую такую сумму.
Итак, суммы, которыми мы будем заниматься, имеют вид
$$
S_q(n)=1^q+2^q+\ldots+n^q.\tag1
$$
Число $q$ предполагается целым и неотрицательным. Например,
$$
\begin{aligned}
S_2(4)&=1^2+2^2+3^2+4^2=30,\\
S_{10}(2)&=1^{10}+2^{10}=1025.
\end{aligned}
$$
Ясно, что $S_0(n)$ для любого натурального $n$ совпадает с $n$, так как все $n$ слагаемых в этом случае равны 1.
§ 1. Что даёт бином Ньютона?
При вычислении сумм (1) нам поможет бином Ньютона. (О биноме Ньютона см. Н. Я. Виленкин, «Комбинаторика», М.: Наука, 1969.)
$$
(k-1)^{q+1}=k^{q+1}-C_{q+1}^1k^q+C_{q+1}^2k^{q-1}-\ldots+(-1)^qC_{q+1}^qk-(-1)^q.\tag2
$$
Перенесём первое слагаемое из правой части в левую и, полагая последовательно $k=1$, 2, $\ldots$, $n$, сложим полученные результаты. Если использовать обозначение (1), мы получим
$$
-n^{q+1}=-C_{q+1}^1S_q(n)+C_{q+1}^2S_{q-1}(n)-\ldots+(-1)^qC_{q+1}^qS_1(n)-(-1)^qS_0(n).
$$
Из этого тождества находим
$$
S_q(n)=\dfrac1{q+1}\{n^{q+1}+C_{q+1}^2S_{q-1}(n)-\ldots+(-1)^qC_{q+1}^qS_1(n)-(-1)^qS_0(n)\}.\tag3
$$
При $q=1$:
$$
S_1(n)=\dfrac12\{n^2+C_2^2S_0(n)\}=\dfrac12(n^2+n).
$$
Теперь, получив выражение для $S_1(n)$, положим в (3) $q=2$:
$$
S_2(n)=\dfrac13\{n^3+C_3^2S_1(n)-S_0(n)\}=\dfrac13{\left\{n^3+\dfrac32(n^2+n)+\dfrac12n\right\}}=\dfrac13{\left(n^3+\dfrac32n^2+\dfrac12n\right)}.
$$
Так последовательно мы можем получить с помощью тождества (3) выражения для $S_3(n)$, $S_4(n)$ и т. д.
В эффективности таких формул вы можете убедиться, проделав некоторые конкретные вычисления. Например, с помощью полученного выражения для $S_2(n)$ такая большая сумма, как $1^2+2^2+\ldots+99^2+100^2$ находится очень быстро: $S_2(100)=338\,350$. А сколько потребовалось бы времени для последовательного сложения!
§ 2. Вместо q членов — один
Итак, к каждой из формул для вычисления сумм $S_q(n)$, $q=1$, 2, $\ldots$ можно последовательно прийти с помощью общего соотношения (3). Такие соотношения, которые определяют новый член некоторой последовательности по её предыдущим членам, называются рекуррентными.
Конечно, более предпочтительными являются такие рекуррентные соотношения, которые содержат в правой части возможно меньше членов, — в лучшем случае только один: предшествующий определяемому.
Для последовательности сумм $S_q(n)$ такое простое рекуррентное соотношение существует.
Для того чтобы его записать, введём следующее обозначение. Пусть $P_m(n)$ — некоторый многочлен степени $m$ относительно $N$:
$$
P_m(n)=a_0n^m+a_1n^{m-1}+\ldots+a_{m-1}n+a_m.
$$
Тогда $P_m^*(n)$ — это многочлен степени $m+1$, получающийся из многочлена $P_m(n)$ заменой в нём степеней $n^k$ выражениями $\dfrac{n^{k+1}-n}{k+1}$ ($k=0$, 1, $\ldots$, $m$).
Очевидно следующее простое свойство: если $P(n)$ и $Q(n)$ — два многочлена, то
$$
[P(n)+Q(n)]^*=P^*(n)+Q^*(n).\tag4
$$
Теперь докажем теорему, состоящую из двух утверждений.
Теорема 1.
- Сумма $S_q(n)$ представляет собой многочлен степени $q+1$ относительно $n$ без свободного члена.
- Сумма $S_q(n)$ связана с суммой $S_{q-1}(n)$ ($q=1$, 2, $\ldots$) соотношением
$$
S_q(n)=n+qS_{q-1}^*(n).\tag5
$$
Доказательство. Оба пункта докажем, применяя полную математическую индукцию.
1°. Так как $S_0(n)$ совпадает с $n$, то первое утверждение при $q=0$ справедливо. Предположим, что оно верно для сумм $S_0(n)$, $S_1(n)$, $\ldots$, $S_{q-1}(n)$. Тогда в правой части (3) мы получим многочлен степени $q+1$ без свободного члена, т. е. утверждение верно и для следующей суммы $S_q(n)$. Следовательно, оно имеет место для всех сумм $S_q(n)$, $q\ge0$.
2°. Соотношение (5) выполняется, очевидно, для $q=1$:
$$
S_1(n)=n+n^*=n+\dfrac{n^2-n}2=\dfrac{n(n+1)}2.
$$
Предположим, что оно справедливо для $q=1$, 2, $\ldots$, $m-1$. Тогда согласно тождеству (3) для $q=m$ получим
$$
\begin{gather*}
S_m(n)=\dfrac1{m+1}\bigl\{n^{m+1}+C_{m+1}^2[n+(m-1)S_{m-2}^*(n)]-{}\\{}-C_{m+1}^3[n+(m-2)S_{m-3}^*(n)]+\ldots+(-1)^mC_{m+1}^m[n+S_0^*(n)]-(-1)^mC_{m+1}^{m+1}n\bigr\}=\\=\dfrac1{m+1}\bigl\{n^{m+1}+n(C_{m+1}^2-C_{m+1}^3+\ldots+(-1)^{m+1}C_{m+1}^{m+1})+{}\\{}+(m-1)C_{m+1}^2S_{m-2}^*(n)-(m-2)C_{m+1}^3S_{m-3}^*(n)+\ldots+(-1)^mC_{m+1}^mS_0^*(n)\bigr\}.
\end{gather*}
$$
Воспользуемся теперь тем, что
$$
1-C_{m+1}^1+C_{m+1}^2-\ldots+(-1)^{m+1}C_{m+1}^{m+1}=0
$$
и, следовательно,
$$
C_{m+1}^2-C_{m+1}^3+\ldots+(-1)^{m+1}C_{m+1}^{m+1}=C_{m+1}^1-1=m.
$$
Замечая ещё, что
$$
C_{m+1}^k\dfrac{m-k+1}{m+1}=C_m^k
$$
и используя свойство (4) операции $^*$, получим такое выражение для $S_m(n)$:
$$
S_m(n)=\dfrac{n^{m+1}+nm}{m+1}+[C_m^2S_{m-2}(n)-C_m^3S_{m-3}(n)+\ldots+(-1)^mC_m^mS_0(n)]^*.
$$
Полагая в (3) $q=m-1$, получим, что выражение в квадратных скобках равно $mS_{m-1}(n)-n^m$, следовательно,
$$
\begin{gather*}
S_m(n)=\dfrac{n^{m+1}+nm}{m+1}+[mS_{m-1}(n)-n^m]^*=\\=\dfrac{n^{m+1}+nm}{m+1}+mS_{m-1}^*(n)-\dfrac{n^{m+1}-n}{m+1}=n+mS_{m-1}^*(n).
\end{gather*}
$$
Таким образом, (5) верно и для $q=m$. Теорема доказана.
Пример. Предположим, вы знаете, что
$$
S_3(n)=\dfrac14(n^4+2n^3+n^2).
$$
Найдём выражение для $S_4(n)$:
$$
\begin{gather*}
S_4(n)=n+4S_3^*(n)=n+(n^4+2n^3+n^2)^*=\\=n+\dfrac{n^5-n}5+2\dfrac{n^4-n}4+\dfrac{n^3-n}3=\dfrac{n^5}5+\dfrac{n^4}2+\dfrac{n^2}3-\dfrac n{30}.
\end{gather*}
$$
§ 3. Общая формула
Бином Ньютона, однако, может дать значительно больше, чем тождество (3), доказанное в § 1.
Рассмотрим следующие преобразования ($m$ и $n$ предполагаются натуральными числами):
$$
m^n-1=[(m-1)+1]^n-1=(m-1)C_n^1+(m-1)^2C_n^2+\ldots+(m-1)^nC_n^n.
$$
Пусть $m\ne1$. Разделив обе части тождества на $m-1$, получим
$$
1+m+m^2+\ldots+m^{n-1}=C_n^1+(m-1)C_n^2+\ldots+(m-1)^{n-1}C_n^n.\tag6
$$
Это равенство справедливо для всех натуральных $m$ и $n$, в том числе и для $m=1$ (в этом случае оно очевидно). Поскольку слева и справа мы имеем многочлены степени $n-1$ относительно $m$, то это возможно лишь в том случае, если многочлены тождественно равны, т. е. их коэффициенты совпадают (в данном случае все они равны единице). Если раскрыть скобки в правой части (6) и приравнять коэффициенты при $m^k$, $k=0$, 1, $\ldots$, $n-1$, единице, то получится ряд тождеств, связывающих биномиальные коэффициенты. Для нас важно следующее: если степени $m^k$, $k=0$, 1, $\ldots$, $n-1$ слева и справа в (6) заменить любыми числами $a_0$, $a_1$, $\ldots$, $a_{n-1}$, равенство не нарушится: ведь коэффициенты перед числами $a_k$ останутся равными единице! Таким образом, мы приходим к следующему тождеству, верному для любых чисел $a_0$, $a_1$, $\ldots$, $a_{n-1}$:
$$
\begin{gather*}
a_0+a_1+a_2+\ldots+a_{n-1}=C_n^1+(a_1-a_0)C_n^2+(a_2-2a_1+a_0)C_n^3+\ldots\\\ldots+[a_{n-1}-C_{n-1}a_{n-2}+C_{n-1}^2a_{n-3}-\ldots+(-1)^{n-1}a_0]C_n^n.\tag7
\end{gather*}
$$
Теорема 2. Сумма $S_q(n)$ в общем случае может быть вычислена по формуле
$$
\begin{gather*}
S_q(n)=C_n^1+(2^q-1)C_n^2+(3^q-2\cdot2^q+1)C_n^3+\ldots\\\ldots+[(q+1)^q-C_q^1q^q+C_q^2(q-1)^2-\ldots+(-1)^q]C_n^{q+1}.\tag8
\end{gather*}
$$
Доказательство. Положим в тождестве (7) $a_k=(k+1)^q$, $k=0$, 1, $\ldots$, $n-1$ и рассмотрим вначале значения $n\le q+1$. Так как в этом случае $C_n^p=0$ для $p\gt q+1$, то из (7) вытекает формула (8) при условии $1\le n\le q+1$. Однако слева и справа мы имеем многочлены степени $q+1$ относительно $n$ без свободного члена и, следовательно, они должны совпадать для всех $n$. Действительно, в противном случае их разность — многочлен степени не выше $q+1$ — имел бы $q+2$ вещественных корней: 0, 1, 2, $\ldots$, $q+1$.
Попытайтесь самостоятельно доказать, что тогда этот многочлен тождественно равен нулю.
Формула (8) представляет сумму $S_q(n)$ в виде линейной комбинации сочетаний $C_n^1$, $C_n^2$, $\ldots$, $C_n^{q+1}$.
$$
\begin{aligned}
S_0(n)&=C_n^1,\\
S_1(n)&=C_n^1+C_n^2,\\
S_2(n)&=C_n^1+3C_n^2+2C_n^3,\\
S_3(n)&=C_n^1+7C_n^2+12C_n^3+6C_n^4,\\
S_4(n)&=C_n^1+15C_n^2+50C_n^3+60C_n^4+24C_n^5
\end{aligned}
$$
и т. д.
Исследовать любопытные закономерности, возникающие между коэффициентами этих комбинаций, например, законы образования коэффициентов по столбцам, предоставляем читателям.
Приведём в заключение ещё несколько задач о суммах $S_q$.
Упражнения
- Покажите, что
$$
\begin{aligned}
S_1&=S_1,\\
2(S_1)^2&=2S_3,\\
4(S_1)^3&=3S_5+S_3,\\
8(S_1)^4&=4S_7+4S_5
\end{aligned}
$$
и вообще, что при $k=1$, 2, 3, $\ldots$
$$
2^{k-1}(S_1)^k=C_k^1S_{2k-1}+C_k^3S_{2k-3}+C_k^5S_{2k-5}+{\ldots},
$$
причём последний член стоящего справа выражения равен $S_k$ либо $kS_{k+1}$ в зависимости от того, нечётно $k$ или чётно.
- Покажите, что
$$
\begin{aligned}
3S_2&=3S_2,\\
6S_2S_1&=5S_4+S_2,\\
12S_2(S_1)^2&=7S_6+5S_4,\\
24S_2(S_1)^3&=9S_8+14S_6+S_4
\end{aligned}
$$
и вообще, что при $k=1$, 2, 3, $\ldots$
$$
3\cdot2^{k-1}S_2(S_1)^{k-1}=(C_k^0+2C_k^1)S_{2k}+(C_k^2+2C_k^3)S_{2k-2}+{\ldots},
$$
причём последний член стоящего справа вьражения равен либо $(k+2)S_{k+1}$, либо $S_k$, в зависимости от того, нечётно $k$ или чётно.
- Покажите, что
$$
\begin{aligned}
S_3&=(S_1)^2,\\
S_5&=(S_1)^2\cdot\dfrac{4S_1-1}3,\\
S_7&=(S_1)^2\cdot\dfrac{6(S_1)^2-4S_1+1}3
\end{aligned}
$$
и вообще, что $S_{2k-1}$ (где $2k-1\ge3$) является многочленом от $S_1=\dfrac{n(n+1)}2$ степени $k$, делящимся на $(S_1)^2$.
- Покажите, что
$$
\begin{aligned}
S_4&=S_2\cdot\dfrac{6S_1-1}5,\\
S_6&=S_2\cdot\dfrac{12(S_1)^2-6S_1+1}7,\\
S_8&=S_2\cdot\dfrac{40(S_1)^3-40(S_1)^2+18S_1-3}{15}
\end{aligned}
$$
и вообще, что $\dfrac{S_{2k}}{S_2}$ является многочленом степени $k-1$ от $S_1$.
- Докажите, что при $k\ge1$ (но не при $k=0$)
$$
S_k(-x-1)=(-1)^{k-1}S_k(x).
$$
- Найдите сумму: $1+27+125+\ldots+(2n-1)^3$.
- Найдите сумму: $2^2+5^2+8^2+\ldots+(3n-1)^2$.
