Курляндчик Л. Д.

‍,

Лисицкий А. Д.

Суммы и произведенияКурляндчик Л. Д., Лисицкий А. Д. Суммы и произведения // Квант. — 1978. — № 10. — С. 31‍—‍37.‍‍

Искусством приводить длинную сумму или громоздкое произведение к простому виду, угадывать, когда такое упрощение возможно, придумывать и доказывать равенства вроде следующих: $$ \begin{gather*} 1\cdot2+2\cdot3+3\cdot4+\ldots+99\cdot100=\dfrac{99\cdot100\cdot101}3,\\ 1^2+2^2+3^2+\ldots+50^2=\dfrac{101(101^2-1)}{24},\\ (1\cdot2\cdot2^2)(1\cdot2\cdot3\cdot3^3)(1\cdot2\cdot3\cdot4\cdot4^4)\ldots (1\cdot2\cdot3\cdot\ldots\cdot9\cdot9^9)=(1\cdot2\cdot3\cdot\ldots\cdot9) ^{10},\\ \dfrac11-\dfrac{1\cdot2}{10\cdot9}-\dfrac{1\cdot2\cdot3}{10\cdot9\cdot8}+ \ldots+\dfrac{1\cdot2\cdot3\cdot\ldots\cdot10}{10\cdot9\cdot8\cdot\ldots\cdot 1}=\dfrac{11}{12}\cdot2,\\ \dfrac11+\dfrac{1\cdot2}{10\cdot9}+\dfrac{1\cdot2\cdot3}{10\cdot9\cdot8}+ \ldots+\dfrac{1\cdot2\cdot3\cdot\ldots\cdot10}{10\cdot9\cdot8\cdot\ldots\cdot 1}=\dfrac{11}{2^{11}}\left(\dfrac21+\dfrac{2^2}2+\dfrac{2^3}3+\ldots+ \dfrac{2^11}{11}\right), \end{gather*} $$ овладеть далеко не просто. Тут требуются большой опыт, интуиция, и, как в каждом искусстве, умение свободно применять различные «технические» приёмы. Мы продемонстрируем некоторые из таких приёмов на ряде примеров; среди них — и совсем простые упражнения, и трудные задачи (в числе последних — задачи М434 и М470 из Задачника «Кванта»).

Мы записываем Формулы, как правило, коротко, с помощью обозначений $$ \begin{aligned} \textstyle\sum\limits_{k=1}^na_k&=a_1+a_2+\ldots+a_n,\\ \textstyle\prod\limits_{k=1}^nb_k&=b_1\cdot b_2\cdot\ldots\cdot b_n,\\ n!&=1\cdot2\cdot\ldots\cdot n. \end{aligned} $$ Советуем тем, кто ещё не научился ими пользоваться, расписывать выкладки более подробно.

1. Остаются крайние

Этот заголовок объясняется следующим очевидным равенством: $$ (a_2-a_1)+(a_3-a_2)+(a_4-a_3)+\ldots+(a_n-a_{n-1})+(a_{n+1}-a_n)=a_{n+1}-a_1 \tag1 $$ или $$ \textstyle\sum\limits_{k=1}^n{}(a_{k+1}-a_k)=a_{n+1}-a_1,\tag{1′} $$ из которого можно, выбирая различным образом последовательность $(a_k)$‍,‍ получить много отнюдь не очевидных равенств.

Пример 1. Положив $a_k=-\dfrac1k$‍,‍ получаем $$ \sum\limits_{k=1}^n\dfrac1{k(k+1)}=\dfrac n{n+1}; $$ трудно найти зад алгебре, где бы не встречался этот пример.

Пример 2. Положим $a_k=\dfrac{k(k-1)d}2$‍.‍ Поскольку $a_{k+1}-a_k=kd$‍,‍ равенство (1) принимает вид $$ \sum\limits_{k=1}^nkd=\dfrac{n(n+1)d}2. $$ Добавив к каждому члену суммы слева ещё по $a-d$‍,‍ а к сумме справа $n(a-d)$‍,‍ получаем известную формулу для суммы $n$‍‍ членов арифметической прогрессии: $$ a+(a+d)+\ldots+(a+(n-1)d)=n(a-d)+\dfrac{n(n+1)d}2=na+\dfrac{n(n-1)d}2. $$

Упражнение 1. Возьмите в (1) $a_k=\dfrac{(2k-1)^3}{24}$‍‍ и получите формулу для $\sum\limits_{k=1}^nk^2$‍.‍

Пример 3. Пусть $m$‍‍ — натуральное число. Положим $$ a_k=\dfrac{(k-1)k(k+1)\ldots(k+m)}{m+2}. $$ Тогда $$ a_{k+1}-a_k=\dfrac{k(k+1)\ldots(k+1+m)}{m+2}-\dfrac{(k-1)k\ldots(k+m)}{m+2}= k(k+1)\ldots(k+m). $$ В этом случае равенство (1) запишется так: $$ \sum\limits_{k=1}^nk(k+1)\ldots(k+m)=\dfrac{n(n+1)\ldots(n+m+1)}{m+2}. $$

Равенство (1) можно использовать и по-другому. Пусть нам надо доказать, что $$ \textstyle\sum\limits_{k=1}^nf(k)=g(n).\tag2 $$ Попробуем доказать равенство $$ g(k)-g(k-1)=f(k).\tag3 $$ Если нам это удастся, то будет доказано и (2). В самом деле, рассмотрим вспомогательную последовательность $$ \left\{\begin{array}{l}a_1=0,\\a_{k+1}=g(k).\end{array}\right. $$ Для этой последовательности равенство (1) имеет вид $$ \textstyle\sum\limits_{k=1}^n{}[g(k)-g(k-1)]=g(n), $$ что, ввиду (3), равносильно (2).

Докажем, например, таким способом равенство $$ \textstyle\sum\limits_{k=1}^nC_{l+k-1}^l=C_{l+n}^{l+1}.\tag4 $$ В соответствии со сказанным для этого достаточно проверить равенство $C_{l+n}^{l+1}-C_{l+n-1}^{l+1}=C_{l+n-1}^l$‍‍ или $C_{l+n-1}^l+C_{l+n-1}^{l+1}=C_{l+n}^{l+1}$‍,‍ вытекающее из известного тождества $C_n^m+C_n^{m+1}=C_{n+1}^{m+1}$‍‍ («Алгебра и начала анализа 9», п. 8). В п. 3 мы докажем тождество (4) другим способом.

Всё вышесказанное переносится и на произведения. Напишем, прежде всего, мультипликативный аналог равенства (1): $$ \dfrac{a_2}{a_1}\cdot\dfrac{a_3}{a_2}\cdot\dfrac{a_4}{a_3}\cdot\ldots\cdot \dfrac{a_n}{a_{n-1}}\cdot\dfrac{a_{n+1}}{a_n}=\dfrac{a_{n+1}}{a_1}\tag5 $$ или $$ \prod\limits_{k=1}^n\dfrac{a_{k+1}}{a_k}=\dfrac{a_{n+1}}{a_1}.\tag{5′} $$ Это равенство можно использовать, подставляя в него произвольные последовательности $(a_k)$‍‍ (с ненулевыми членами) и для доказательства заданных тождеств.

Докажем, например, что‍$$ \prod\limits_{k=1}^n{}(2^k-1)!!=\dfrac{2\cdot(2^n)!}{2^{2^n}},\tag6 $$ для чего проверим равенство $$ \dfrac{2\cdot(2^n)!}{2^{2^n}}:\dfrac{2\cdot(2^{n-1})!}{2^{2^{n-1}}}= (2^n-1)!!\tag7 $$ или $$ \dfrac{(2^n)!}{(2^{n-1})!\cdot2^{2^{n-1}}}=(2^n-1)!!.\tag{7′} $$ Равенство (7′) легко доказывается при помощи двух очевидных тождеств: $$ (2t-1)!!=\dfrac{(2t)!}{(2t)!!},\quad(2t)!!=2^t\cdot t!. $$ Равенство (6) можно также доказать, прологарифмировав его и перейдя к сумме.

Из (6) можно вывести, что в разложение числа $(2^n)!$‍‍ на простые множители двойка входит ровно $2^n-1$‍‍ раз (подумайте, почему это так).

Итак, рассмотренный приём позволяет не только получать новые равенства, но и доказывать уже заданные.

Упражнения

Докажите, что:

2. $$\sum\limits_{k=1}^n\dfrac1{k(k+1)(k+2)}= \dfrac14-\dfrac1{2(n+1)(n+2)}.$$
3. $$\sum\limits_{k=1}^n\dfrac{x^{2^{k-1}}}{1-x^{2^k}}=\dfrac1{1-x}\cdot \dfrac{x-x^{2^n}}{1-x^{2^n}}.$$
4. $$\textstyle\sum\limits_{k=1}^nk\cdot k!=(n+1)!-1.$$
5. $$\textstyle\prod\limits_{k=1}^nk^k\cdot k!=(n!)^{n+1}.$$
6. $$\begin{gathered}a_1+(a_1+1)a_2+(a_1+1)(a_2+1)a_3+\ldots+(a_1+1)(a_2+1) \ldots(a_{n-1}+1)a_n=\\=(a_1+1)(a_2+1)\ldots(a_n+1)-1.\end{gathered}$$
7. $$\sum\limits_{k=1}^n\dfrac1{k(k+1)\ldots(k+m)}=\dfrac1m\left(\dfrac1{m!}- \dfrac1{(n+1)(n+2)\ldots(n+m)}\right).$$
8. $$\sum\limits_{k=1}^n\dfrac{x^k\cdot k!}{(x+1)(2x+1)\ldots(kx+1)}= \dfrac1{x-1}\cdot\dfrac{x^{n+1}\,(n+1)!}{(x+1)(2x+1)\ldots(nx+1)}+ \dfrac x{1-x}.$$
9. $$\sum\limits_{k=0}^{n-1}\dfrac{p_0p_1\ldots p_kq_{k+1}} {(p_1+q_1)\ldots(p_{k+1}+q_{k+1})}=1-\dfrac{p_1p_2\ldots p_n}{(p_1+q_1)\ldots (p_n+q_n)}.$$ (Здесь $(p_k)$‍‍ и $(q_k)$‍‍ — две последовательности и $p_0=1$‍.)‍

К сожалению, указанный способ годится только в том случае, когда в сумме $\sum\limits_{k=1}^nb_k$‍‍ слагаемые $b_k$‍‍ не зaвисят от $n$‍.‍ В следующем пункте мы будем доказывать равенства, в которых слагаемые зависят от $n$‍.‍

2. Метод «туда-назад»

Название этого метода (но не сам метод) — выдумка авторов. Историки математики утверждают, что именно с его помощью маленький Гаусс удивил своего школьного учителя, быстро найдя сумму натуральных чисел от 1 до 100. Покажем применение метода «туда-назад» на примерах.

Докажем, что для нечётного $n$‍‍ $$ \textstyle\sum\limits_{k=0}^n{}(-1)^k\sqrt{C_n^k}=0. $$ Запишем сумму $S_n$‍‍ двумя способами $$ \def\|#1{\smash{#1}\vphantom{C_n^0}} \begin{align} S_n&=\sqrt{C_n^0}-\sqrt{C_n^1}+\sqrt{C_n^2}-\ldots+\sqrt{\|{C_n^{n\smash-1}}}- \sqrt{C_n^n}\tag*{(туда),}\\ S_n&=-\sqrt{C_n^n}+\sqrt{\|{C_n^{n\smash-1}}}-\sqrt{\|{C_n^{n\smash-2}}}+ \ldots-\sqrt{C_n^1}+\sqrt{C_n^0}\tag*{(назад).} \end{align} $$ В нашей сумме перед $\sqrt{C_n^n}$‍‍ знак минус, потому что $n$‍‍ нечётно. Сложим два полученных выражения: $$ 2S_n=(\sqrt{C_n^0}-\sqrt{C_n^0})+(-\sqrt{C_n^1}+\sqrt{C_n^1})+\ldots+ (-\sqrt{C_n^n}+\sqrt{C_n^n}). $$ Легко сообразить, что в каждой скобке стоит нуль, так как $C_n^m=C_n^{n-m}$‍.‍ Поэтому $2S_n=0$‍,‍ откуда $S_n=0$‍.‍

Ещё пример: $$ \sum\limits_{k=0}^{2n+1}\dfrac{(-1)^k}{(C_{2n+1}^k)^2}=0. $$

Действуем аналогично: $$ \begin{align} S_n&=\dfrac1{(C_{2n+1}^0)^2}-\dfrac1{(C_{2n+1}^1)^2}+\ldots- \dfrac1{(C_{2n+1}^{2n+1})^2}\tag*{(туда),}\\ S_n&=-\dfrac1{(C_{2n+1}^{2n+1})^2}+\dfrac1{(C_{2n+1}^{2n})^2}-\ldots+ \dfrac1{(C_{2n+1}^0)^2}\tag*{(назад).} \end{align} $$ Складывая эти выражения и учитывая, что $C_{2n+1}^k=C_{2n+1}^{2n+1-k}$‍,‍ получаем $2S_n=0$‍.‍ Отсюда $S_n=0$‍.‍

А вот более сложный, но и более интересный пример на эту же тему: $$ \sum\limits_{k=0}^n\dfrac{(-1)^k}{C_n^k}=\dfrac{n+1}{n+2}(1+(-1)^n).\tag8 $$

Решить эту задачу так же просто, как две предыдущие, не удаётся. Обозначим $\displaystyle\sum\limits_{k=0}^n\dfrac{(-1)^k}{C_n^k}$‍‍ через $S_n$‍.‍ Если $n$‍‍ нечётно, вы без труда докажете, что $S_n=0$‍.‍ Случай же чётного $n$‍‍ сведём к нечётному. Проследите внимательно, как это делается. Обозначим $\displaystyle\sum\limits_{k=0}^n\dfrac{(-1)^k(k+1)}{C_n^k}$‍‍ через $T_n$‍.‍ Запишем $T_n$‍‍ двумя способами: $$ \begin{align} T_n&=\dfrac1{C_n^0}-\dfrac2{C_n^1}+\ldots+\dfrac{n+1}{C_n^n}\tag*{(туда),}\\ T_n&=\dfrac{n+1}{C_n^n}-\dfrac n{C_n^{n-1}}+\ldots+\dfrac1{C_n^0} \tag*{(назад).} \end{align} $$ Складывая, получаем $$ 2T_n=(n+2)\left(\dfrac1{C_n^0}-\dfrac1{C_n^1}+\ldots+\dfrac1{C_n^n}\right)= (n+2)\,S_n. $$ С другой стороны, $$ T_n=\sum\limits_{k=0}^n\dfrac{(-1)^k\,(k+1)\,k!\,(n-k)!}{n!}=(n+1) \sum\limits_{k=0}^n\dfrac{(-1)^k}{C_{n+1}^{k+1}}=(n+1)(1-S_{n+1}). $$ Ho так как $S_{n+1}=0$‍‍ ($n+1$‍‍ нечётно), $T_n=n+1$‍.‍ Мы уже доказали, что $S_n=\dfrac2{n+2}T_n$‍.‍ Значит, $S_n=\dfrac{2(n+1)}{n+2}$‍.‍ Осталось заметить, что $$ \dfrac{n+1}{n+2}(1+(-1)^n)=\begin{cases} 0,&n~\text{нечётно},\\ \dfrac{2(n+1)}{n+2},&n~\text{чётно}.\end{cases} $$

Доказательство равенства $$ \sum\limits_{k=0}^n\dfrac1{C_n^k}=\dfrac{n+1}{2^{n+1}}\sum\limits_{k=1}^{n+1} \dfrac{2^k}k\tag9 $$ сложнее всех предыдущих, но оно и самое поучительное.

Введём следующие обозначения: $$ \sum\limits_{k=0}^n\dfrac1{C_n^k}=D_n;\quad \sum\limits_{k=0}^n\dfrac{k+1}{C_n^k}=E_n;\quad \dfrac{n+1}{2^{n+1}}\sum\limits_{k=1}^{n+1}\dfrac{2^k}{k!}=F_n. $$

Сначала по методу «туда-назад» дважды запишем сумму $$ \begin{align} E_n&=\dfrac1{C_n^0}+\dfrac2{C_n^1}+\ldots+\dfrac{n+1}{C_n^n}\tag*{(туда),}\\ E_n&=\dfrac{n+1}{C_n^n}+\dfrac n{C_n^{n-1}}+\ldots+\dfrac1{C_n^0} \tag*{(назад).} \end{align} $$ Сложим эти равенства: $$ 2E_n=(n+2)\sum\limits_{k=0}^n\dfrac1{C_n^k}=(n+2)\,D_n. $$ Значит, $D_n=\dfrac2{n+2}E_n$‍.‍ Теперь, проделав выкладки, аналогичные тем, которые мы провели при решении предыдущей задачи, выразим $E_n$‍‍ через $D_{n+1}$‍.‍ А именно, $$ E_n=\sum\limits_{k=0}^n\dfrac{k+1}{C_n^k}=(n+1)\sum\limits_{k=0}^n\dfrac1 {C_{n+1}^{k+1}}=(n+1)(D_{n+1}-1), $$ и мы можем выразить $D_{n+1}$‍‍ через $D_n$‍:‍ $$ D_n=\dfrac2{n+2}E_n=\dfrac2{n+2}(n+1)(D_{n+1}-1), $$ откуда $$ D_{n+1}=1+\dfrac{n+2}{2(n+1)}D_n. $$

Теперь, пользуясь методом математической индукции, докажем, что $D_n=F_n$‍‍ при всех целых $n\ge0$‍.‍ Легко видеть, что $D_0=1$‍‍ и $F_0=1$‍.‍ Предположим, что $D_s=F_s$‍.‍ Тогда $$ \begin{gathered} D_{s+1}=1+\dfrac{s+2}{2(s+1)}D_s=1+\dfrac{s+2}{2(s+1)}F_s= 1+\dfrac{s+2}{2(s+1)}\cdot\dfrac{s+1}{2^{s+1}}\sum\limits_{k=1}^{s+1} \dfrac{2^k}k=\\=1+\dfrac{s+2}{2^{s+2}}\sum\limits_{k=1}^{s+1}\dfrac{2^k}k= \dfrac{s+2}{2^{s+2}}\sum\limits_{k=1}^{s+2}\dfrac{2^k}k=F_{s+1}. \end{gathered} $$ Значит, $D_n=F_n$‍‍ при всех целых $n\ge0$‍.‍ Задача решена.

Доказав равенства (8) и (9), мы решили задачу М470 («Квант», 1977, № 10). Равенство (9) позволяет предложить новое решение задачи М434 («Квант», 1977, № 12).

Пусть $\displaystyle\sum\limits_{k=1}^n\dfrac{2^k}k=\dfrac{p_n}{q_n}$‍‍‚ где $p_n$‍‍ и $q_n$‍‍ взаимно просты. Обозначим через $\nu(n)$‍‍ наибольшую степень числа 2, нa которую делится $p_n$‍.‍ Докажем, что $\nu(n)\ge\dfrac{n-3}2$‍.‍

Из (9) $\displaystyle\sum\limits_{k=0}^n\dfrac1{C_n^k}=\dfrac{n+1}{2^{n+1}} \cdot\dfrac{p_{n+1}}{q_{n+1}}$‍.‍ Поэтому $\displaystyle\dfrac{p_{n+1}}{q_{n+1}} =\dfrac{2^{n+1}}{n+1}\sum\limits_{k=0}^n\dfrac1{C_n^k}$‍‍ или $\displaystyle \dfrac{p_n}{q_n}=\dfrac{2^n}n\sum\limits_{k=0}^{n-1}\dfrac1{C_{n-1}^k}$‍.‍ Отсюда $$ \dfrac{p_n}{q_n}=\dfrac{2^n}{n!}((n-1)!+1!\,(n-2)!+2!\,(n-3)!+\ldots+ (n-1)!). $$ В $n!$‍‍ число 2 входит в степени $\left[\dfrac n2\right]+\left[\dfrac n4 \right]+\ldots\le\dfrac n2+\dfrac n4+\ldots\lt n$‍.‍ В $k!\,(n-k-1)!$‍‍ оно входит в степени, большей чем $$ \left[\dfrac k2\right]+\left[\dfrac{n-k-1}2\right]\ge \dfrac k2+\dfrac{n-k-1}2-1=\dfrac{n-3}2. $$ Значит $\nu(n)\ge\dfrac{n-3}2$‍.‍

Упражнения

Докажите равенства:

10. $$\textstyle\sum\limits_{k=0}^nkC_n^k=n\cdot2^{n-1}.$$
11. $$\textstyle\sum\limits_{k=0}^nk^3C_n^k=\dfrac32n\cdot \sum\limits_{k=0}^nk^2C_n^k-n^3\cdot2^{n-2}.$$
12. $$\textstyle\sum\limits_{k=0}^nk(C_n^k)^2=\dfrac n2C_{2n}^n.$$
13. $$\textstyle\sum\limits_{k=0}^nk^3(C_n^k)^2=-\dfrac{n^3}4C_{2n}^n+ \dfrac32\sum\limits_{k=0}^nk^2(C_n^k)^2=n^3\left(\dfrac32C_{2n-2}^{n-1}- \dfrac14C_{2n}^n\right).$$

Ну, а как же действовать, если сумму надо вычислить? Иногда это удаётся сделать методом «туда-назад». Но есть и другие методы.

3. Сравнение коэффициентов

Этот метод — один из наиболее плодотворных. Мы надеемся, что вы по достоинству оцените его красоту и изящество. Основой метода является

Теорема. Если для двух многочленов $$ \begin{aligned} f(x)&=a_0x^n+a_1x^{n-1}+\ldots+a_{n-1}x+a_n,\\ g(x)&=b_0x^m+b_1x^{m-1}+\ldots+b_{m-1}x+b_m \end{aligned} $$ $f(d)=g(d)$‍‍ при всех $d\in\mathbb{R}$‍,‍ то $m=n$‍‍ и $b_0=a_0$‍,‍ $b_1=a_1$‍,‍ $\ldots$‍,‍ $b_m=a_n$‍.‍

Эта теорема мгновенно получается, если предварительно будет доказана

Лемма. Если для многочлена $$ h(x)=C_0x^l+C_1x^{l-1}+\ldots+C_{l-1}x+C_l $$ $h(d)=0$‍‍ при любом $d\in\mathbb{R}$‍,‍ то $C_0=C_1=\ldots=C_{l-1}=C_l=0$‍.‍

Доказательство. Применим индукцию по $l$‍.‍ При $l=0$‍‍ утверждение очевидно. Предположим теперь, что наше утверждение верно при всех $l\le s-1$‍‍‍. Докажем, что тогда оно верно и для $l=s$‍.‍ Пусть $$ h(x)=C_0x^s+C_1x^{s-1}+\ldots+C_{s-1}x+C_s. $$ Тогда $2^sh(d)-h(2d)=0$‍‍ при любом $d\in\mathbb{R}$‍,‍ а степень многочлена $2^sh(x)-h(2x)$‍‍ меньше $s$‍.‍ Поэтому по предположению индукции все его коэффициенты равны нулю, т. е. $$ (2^s-2^{s-1})C_1=0,\quad(2^s-2^{s-2})C_2=0,\quad\ldots,\quad(2^s-1)C_s=0. $$ Следовательно, $C_1=C_2=\ldots=C_s=0$‍.‍ Тогда, конечно, и $C_0=0$‍.‍ Лемма доказана.

В качестве первой иллюстрации установим ещё раз равенство (4). Рассмотрим многочлен $$ f(x)=1+(1+x)+(1+x)^2+\ldots+(1+x)^{m-1}. $$ Коэффициент при $x^l$‍‍ в этом многочлене по формуле Ньютона («Алгебра и начала анализа 9», п. 9) равен $$ C_l^l+C_{l+1}^l+\ldots+C_{m-1}^l=\textstyle\sum\limits_{k=1}^{m-l} C_{l+k-1}^l. $$ С другой стороны, последовательность 1, $1+x$‍,‍ $(1+x)^2$‍,‍ $\ldots$‍,‍ $(1+x)^{m-1}$‍‍ — это геометрическая прогрессия. Поэтому $$ f(x)=\dfrac{(1+x)^m-1}{(1+x)-1}=\dfrac1x[(1+x)^m-1]. $$ Снова применяя формулу Ньютона, получаем $$ \textstyle f(x)=\dfrac1x[(1+x)^m-1]=\dfrac1x\sum\limits_{k=1}^mC_m^kx^k= \sum\limits_{k=1}^mC_m^kx^{k-1}. $$ Значит, коэффициент при $x^l$‍‍ равен $C_m^{l+1}$‍.‍ По теореме получаем (4).

Найдём $\sum\limits_{k=0}^n{}(C_n^k)^2$‍.‍ Рассмотрим многочлен $$ f(x)=(1+x)^n\,(x+1)^n= (C_n^0+C_n^1x+C_n^2x^2+\ldots+C_n^nx^n) (C_n^0x^n+C_n^1x^{n-1}+C_n^2x^{n-2}+\ldots+C_n^n). $$ Коэффициент при $x^n$‍‍ в этом произведении равен, очевидно, $\sum\limits_{k=0}^n{}(C_n^k)^2$‍.‍ С другой стороны, $f(x)=(1+x)^{2n}$‍.‍ Коэффициент при $x^n$‍‍ в нём равен $C_{2n}^n$‍.‍ По теореме получаем, что $\sum\limits_{k=0}^n{}(C_n^k)^2=C_{2n}^n$‍.‍

Теперь найдём $\sum\limits_{k=0}^n{}(-1)^k(C_n^k)^2$‍.‍ При решении предыдущей задачи мы рассматривали многочлен $f(x)=(1+x)^n(x+1)^n$‍.‍ Здесь же, по-видимому, надо взять похожий многочлен, но чтобы в нём знаки у коэффициентов чередовались. Давайте попробуем рассмотреть многочлен $$ g(x)=(1+x)^n\,(x-1)^n= (C_n^0+C_n^1x+C_n^2x^2+\ldots+C_n^nx^n) (C_n^0x^n-C_n^1x^{n-1}+C_n^2x^{n-2}-\ldots+(-1)^nC_n^n). $$

Коэффициент при $x^n$‍‍ в этом произведении равен $\sum\limits_{k=0}^n{}(-1)^k(C_n^k)^2$‍.‍ С другой стороны, $$ g(x)=(1+x)^n(x-1)^n=(-1)^n(1-x^2)^n=(-1)^n\textstyle\sum\limits_{k=0}^n (-1)^kC_n^kx^{2k}. $$ В этой сумме коэффициенты при нечётных степенях $x$‍‍ равны 0. Поэтому, если $n$‍‍ нечётно, то коэффициент при $x^n$‍‍ равен 0. Если же $n$‍‍ чётно, то коэффициент при $x^n$‍‍ равен $(-1)^{n+\frac{\scriptstyle n}{\scriptstyle2}} C_{n}^{\frac{\scriptstyle n}{\scriptstyle2}}=(-1)^{\frac{\scriptstyle n} {\scriptstyle2}}C_{n}^{\frac{\scriptstyle n}{\scriptstyle2}}$‍.‍ Итак, $$ \textstyle\sum\limits_{k=0}^n{}(-1)^k(C_n^k)^2= \begin{cases}0,&n~\text{нечётно},\\ (-1)^{\frac{\scriptstyle n}{\scriptstyle 2}}C_n^{\frac{\scriptstyle n} {\scriptstyle 2}}&n~\text{чётно}.\end{cases} $$

Упражнения

14. Найдите сумму $\sum\limits_{k=0}^n\dfrac{C_n^k}{k+1}$‍.‍ $\Big($‍‍Ответ: $\dfrac{2^{n+1}-1}{n+1}.\Big)$‍‍
15. Обозначим через $B_n^k$‍‍ коэффициент при $x^k$‍‍ в многочлене $(1+x+x^2)^n$‍.‍ Найдите сумму $\sum\limits_{k=0}^{2n}{}(B_n^k)^2$‍.‍ (Ответ: $B_{2n}^{2n}$‍.)‍

На первый взгляд этот метод выглядит очень искусственным, потому что кажется непонятным, как же научиться выбирать нужный многочлен. К сожалению, в этой статье мы не можем более подробно останавливаться на этом вопросе.

Тем не менее мы думаем, что, решив предложенные упражнения, вы сможете самостоятельно решать аналогичные задачи.

4. Преобразование Абеля

Пусть нам дана сумма $$ S_n=a_1b_1+a_2b_2+\ldots+a_nb_n, $$ где $a_1$‍,‍ $a_2$‍,‍ $\ldots$‍,‍ $a_n$‍,‍ $b_1$‍,‍ $b_2$‍,‍ $\ldots$‍,‍ $b_n$‍‍ — две последовательности. Обозначим суммы $b_1$‍,‍ $b_1+b_2$‍,‍ $\ldots$‍,‍ $b_1+b_2+\ldots+b_n$‍,‍ соответственно, через $B_1$‍,‍ $B_2$‍,‍ $\ldots$‍,‍ $B_n$‍.‍ Тогда $b_1=B_1$‍,‍ $b_k=B_k-B_{k-1}$‍‍ при $k\gt1$‍‍ и $\sum\limits_{k=1}^na_kb_k$‍‍ можно преобразовать так: $$ \begin{gathered} \textstyle\sum\limits_{k=1}^na_kb_k=a_1B_1+a_2(B_2-B_1+\ldots+a_n(B_n-B_{n-1}= \\=(a_1-a_2)B_1+(a_2-a_3)B_2+\ldots+(a_{n-1}-a_n)B_{n-1}+a_nB_n= \textstyle\sum\limits_{k=1}^{n-1}{}(a_k-a_{k+1})B_k+a_nB_n.\tag{10} \end{gathered} $$ Это преобразование называют преобразованием Абеля (о замечательном норвежском математике Нильсе Хенрике Абеле см. в «Кванте» № 5 за 1976 год‍).

Воспользовавшись преобразованием Абеля, найдём сумму $\sum\limits_{k=1}^nkq^{k-1}$‍.‍ Положим в тождестве (10) $a_1=1$‍,‍ $a_2=2$‍,‍ $\ldots$‍,‍ $a_n=n$‍;‍ $b_1=1$‍,‍ $b_2=q$‍,‍ $\ldots$‍,‍ $b_n=q^{n-1}$‍.‍ Тогда $B_k=\dfrac{q^k-1}{q-1}$‍‍ и $a_1-a_2=a_2-a_3=\ldots=a_{n-1}-a_n=-1$‍.‍ Поэтому $$ \begin{gathered} \sum\limits_{k=1}^nkq^{k-1}= \sum\limits_{k=1}^{n-1}{}(-1)\dfrac{q^k-1}{q-1}+n\dfrac{q^n-1}{q-1}= \dfrac{-1}{q-1}\sum\limits_{k=0}^{n-1}{}(q^k-1)+n\dfrac{q^n-1}{q-1}=\\ =\dfrac{-1}{q-1}\left(\dfrac{q^n-1}{q-1}-n\right)+n\dfrac{q^n-1}{q-1}= \dfrac{nq^n}{q-1}-\dfrac{q^n-1}{(q-1)^2}. \end{gathered} $$

Упражнения

Преобразованием Абеля найдите:

16. $$\textstyle\sum\limits_{k=1}^nk^2q^{k-1}.$$
17. $$\textstyle\sum\limits_{k=1}^nk\sin kx.$$
18. $$\textstyle\sum\limits_{k=1}^nk^2\cos kx.$$

Докажите равенства:

19. $$\sum\limits_{k=0}^{2n-1}\dfrac{(-1)^kk}{(C_{2n-1}^k)^2}= \dfrac{4n^2}{2n+1}\left(1-\sum\limits_{k=0}^{2n}\dfrac{(-1)^k}{(C_{2n}^k)^2} \right).$$
20. $$\sum\limits_{k=0}^n{}(-1)^k(C_n^k)^3=\begin{cases}0,&\text{если}~ n=2t+1,\\(-1)^t\dfrac{(3t)!}{(t!)^3},&\text{если}~n=2t.\end{cases}$$
21. $$\sum\limits_{k=0}^n{}(-1)^kk(C_n^k)^3=\begin{cases}(-1)^tt\dfrac{(3t)!} {(t!)^3},&\text{если}~n=2t,\\(-1)^{t+1}\dfrac{(3t+1)!}{(t!)^3},&\text{если}~ n=2t+1.\end{cases}$$
22. $$\sum\limits_{k=0}^n{}(-1)^kk^2(C_n^k)^3=\begin{cases}(-1)^t\cdot\dfrac23 t^2\dfrac{(3t)!}{(t!)^3},&\text{если}~n=2t,\\(-1)^{t+1}(2t+1)\dfrac{(3t+1)!} {(t!)^3},&\text{если}~n=2t+1.\end{cases}$$
23. Пусть $(a_n)$‍‍ — арифметическая прогрессия с разностью $d$‍.‍ Тогда $$\sum\limits_{k=0}^n{}(-1)^k\dfrac{a_{k+1}}{C_n^k}=\begin{cases}\dfrac{n+1} {n+2}(a_1+a_{n+1}),&\text{если}~n~\text{чётно},\\-\dfrac{(n+1)^2}{n+3}d,& \text{если}~n~\text{нечётно}\end{cases}$$